[Haskell-cafe] Some lambda identities

0 views
Skip to first unread message

Yitzchak Gale

unread,
Oct 9, 2007, 6:35:45 AM10/9/07
to Haskell-cafe
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
_______________________________________________
Haskell-Cafe mailing list
Haskel...@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Yitzchak Gale

unread,
Oct 9, 2007, 7:27:53 AM10/9/07
to Haskell-cafe, apfe...@quantentunnel.de
I wrote:
> 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
> You get a lot more interesting stuff when you
> throw flip into the mix.
> Anyone know more about these things?

apfelmus pointed out that my "c" is the B
combinator:

http://en.wikipedia.org/wiki/Combinatory_logic#Combinators_B.2C_C

And flip is (essentially) the B combinator.

Any other references?

Yitzchak Gale

unread,
Oct 9, 2007, 7:49:38 AM10/9/07
to Haskell-cafe, apfe...@quantentunnel.de
I wrote:
> And flip is (essentially) the B combinator.

Oops, the C combinator.

-Yitz

Reply all
Reply to author
Forward
0 new messages