[Haskell-cafe] Difference Lists versus Accumulators
Hey all, The connection between difference lists and accumulators is probably well known, but I only recently realized it myself and a quick Google search didn't find turn up any page where this was explicitly stated, so I thought this observation might be useful to some. Every beginner Haskell student learns that this definition of reverse has O(n^2) complexity: reverse [] = [] reverse (x : xs) = reverse xs ++ [x] But what happens when we return a difference list instead, replacing [] with id, (++) with (.) and [x] with (x :)? reverse' [] = id reverse' (x : xs) = reverse xs . (x :) This definition of reverse' has type reverse' :: [a] - [a] - [a] Let's inline the second argument: reverse' [] acc = acc reverse' (x : xs) acc = reverse' xs (x : acc) And we have recovered the standard definition using an accumulator! I thought that was cute :) And may help understanding why difference lists are useful. Edsko ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Difference Lists versus Accumulators
* Edsko de Vries edskodevr...@gmail.com [2013-01-08 12:22:59+] But what happens when we return a difference list instead, replacing [] with id, (++) with (.) and [x] with (x :)? ... And we have recovered the standard definition using an accumulator! I thought that was cute :) And may help understanding why difference lists are useful. Edsko Perl: There Is More Than One Way To Do It Python: There Is One Way To Do It Haskell: There Is One Way To Do It, Up To Isomorphism :) Roman ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Example programs with ample use of deepseq?
http://article.gmane.org/gmane.comp.lang.haskell.parallel/340 (with follow-up message about rseq = rdeepseq) - J.W. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] What happened to first-class modules?
I just read this page http://www.haskell.org/haskellwiki/First-class_module. It seems there was not much no ongoing work on this topic... does somebody know what happened to first-class modules? what are the actual research papers about this topic? Thanks -- Ismael ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Example programs with ample use of deepseq?
Joachim Breitner m...@joachim-breitner.de wrote: I’m wondering if the use of deepseq to avoid unwanted lazyness might be a too large hammer in some use cases. Therefore, I’m looking for real world programs with ample use of deepseq, and ideally easy ways to test performance (so preferably no GUI applications). I’ll try to find out, by runtime observerations, which of the calls ot deepseq could be replaced by id, seq, or „shallow seqs“ that, for example, calls seq on the elements of a tuple. Now that you know when /not/ to use deepseq, let me tell you when it's appropriate: parallelization via parallel strategies. It's not exactly necessary to use deepseq (or rdeepseq in this case), but it's often very easy to express your algorithms in the usual way and then just change some of the 'map' applications to 'parMap rdeepseq'. When your algorithm is written with parallelization in mind this often gives you an amazingly parallel program by changing only a few words in your source code. Greets, Ertugrul -- Not to be or to be and (not to be or to be and (not to be or to be and (not to be or to be and ... that is the list monad. signature.asc Description: PGP signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Difference Lists versus Accumulators
See the first Worker / Wrapper paper by Andy Gill and Graham Hutton. Particularly there is exactly this derivation of reverse through preliminarily using a Hughes (difference) list. On 8 January 2013 12:22, Edsko de Vries edskodevr...@gmail.com wrote: Hey all, The connection between difference lists and accumulators is probably well known, but I only recently realized it myself and a quick Google search didn't find turn up any page where this was explicitly stated, so I thought this observation might be useful to some. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Example programs with ample use of deepseq?
surprisingly, deepseq is not used as much as I thought. http://packdeps.haskellers.com/reverse/deepseq lists a lot of packages, but (after grepping through some of the code) most just define NFData instances and/or use it in tests, but rarely in the „real“ code. For some reason I expected it to be in more widespread use. I've been using deepseq quite a bit lately, but for the purpose of debugging space leaks. If, when I deepseq a big structure, the space leak goes away, I can then apply it to some subset. After much trial-and-error I can find something which is insufficiently strict. Ideally I can then strictify that one thing and stop using the deepseq. I wish there was a more efficient way to do this. I also use it to explicitly force certain parts of a data structure so they evaluate in parallel, though that part is not actually done yet. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Example programs with ample use of deepseq?
Hi, Am Dienstag, den 08.01.2013, 13:01 -0800 schrieb Evan Laforge: surprisingly, deepseq is not used as much as I thought. http://packdeps.haskellers.com/reverse/deepseq lists a lot of packages, but (after grepping through some of the code) most just define NFData instances and/or use it in tests, but rarely in the „real“ code. For some reason I expected it to be in more widespread use. I've been using deepseq quite a bit lately, but for the purpose of debugging space leaks. If, when I deepseq a big structure, the space leak goes away, I can then apply it to some subset. After much trial-and-error I can find something which is insufficiently strict. Ideally I can then strictify that one thing and stop using the deepseq. I wish there was a more efficient way to do this. this is also a possible application of my approach, by providing a „I want this data structure to be fully evaluated now, please tell me how it currently looks, i.e. where in the data structure still thunks lie hidden.“ Do you have a nice, striking example where using your approach (using deepseq and comparing efficiency) you could make a difference, and where a tool as described above would make the analysis much easier? Thanks, Joachim -- Joachim Breitner e-Mail: m...@joachim-breitner.de Homepage: http://www.joachim-breitner.de Jabber-ID: nome...@joachim-breitner.de signature.asc Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
