On 5 November 2010 06:40, Richard O'Keefe
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