Skip to content

Instantly share code, notes, and snippets.

@cdparks

cdparks/church.js

Created Jan 23, 2018
Embed
What would you like to do?
Church Encoded List in Flow
/* @flow */
export type ChurchT<A> = <R>(cons: (a: A, r: R) => R, nil: () => R) => R
function fromArray<A>(array: Array<A>): ChurchT<A> {
return function<R>(cons: (a: A, r: R) => R, nil: () => R): R {
let result = nil()
for (let i = array.length - 1; i >= 0; --i) {
result = cons(array[i], result)
}
return result
}
}
function toArray<A>(f: ChurchT<A>): Array<A> {
return f((x, xs) => [x, ...xs], () => [])
}
function foldr<A, B>(f: (a: A, b: B) => B, z: B, as: ChurchT<A>): B {
return as(f, () => z)
}
function cons<A>(a: A, as: ChurchT<A>): ChurchT<A> {
return function<R>(cons: (a: A, r: R) => R, nil: () => R): R {
return cons(a, as(cons, nil))
}
}
function nil<A>(): ChurchT<A> {
return function<R>(_cons: (a: A, r: R) => R, nil: () => R): R {
return nil()
}
}
function map<A, B>(f: (a: A) => B, as: ChurchT<A>): ChurchT<B> {
return foldr((x, xs) => cons(f(x), xs), nil(), as)
}
export default {
fromArray,
toArray,
foldr,
cons,
nil,
map
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.