On 5 November 2010 06:40, Richard O'Keefe <o...@cs.otago.ac.nz> wrote: > > On 4/11/2010, at 10:56 PM, Claus Reinke wrote: >> Even in your SML code, the "boring old plain lists" seemed to be >> list_flatten, which uses difference lists in disguise, and won >> your little test, right? Using Haskell notation: >> >> flat (LEAF x) ys = x : ys >> flat (FORK(a,b)) ys = flat a (flat b ys) > > Measured time: > 0.902 seconds (2**22 leaves) > 2.716 seconds (2**23 leaves) >> --> >> flat (LEAF x) = \ys->x : ys >> flat (FORK(a,b)) = \ys->flat a (flat b ys) > > Measured time: > 0.980 seconds (2**22 leaves) > 7.999 seconds (2**23 leaves) >> --> >> flat (LEAF x) = (x :) >> flat (FORK(a,b)) = flat a . flat b > > Measured time: > 10.189 seconds (2**22 leaves) > 163.184 seconds (2**23 leaves) > > In all cases, the final result was a list, not a function. > I was actually expecting the first and second versions to > be the same code. > [SNIP]
Hello Richard I'm not entirely convinced that your experiment is a case against Hughes lists. The flattening of the bin-tree can use exactly _cons_ as it can go to right-bottom leaf and then work backwards with the accumulator cons-ing a single element at each step. I'd expect a plain list to be better for this as I expect a constructor to be more efficient than a function. Figuratively speaking, I'd contend that the bin-tree (aka a join-list) has already taken the weight of the concatenation. To show a Hughes list as efficient or inefficient a test would need to compare a plain list and a Hughes list doing the concatenation themselves - the common exemplar being string building vis the ShowS type. Best wishes Stephen _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe