Church' List constructors (was: "Green Card" ...)

[Koen Claessen]

Marcin 'Qrczak' Kowalczyk wrote:

 | newtype List a = List (forall b. b -> (a -> List a -> b) -> b)
 | 
 | nil          = List (\fornil forcons -> fornil)
 | cons    x xs = List (\fornil forcons -> forcons x xs)
 | forlist      fornil forcons (List ls) = ls fornil forcons
 :
 | In ghc algebraic types are really implemented in a similar way :-)

Well, not really. This implementation does not give you
sharing between lists. Everytime you use "forlist", the list
is reevaluated. In GHC, this does not happen of course.

Regards,
Koen.

--
Koen Claessen         http://www.cs.chalmers.se/~koen     
phone:+46-31-772 5424      mailto:koen@cs.chalmers.se
-----------------------------------------------------
Chalmers University of Technology, Gothenburg, Sweden