lists in Lambda in JavaScript
Dec. 31st, 2023 07:11 pm(disclaimer: this is educational material)
// Definitions for Boolean Logic
const True = x => y => x
const False = x => y => y
const Bool = b => b ? True : False
// Definitions for pair and projection
const p1 = x => y => x // did you notice? It's True
const p2 = x => y => y // did you notice? It's False
const Pair = x => y => f => f(x)(y)
// Option constructors
const None = Pair(True)("None")
const Some = x => Pair(False)(x)
// List constructors and operations
const Nil = Pair(True)("Nil")
const isEmpty = x => x(p1)
const Head = z => z(p2)(p1)
const HeadOption = z => z(p1)(None)(Some(z(p2)(p1)))
const Tail = z => z(p2)(p2)
const Cons = h => t => Pair(False)(Pair(h)(t))
const Map = z => f => (isEmpty(z) (() => Nil) (() => Cons(f(Head(z))) (Map(Tail(z))(f))))()
// visualizer
const show = text => xs => {
var buf = ""
Map(xs)(x => buf += (x + ":"))
println(`${text} ${buf}Nil`)
}
const Filter = z => p =>
(isEmpty(z)
(() => Nil)
(() => (p(Head(z)) (Cons(Head(z))(Filter(Tail(z))(p))) (Filter(Tail(z))(p))))
)() // have to do it lazily
// samples
const ab = Cons("a")(Cons("b")(Nil))
show("Expecting Nil ->")(Nil)
show("Expecting a:b:Nil ->")(ab)
const list1 = Cons(1)(Cons(-2)(Cons(3)(Cons(-4)(Nil))))
show("three numbers")(list1)
const isPositive = x => Bool(x > 0)
show("squares")(Map(list1)(x => x*x))
show("positives")(Filter(list1)(isPositive))
