Comments on A Neighborhood of Infinity: How to write tolerably efficient optimzation code ...

Saizan,

Oh, I'm not so bothered about t...

2007-06-26T15:26:00.000-07:00

Saizan,

Oh, I'm not so bothered about that. g has the bizarre property that you can have x==y but g x /= g y. So you can trick >>= into collapsing things together which you can later pick apart.

But I should state things rigorously. My Monad class requires that Eq and Ord are "well behaved".

Saizan,

I've been away for a few days but I...

2007-06-26T14:58:00.000-07:00

Saizan,

I've been away for a few days but I'll look closely at your example....

Trying to modify "the above code so that it finds ...

2007-06-25T12:13:00.000-07:00

Trying to modify "the above code so that it finds the one shortest path from {A,B} to {E,F}", without using runM and keeping the returned value as (step1,step4), i've accidentally found a counterexample for the third monad law:

> newtype Collapse a = Collapse { unC :: a } deriving (Show)
> instance Eq (Collapse a) where (==) _ _ = True
> instance Ord (Collapse a) where (<=) _ _ = True
> f = return . Coll
> g = return . unC

(ex3 >>= f) >>= g --> M {runM = [((B,F),4.0,[B,A,C,E])]}
ex3 >>= (\x -> f x >>= g) --> M {runM = [((A,E),6.0,[A,B,D,E]),((A,F),6.0,[A,C,E,F]),((B,E),4.0,[B,A,C,E]),((B,F),8.0,[B,D,E,F])]}

Anonymous,

Hey! Looks like someone else has...

2007-06-20T14:51:00.000-07:00

Anonymous,

Hey! Looks like someone else has been thinking along similar lines. The free-rig monad sounds exactly like mine (rig=semiring) although jcreed talks about it slightly differently from what I'd expect.

At least I now know I'm not insane...

You might be interested in the links from
http:...

2007-06-20T13:49:00.000-07:00

You might be interested in the links from
http://jcreed.livejournal.com/1024229.html

Great article, though I must admit that it took me...

2007-06-18T05:14:00.000-07:00

Great article, though I must admit that it took me quite a while to really get to grips with it. Thanks a lot for the mind-expanding experience :-)

I did a bit more work on the edit distance code be...

2007-06-17T09:08:00.000-07:00

I did a bit more work on the edit distance code because, as I hinted, I had suspicions about it. Essentially a rectangular graph is being traversed. But it turns out that each node is visited many times through a traversal. The final algorithm still has polynomial complexity in the string lengths - but it's now worse than quadratic. Hence my title "...tolerably efficient..." rather than "...blindingly efficient...":-)

Floyd-Warfield? What was I thinking? Maybe that's ...

2007-06-17T08:08:00.000-07:00

Floyd-Warfield? What was I thinking? Maybe that's the problem. I've just given away that I'm really one of those markov chain text generators...

s/Floyd-Warfield/Floyd-Warshall/

2007-06-17T04:39:00.000-07:00

s/Floyd-Warfield/Floyd-Warshall/

Very nice article.

For changing the associa...

2007-06-17T04:26:00.000-07:00

Very nice article.

For changing the associativity you could take a look at continuations. Koen Claessen uses this technique for his parser combinators (on which Text.ParserCombinators.ReadP is based). See section 9 of
http://www.cs.chalmers.se/~koen/pubs/entry-jfp04-parser.html

Me again :-)

I finally found the URL of the...

2007-06-17T01:54:00.000-07:00

Me again :-)

I finally found the URL of the article about semirings and idempotent analysis that I wanted to recommend : MASLOV DEQUANTIZATION, IDEMPOTENT AND TROPICAL MATHEMATICS:
A BRIEF INTRODUCTION

On arXiv there are lots of papers by Maslov giving computer applications of the (min,+) semiring and other idempotent semirings. The paper I linked just above is a very good overview with lots of results : Fourier-Legendre transform, shortest path problem etc...

Restricted monads will probably be possible with t...

2007-06-17T01:38:00.000-07:00

Restricted monads will probably be possible with the class families that I have seen discussed for the first time here.

Regarding the very last point, I think we're quite...

2007-06-17T00:59:00.000-07:00

Regarding the very last point, I think we're quite close to your desired solution there, with indexed type families.

A restricted Set interface is given as an example of the use of class-associated classes, in the slides below, from last week's Sydney PL research meeting. See slide 25 from Type Families in Haskell

I'm sure Manuel and the rest of the type families hackers would appreciate any interesting applications of the new indexed type families extensions in GHC head. The subject of some future sigfpe posts... ?

Floyd-Warfield?

2007-06-16T22:40:00.000-07:00

Floyd-Warfield?

Does FSM expand to "Finite State Machine" or "Flyi...

2007-06-16T22:04:00.000-07:00

Does FSM expand to "Finite State Machine" or "Flying Spaghetti Monster"?

Comments on A Neighborhood of Infinity: How to write tolerably efficient optimzation code ...

Saizan,Oh, I'm not so bothered about t...

Saizan,I've been away for a few days but I...

Trying to modify "the above code so that it finds ...

Anonymous,Hey! Looks like someone else has...

You might be interested in the links fromhttp:...

Great article, though I must admit that it took me...

I did a bit more work on the edit distance code be...

Floyd-Warfield? What was I thinking? Maybe that's ...

s/Floyd-Warfield/Floyd-Warshall/

Very nice article.For changing the associa...

Me again :-)I finally found the URL of the...

On arXiv there are lots of papers by Maslov giving computer applications of the (min,+) semiring and other idempotent semirings. The paper I linked just above is a very good overview with lots of results : Fourier-Legendre transform, shortest path problem etc...

Restricted monads will probably be possible with t...

Regarding the very last point, I think we're quite...

Floyd-Warfield?

Does FSM expand to "Finite State Machine" or "Flyi...

Saizan,

Oh, I'm not so bothered about t...

Saizan,

I've been away for a few days but I...

Anonymous,

Hey! Looks like someone else has...

You might be interested in the links from
http:...

Very nice article.

For changing the associa...

Me again :-)

I finally found the URL of the...