3 ms·
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: --
by cousin_it 12y ago
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.