Skip to content

Instantly share code, notes, and snippets.

@namenu
Created September 6, 2018 17:14
Show Gist options
  • Save namenu/5b8c2d503ccf1a96ffbe5104c16be2d1 to your computer and use it in GitHub Desktop.
Save namenu/5b8c2d503ccf1a96ffbe5104c16be2d1 to your computer and use it in GitHub Desktop.
Reverse a linked list
// Q. Reverse a linked list.
// What is linked list?
const cons = h => t => f => f(h)(t)
// What is boolean?
const T = a => b => a
const F = a => b => b
// What is integer?
const N0 = f => a
const N1 = f => a => f(a)
const N2 = f => a => f(f(a))
const N3 = f => a => f(f(f(a)))
// Define a list of `1 -> 2 -> 3`.
const NIL = cons(F)(F)
const ISNIL = p => p(T)(T(F))(T)
const x = cons(N1)(cons(N2)(cons(N3)(NIL)))
// Print it.
const print = l =>
ISNIL(l)
(() => {
console.log("@");
})
(() => {
console.log(l(T))
print(l(F));
})
() // for lazy eval
print(x)
// Reverse it.
const rev = l => r =>
ISNIL(l)
(() => r)
(() => rev(l(F))(cons(l(T))(r)))
() // <- for lazy eval
print(rev(x)(NIL))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment