[Haskell-cafe] Reference for technique wanted

[Stephen Tetley]

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