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

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