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

[Serge Le Huitouze]

> (...)
> 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


Regards.

--Serge