News for hackers. Stuff that matters.
Re:Rich Hickey – Inside Transducers [video] by cousin_it on Friday November 21, 2014 @09:33AM (#8641409)
Yeah. That's actually how you implement lists in lambda calculus, as opaque functions that accept a "visitor". There are two different ways of doing it:

    -- Mogensen-Scott encoding
    data ScottList a = ScottList (forall r. (a -> ScottList a -> r) -> r -> r)

    -- Boehm-Berarducci encoding
    data ChurchList a = ChurchList (forall r. (a -> r -> r) -> r -> r)
Roughly, the first encoding gives you pattern matching, and the second gives you foldr (reduce). Either of these operations is sufficient to do anything with the list.

Also note that both of these are encodings of lazy (potentially infinite) lists. To encode strict (guaranteed finite) lists, you really need algebraic data types like in ML, the visitor pattern can't do that.

There are no comments on this comment yet.