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

[Nicola Gigante]

Hello everybody

I would kindly ask you to take a look at this code and tell me your opinions:

https://gist.github.com/nicola-gigante/43533ce907f88a6aba16 <https://gist.github.com/nicola-gigante/43533ce907f88a6aba16>

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.

I’ve tried to implement all the type classes that I currently use, and it seems to work.
Also, all the operations of those typeclasses seems to preserve the original laziness properties,
despite I was expecting the contrary. 

A list in this code is basically a function that’s constructed by composing a lot of partially applied cons operators.
To obtain a plain list from it, it’s sufficient to apply the empty list at the end. So I was expecting that
to evaluate even the first element of the list, the code would have to evaluate all the function composition chain
to obtain the entire function to being able to apply the final argument. It seems not true, since this code
can still manipulate infinite lists. For example:

> fmap (*2) . fromList $ repeat 42

This code prints an infinite stream of “84” numbers in GHCI. It doesn’t wait to have the entire list to then print it out.
In my understanding that means I’m building the list sufficiently lazily, or am I missing something?
In the case this actually means my datatype is lazy enough, why isn’t it more strict instead, following the above reasoning?
Is it the case that haskell laziness extends to partially constructed functions?

Also, the implementation is very simple. Basically I use the list functions and go back and forth with toList/fromList. 
It all seems too easy… am I wasting a lot of time or space somewhere?

Thank you a lot for your help,
Greetings,
Nicola
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20141118/82716207/attachment.html>