Notebooks 2.0 is here.
Published
Edited
Jan 10, 2020
// The recursive function used by REDUCE
make_reduc =
next_reduc =>
list =>
fn =>
acc =>
(new_acc =>
// Have we reached the end of the list?
lib.IS_LAST(list)
// Yup, so simply return the accumulator
(f => (new_acc)(f))
// Nope, so recursively call ourselves passing the
// remainder of the list, the reduction function and the
// new accumulator value
(f => (next_reduc(lib.TAIL(list))
(fn)
(new_acc))
(f)
)
)
// Calculate the new accumulator value. This value
// appears as parameter new_acc in the above function
(fn(lib.HEAD(list))(acc))
// Create the REDUCE function using the Y-Combinator
REDUCE = lib.Y(make_reduc)
// Define a function to count the number of items in a list
COUNT = list => REDUCE(list) // The list being reduced
(dont_care => acc => lib.SUCC(acc)) // The reduction function
(lib.ZERO) // The accumulator start value
// Create a list holding the first four positive integers
listOfInts = lib.array2list([1,2,3,4])
lib.to_integer(COUNT(listOfInts))
// Define a FACTORIAL function
FACTORIAL1 =
list =>
REDUCE(list) // The list being reduced
(val => acc => lib.MULTIPLY(val)(acc)) // The reduction function
(lib.ONE) // The starting value for the accumulator
lib.to_integer(FACTORIAL1(listOfInts))
// Convert a positive integer to its Church encoding
// Null must be explicitly tested for to avoid disappearing down the rabbit hole of infinite recursion.
// This is because JavaScript coerces null to be zero; therefore, the "(n-1)" part of the expression
// "next_qty_fn(lib.SUCC(qty_fn))(n-1)" will become 0-1 which then leads to infinite recursion.
// This behaviour does however result in mapping null to ZERO, which might produce misleading results...
do_qty_fn =
next_qty_fn =>
qty_fn =>
n => (n === 0 || n === null)
? qty_fn
: next_qty_fn(lib.SUCC(qty_fn))(n-1)
TO_CHURCH = lib.Y(do_qty_fn)(lib.ZERO)
// Define a FACTORIAL function
FACTORIAL =
list =>
REDUCE(list) // The list being reduced
(val => acc => lib.MULTIPLY(TO_CHURCH(val))(acc)) // The reduction function now using Church numerals
(lib.ONE) // The accumulator start value
lib.to_integer(FACTORIAL(listOfInts))
// Define a SUM function
SUM =
list =>
REDUCE(list) // The list being reduced
(val => acc => lib.ADD(TO_CHURCH(val))(acc)) // The reduction function now using Church numerals
(lib.ZERO) // The accumulator start value
lib.to_integer(SUM(listOfInts))
// Fold left is simply a synonym for REDUCE
FOLDL = REDUCE
// Fold right is simply a fold left on the reversed list
FOLDR = list => REDUCE(lib.REVERSE(list))
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
