3 ms·
I'm confused by their "3 part linked list". I always thought the elegance of lambda calculus was that each data structure was equivalent to the method by which
by kazagistar 10y ago
I'm confused by their "3 part linked list". I always thought the elegance of lambda calculus was that each data structure was equivalent to the method by which you use it. A boolean is a function that does a conditional statement. A number is a function that does a loop. So logically, a list is a function that does a fold, like "LIST :: (a -> b -> a) -> a -> a".
- derkha 10y agoYes, that is a valid alternative encoding: https://en.wikipedia.org/wiki/Church_encoding#Represent_the_list_using_right_fold https://en.wikipedia.org/wiki/Church_encoding#Represent_the_... In general, what you describe is representing an inductive type by its _eliminator_: https://www.quora.com/In-type-theory-what-is-an-eliminator-and-what-is-its-opposite https://www.quora.com/In-type-theory-what-is-an-eliminator-a...
- twanvl 10y agoThere are many different ways to encode lists. You are using the Church encoding, where a value is a fold, nil = λn.λc.n cons = λx.λxs.λn.λc.c x (xs n c) fold = λf.λz.λxs.xs z f Another option is the Scott encoding, where a value is a case distinction nil = λn.λc.n cons = λx.λxs.λn.λc.c x xs fold = Y (λfold.λf.λz.λxs.xs z (λhead.λtail.f head (fold f z tail))) And then there is the 3-tuple thing proposed in the article.