Skip to content

Instantly share code, notes, and snippets.

@i-am-tom
Created September 10, 2017 08:51
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save i-am-tom/3bccf255ce37dbba7d281ca98397035a to your computer and use it in GitHub Desktop.
Save i-am-tom/3bccf255ce37dbba7d281ca98397035a to your computer and use it in GitHub Desktop.
Lambda Calculus evaluation of `compose flip flip id`
((\f.\g.\x.f(gx))(\f.\x.\y.fyx)(\f.\x.\y.fyx))(\x.x)

Renaming things for clarity...

((\f.\g.\x.f(gx))(\f2.\x2.\y2.f2 y2 x2)(\f3.\x3.\y3.f3 y3 x3))(\x4.x4)

Substitute (\f2.\x2.\y2.f2 y2 x2) for f...

((\g.\x.(\f2.\x2.\y2.f2 y2 x2)(gx))(\f3.\x3.\y3.f3 y3 x3))(\x4.x4)

Substitute (\f3.\x3.\y3.f3 y3 x3) for g...

(\x.(\f2.\x2.\y2.f2 y2 x2)((\f3.\x3.\y3.f3 y3 x3)x))(\x4.x4)

Substitute (\x4.x4) for x...

(\f2.\x2.\y2.f2 y2 x2)((\f3. \x3. \y3.f3 y3 x3)(\x4.x4))

Substitute (\x4.x4) for f3...

(\f2.\x2.\y2.f2 y2 x2)(\x3.\y3.(\x4.x4) y3 x3)

Substitute (\x3.\y3.(\x4.x4) y3 x3) for f2...

\x2.\y2.(\x3.\y3.(\x4.x4) y3 x3) y2 x2

Substitute y3 for x4...

\x2.\y2.(\x3.\y3.y3 x3) y2 x2

Substitute y2 for x3...

\x2.\y2.(\y3.y3 y2) x2

Substitute x2 for y3...

\x2.\y2.x2 y2

Rename variables...

\f.\x.f x

It takes a function and an input, and applies the input to the function. Which is kinda what the function does anyway... In short, this takes a function and does absolutely nothing to it :D

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment