Skip to content

Instantly share code, notes, and snippets.

@VictorTaelin
Created November 18, 2025 18:21
Show Gist options
  • Select an option

  • Save VictorTaelin/188126ef0a50f514175ec234b75c52bd to your computer and use it in GitHub Desktop.

Select an option

Save VictorTaelin/188126ef0a50f514175ec234b75c52bd to your computer and use it in GitHub Desktop.
λ-calculus tuple rotl problem
Implement a λ-Term named `rotL` that, when applied to a function F, a Church Nat
N, and a Church N-Tuple, returns the same Church N-Tuple, but with elements
shifted left. In other words, create a generic 'rotL<N,F,t>' function for
N-tuples. Example:
- (rotL λf.λx.(f (f x)) λt.(t 1 2)) == λt.(t 2 1)
- (rotL λf.λx.(f (f (f x))) λt.(t 1 2 3)) == λt.(t 2 3 1)
Your final answer must be a λ-Term that implements `rotL` correctly, as follows:
@rotL = term_here
NOTE: Don't omit parenthesis. Each application requires them. Example:
- WRONG: λf. λx. f (f x)
- RIGHT: λf. λx. (f (f x))
- WRONG: (λx. f x) λx.x
- RIGHT: (λx.(f x) λx.x)
- WRONG: λf. λx. λy. (f x y)
- RIGHT: λf. λx. λy. ((f x) y)
ANSWER:
@marvinborner
Copy link

marvinborner commented Nov 18, 2025

Interesting. I would have assumed it to find the obvious solution for n-1

n=>t=>k=>t(x=>n(q=>r=>s=>q(r(s)))(u=>u(x))(k))

and adapt it such that it increments the Church n separately or sth
(which is basically what it does, now that I think about it)

Not sure it matters, but fyi such solutions are part of bruijn's standard library (e.g. here), so it might be baked into the model already

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