tag:blogger.com,1999:blog-11295132.post3662062791857319803..comments2014-08-17T09:30:19.334-07:00Comments on A Neighborhood of Infinity: How to write tolerably efficient optimzation code without really trying...Dan Piponihttps://plus.google.com/107913314994758123748noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-11295132.post-3119093273783654532012-02-24T09:37:11.123-08:002012-02-24T09:37:11.123-08:00So now that we have constraint kinds, is there a c...So now that we have constraint kinds, is there a cleaner way of stating this?Tyrhttp://www.blogger.com/profile/17404408031973346085noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-89197595401912481332007-06-26T15:26:00.000-07:002007-06-26T15:26:00.000-07:00Saizan,Oh, I'm not so bothered about that. g has t...Saizan,<BR/><BR/>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.<BR/><BR/>But I should state things rigorously. My Monad class requires that Eq and Ord are "well behaved".sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-42259107411295579442007-06-26T14:58:00.000-07:002007-06-26T14:58:00.000-07:00Saizan,I've been away for a few days but I'll look...Saizan,<BR/><BR/>I've been away for a few days but I'll look closely at your example....sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-63035009352853330992007-06-25T12:13:00.000-07:002007-06-25T12:13:00.000-07:00Trying to modify "the above code so that it finds ...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:<BR/><BR/>> newtype Collapse a = Collapse { unC :: a } deriving (Show)<BR/>> instance Eq (Collapse a) where (==) _ _ = True<BR/>> instance Ord (Collapse a) where (<=) _ _ = True<BR/>> f = return . Coll<BR/>> g = return . unC<BR/><BR/>(ex3 >>= f) >>= g --> M {runM = [((B,F),4.0,[B,A,C,E])]}<BR/>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])]}Saizanhttp://www.blogger.com/profile/07314943153376710289noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-74099983851642517162007-06-20T14:51:00.000-07:002007-06-20T14:51:00.000-07:00Anonymous,Hey! Looks like someone else has been th...Anonymous,<BR/><BR/>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.<BR/><BR/>At least I now know I'm not insane...sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-32226649436397392322007-06-20T13:49:00.000-07:002007-06-20T13:49:00.000-07:00You might be interested in the links fromhttp://jc...You might be interested in the links from<BR/>http://jcreed.livejournal.com/1024229.htmlAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-10115887846211809772007-06-18T05:14:00.000-07:002007-06-18T05:14:00.000-07:00Great article, though I must admit that it took me...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 :-)Omega Primehttp://www.blogger.com/profile/05003540528496327090noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-89126545542916677292007-06-17T09:08:00.000-07:002007-06-17T09:08:00.000-07:00I did a bit more work on the edit distance code be...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...":-)sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-89125030081495011522007-06-17T08:08:00.000-07:002007-06-17T08:08:00.000-07:00Floyd-Warfield? What was I thinking? Maybe that's ...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...sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-83197448109555477652007-06-17T04:39:00.000-07:002007-06-17T04:39:00.000-07:00s/Floyd-Warfield/Floyd-Warshall/s/Floyd-Warfield/Floyd-Warshall/Thomas Schillinghttp://www.blogger.com/profile/04274984206279511399noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-42467893100003778682007-06-17T04:26:00.000-07:002007-06-17T04:26:00.000-07:00Very nice article.For changing the associativity y...Very nice article.<BR/><BR/>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<BR/>http://www.cs.chalmers.se/~koen/pubs/entry-jfp04-parser.htmlTwan van Laarhovenhttp://www.blogger.com/profile/18138442561179666544noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-64159620707136320522007-06-17T01:54:00.000-07:002007-06-17T01:54:00.000-07:00Me again :-)I finally found the URL of the article...Me again :-)<BR/><BR/>I finally found the URL of the article about semirings and idempotent analysis that I wanted to recommend : <A HREF="http://glitvinov.googlepages.com/2007_JMS_426.pdf" REL="nofollow">MASLOV DEQUANTIZATION, IDEMPOTENT AND TROPICAL MATHEMATICS: <BR/>A BRIEF INTRODUCTION</A>alpheccarhttp://www.blogger.com/profile/14645433315403867431noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-64852725780256414242007-06-17T01:44:00.000-07:002007-06-17T01:44:00.000-07:00On arXiv there are lots of papers by Maslov giving...On arXiv there are lots of papers by <A HREF="http://arxiv.org/abs/math/0101021" REL="nofollow">Maslov</A> 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...alpheccarhttp://www.blogger.com/profile/14645433315403867431noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-57578165486214627882007-06-17T01:38:00.000-07:002007-06-17T01:38:00.000-07:00Restricted monads will probably be possible with t...Restricted monads will probably be possible with the class families that I have seen discussed for the first time <A HREF="http://www.comp.mq.edu.au/~asloane/pmwiki.php/SAPLING/SAPLING071?action=download&upname=chakravarty-slides071.pdf" REL="nofollow">here.</A>alpheccarhttp://www.blogger.com/profile/14645433315403867431noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-46831505307211553822007-06-17T00:59:00.000-07:002007-06-17T00:59:00.000-07:00Regarding the very last point, I think we're quite...Regarding the very last point, I think we're quite close to your desired solution there, with <A HREF="http://haskell.org/haskellwiki/GHC/Indexed_types" REL="nofollow">indexed type families</A>.<BR/><BR/>A restricted Set interface is given as an example of the use of class-associated classes, in the slides below, from last week's <A HREF="http://www.comp.mq.edu.au/~asloane/pmwiki.php/SAPLING/SAPLING071" REL="nofollow">Sydney PL research meeting</A>. See slide 25 from <A HREF="http://www.comp.mq.edu.au/~asloane/pmwiki.php/SAPLING/SAPLING071?action=download&upname=chakravarty-slides071.pdf" REL="nofollow">Type Families in Haskell</A><BR/><BR/>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... ?Don Stewarthttp://www.blogger.com/profile/08476737262404343154noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-12727061592199569992007-06-16T22:40:00.000-07:002007-06-16T22:40:00.000-07:00Floyd-Warfield?Floyd-Warfield?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-72530400491810271442007-06-16T22:04:00.000-07:002007-06-16T22:04:00.000-07:00Does FSM expand to "Finite State Machine" or "Flyi...Does FSM expand to "Finite State Machine" or "Flying Spaghetti Monster"?Aaron Denneyhttp://www.blogger.com/profile/15613957348593645695noreply@blogger.com