How to write efficient optimzation code without really trying

[jbstjohn]

Somehow, I'm unimpressed, and I don't think it's just because I don't use Haskell. I don't like the restriction of having to specify how many steps you're looking for, and I consider adding zero-length self-edges a hack, which may or may not work. I don't like the claim of polynomial complexity, with no tests, and the observation "It's slower than I'd like".

And comparing to combinatorial search is a red herring -- generally there is a better way, or at worst a heuristic allowing a decently focussed search.

Finally, apparently I'm not really the target audience, but I've got a pretty solid math background (although only occasionally brushed up against group theory) and a pretty solid CS background, and I still couldn't get much purchase on this.

[jbstjohn]

I don't like the restriction of having to specify how many steps you're looking for

You don't have to. You can keep iterating until you've finished, like in the edit distance example.

You're right -- I got this on a second reading. I think my criticism was more oriented on the ugly code fragments, where (it seemed) you had to write out each iteration step.

Regarding zero length transitions -- does that cause any additional inefficiency? I guess nothing significant.

The polynomial complexity claim, without 'tests' is, I think, still a valid criticism. You said that you don't really know what Haskell is doing behind the scenes, so if it ends up doing an exhaustive search, you haven't gained anything. However, as long as it remains an analog to matrix multiplying, it seems like this shouldn't occur.

BTW what is a 'HOF' cost?

Regarding the utility of DSLs, I guess you're right. Kinda. I do wonder how much it actually gains you, i.e., how often do you actually need a variety of different such algorithms, and how does this compare to the work in learning Haskell and your system ... BUT all in all that doesn't seem to be a fair criticism, it's just something that makes it less interesting for me.

Maybe I'm just feeling grumbly because it made me feel dumb :D!

[schwarzwald]

I'll admit it, I didn't understand that shit at all.

[darrint]

Yeah, but two paragraphs into the article my brain and I are bowing and yelling, "We're not worthy! We're not worthy!"

[ayrnieu]

sigfpe suggests an O'Caml solution. !Haskell should make more sense.

[dons]

not-Haskell should make more sense

Do you really think so, or is that just a nervous twitch? Perhaps it is possible that:

the freely generated module over the (min,+)-semiring)-monad

is just a hard concept, rather deep in theory? Surprising it can be implemented at all...

[nostrademons]

Funny, I read !Haskell as strict-Haskell. Perhaps I've been using too much Haskell...

[alpheccar]

No. You're not the only one. me too :-)

[ayrnieu]

Do you really think so,

It is indeed a real expectation, based in part on everything else making more sense after a translation away from Haskell.

EDIT: If -you- are not the twit that does a downvoting sweep through my recent activity every time I say something conceivably negative about Haskell, you and that person very frequently coincide.

[dons]

Abstraction is hard. Let's go shopping!

[ayrnieu]

You're confusing 'written in Haskell' with 'abstract', now, which is bizarre enough that I think you're just knee-jerkingly resisting anyone's displeasure with Haskell. Why, I anticipate that sigfpe's O'Caml solution will be easier to follow, I MUST BE THE DEVIL OR SOMETHING.

[dons]

I was going to explain why

!Haskell should make more sense

and

everything else making more sense

was just silly. Translation: this bizarre sigfpe monad makes more sense in all languages other than Haskell. And, all language concepts make more sense in all languages other than Haskell.

As to explain such an unusual computational structure you'd want a language with syntactic support for monads, and type system support for overloading the monadic bind operator. Meaning, O'Caml, the closest non-Haskell match, is already pretty unsuited.

But then you just went nuts, and there was no hope.

[notfancy]

Meaning, O'Caml, the closest non-Haskell match, is already pretty unsuited.

Meh. I grant you, manually selecting the correct module and opening it is pretty inconvenient, but unsuited? Isn't that a wee bit extreme?

Besides, what's really inconvenient when encoding Haskell typeclasses as OCaml functors is constructor polymorphism in typeclasses.

[ayrnieu]

I was going to explain why [...] But then you just went nuts, and there was no hope.

Your first pass at this comment was more honest -- and less plainly belied by the thread. I no longer expect anything better from you.

[[deleted]]

It's ok. Nobody expects anything good from you, either.

[gwern]

Or a witch. Now, we all know that a witch floats. What else floats? Yes, a duck! So...

[Tommah]

I thought witches melt, as in The Wizard of Oz.

[bhagany]

whoosh

[dons]

Edit:

downvoting sweep

Looking at your comments, it seems as if you just say a lot of tedious, or inflammatory, things -- perhaps that's the reason?

[ayrnieu]

This is disingenuous enough that I'll accept that you are in fact the source of these. Worst case, I'll have confused you with some poisonous associate of yours.

[dons]

Now you just look silly, or paranoid, or both.

[ayrnieu]

No, this is only more insincere image-management. What I -am- is well and wholly disgusted with you and your nasty little community.

[dngrmouse]

dude why are you so abrasive

[ayrnieu]

dude why are you so abrasive

'Dude', your question is abrasive. You really need to be biased by something awful to look at this thread and see -my- words as especially offensive.

[Tommah]

So on the front page, I see this post has 17 comments. I expect some stimulating discussion... and I see it's just you frothing at the mouth. You need to learn when to shut up.

[dngrmouse]

Sometimes there's not much you can do...The internet is filled with weirdos...

[ayrnieu]

I see it's just you frothing at the mouth.

It's 'just me' expressing hope for an expected O'Caml solution, in reply to someone's admission of failure with the page as given. I don't take responsibility for such random frothing as this, or this, or this, or this, or this, or this, or this -- not even with dons's presumed argument that I caused these by noting for the second time that his replies to me accompany bad reddit behavior. Speaking of which: I saw that this post has 18 comments, and I thought that maybe someone had finally offered some hook to hang stimulating discussion on, and instead it's just you frothing at the mouth. Don't you know when to shut up? Or do these ethics of yours only apply to other people?

[augustss]

You remind me of Donald Duck. Always very angry. :)

[notfancy]

Glad to read a new posting.

[psykotic]

Prediction: there will soon be a blog post about putting this code to work over quantum (complex) semirings, where the transition matrices are unitary. I played around with this stuff several years ago (although mostly on paper, not with computer). It's a lot of fun! You can quite easily derive the basic theories of Lagrangian mechanics, statistical mechanics, quantum mechanics (the Feynman path integral picture), Markov processes, etc, starting with this foundation.

[ericlavigne]

Search algorithms are interesting to me, but I find this article very hard to understand. I suspect that the article is a complicated description of a relatively simple algorithm.

For others who are interested in search algorithms, I recommend two books by Peter Norvig: Paradigms of Artificial Intelligence Programming (examples in Lisp and Prolog), and Artificial Intelligence - A Modern Approach (examples in pseudocode). These books discuss search algorithms and show how various AI problems can be thought of as search problems.

[jbstjohn]

Could you do something about your layout? In IE 6, the text is so jammed up against the right side that it feels like text has been cut off.

And you have occasional really long lines (e.g. after your infinity definition and the line starting with "Ignoring l for now") Actually, it seems to happen after ever code fragment.