[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
structure.
Anyone know more about these things?
Thanks,
Yitz
More information about the Haskell-Cafe
mailing list