Question

It's possible to encode various types in the untyped lambda calculus through higher order functions.

Examples:
zero  = λfx.      x
one   = λfx.     fx
two   = λfx.   f(fx)
three = λfx. f(f(fx))
etc

true  = λtf. t
false = λtf. f

tuple = λxyb. b x y
null  = λp. p (λxy. false)

I was wondering if any research has gone into embedding other less conventional types. It would be brilliant if there is some theorem which asserts that any type can be embedded. Maybe there are restrictions, for example only types of kind * can be embedded.

If it is indeed possible to represent less conventional types, it would be awesome to see an example. I'm particularly keen on seeing what the members of the monad type class look like.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top