[Haskell-cafe] Code review: list-like datatype with constant time appending based on function composition.

[Nicola Gigante]

Il giorno 18/nov/2014, alle ore 17:37, Arie Peterson <ariep at xs4all.nl> ha scritto:

>> What about my doubts on why it works so lazily?
> 
> Suppose 'f' is the function '(1 :)', and 'g' is some other unspecified other 
> function of type '[Integer] -> [Integer]' ("difference list").
> 
> You may evaluate the concatenation '(f . g) []' like this:
> 
> (f . g) []
>  = f (g [])
>  = 1 : g []
> 
> and at this point, you already have partial knowledge of the resulting list.
> 
> Note that we use "lazy evaluation", in the sense that we do not evaluate the 
> argument 'g []' to the function 'f' right away, but proceed by first 
> substituting the definition of 'f’.

Thanks, that makes sense, but it still seem to me that it depends on the order
of application of the composition operator. For example, what if the structure 
has been constructed by a left fold, so I have:

((((((f . g) . h) …..)

In this case, the evaluation have to descend ’n’ thunks to find the first function to
apply, so I can’t handle infinite lists. On the other hand, I can’t handle such an infinite
list from a left fold anyway, so maybe that’s the point?

Speaking about this “difference list” more generally, which are the negative sides
of using such a data structure?
For example, when should I use Data.Sequence, for example, that requires
Ord on my data types, while DList offers more or less the same features (or
am I missing something?) Performance?

Thank you very much,
Nicola