Il giorno 18/nov/2014, alle ore 16:59, Serge Le Huitouze ha scritto:

...

(...) The file try to implement a list-like data type, based on function composition to achieve a constant-time appending operation (in contrast to linear (++)).

I’m sure this is something old. If you have material that covers an approach like this, please tell me.

There is this paper of ICLP 1991 (even though the implementation language is lambda-Prolog): "Naive Reverse can be Linear", by Brisset P. and Ridoux O. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.8975

Which itself, references this paper of 1986 Information Processing Letters (n° 22, pp. 141-144): "A novel representationof lists and its application to the function “reverse”", by Hugues R.J.M. http://www.cs.tufts.edu/~nr/cs257/archive/john-hughes/lists.pdf

Thank you Serge and Tom for your quick answers! I’m surely going to read those paper, and use Data.DList instead of my own implementation, to not reinvent the wheel. What about my doubts on why it works so lazily?

Regards.

—Serge

Greetings, Nicola

Il giorno 18/nov/2014, alle ore 17:37, Arie Peterson 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

On Tue, Nov 18, 2014 at 05:07:21PM +0100, Nicola Gigante wrote:

I’m surely going to read those paper, and use Data.DList instead of my own implementation, to not reinvent the wheel.

What about my doubts on why it works so lazily?

I don't know why you'd be doubtful about laziness. It seems perfectly lazy to me. I wrote the post a while ago on how DList works. Perhaps it will help you. http://h2.jaguarpaw.co.uk/posts/demystifying-dlist/ Tom