[Haskell-cafe] Some lambda identities

Yitzchak Gale gale at sefer.org
Tue Oct 9 06:34:44 EDT 2007

While playing with @pl on #haskell, I noticed some
weird and surprising lambda identities. For example:

let {c = (.); c4 = c c c c}
Then we have:
c c4 == c c4 c c c c

Proof: Repeatedly apply the identity:

(*) x (y z) == c x y z

More stuff:

c c2 == c4, c c3 == c7, but c cn does not appear
to be reducible for n>3.

c7 c3 == c3 c7 c c c

You get a lot more interesting stuff when you
throw flip into the mix.

The identity (*) is actually a semi-associativity
condition that makes the entire lambda calculus
into a semi-monoid. Apparently with very interesting

Anyone know more about these things?


More information about the Haskell-Cafe mailing list