rosetta/variadic_fixed-point_combinator.bruijn

:import std/Combinator .
:import std/Number .
:import std/List .

# ---------------
# explicit Church
# ---------------

# passes all functions explicitly
explicit-y* [[[0 1] <$> 0] ([[1 <! ([[1 2 0]] <$> 0)]] <$> 0)]

# even x = if x == 0 then true else odd? (x-1)
g [[[=?0 [[1]] (1 --0)]]]

# odd x = if x == 0 then false else even? (x-1)
h [[[=?0 [[0]] (2 --0)]]]

# merged even/odd
rec explicit-y* (g : {}h)

:test (^rec (+5)) ([[0]])
:test (_rec (+5)) ([[1]])

# n % 3
mod3 ^(explicit-y* (zero : (one : {}two)))
	zero [[[[=?0 (+0) (2 --0)]]]]
	one [[[[=?0 (+1) (1 --0)]]]]
	two [[[[=?0 (+2) (3 --0)]]]]

:test ((mod3 (+5)) =? (+2)) ([[1]])

# ----------------
# explicit tupling
# ----------------

# passes all functions explicitly
# requires a tuple mapping function first
# or, minified: [[0 0] [[2 (1 1 0) 0]]] (38 bit!)
tupled-y* [y [[2 (1 0) 0]]]

# merged even odd
rec tupled-y* map [0 g h]
	map [&[[[0 (3 2) (3 1)]]]]

# [[1]] / [[0]] are tuple selectors:

:test (rec [[1]] (+5)) ([[0]])
:test (rec [[0]] (+5)) ([[1]])

# n % 3, [[[2]]] selects first tuple element
mod3 tupled-y* map [0 zero one two] [[[2]]]
	map [&[[[[0 (4 3) (4 2) (4 1)]]]]]
	zero [[[[=?0 (+0) (2 --0)]]]]
	one [[[[=?0 (+1) (1 --0)]]]]
	two [[[[=?0 (+2) (3 --0)]]]]

:test ((mod3 (+5)) =? (+2)) ([[1]])

# NOTE: You can merge the mapping argument directly into the list
#       like [[0 (1 A) (1 B) (1 C) ...]]. Then y*=y.

# ---------------
# implicit Church
# ---------------

# passes all functions in a single list
implicit-y* y [[&(1 0) <$> 0]]

# even x = if x == 0 then true else odd? (x-1)
g [[=?0 [[1]] (_1 --0)]]

# odd x = if x == 0 then false else even? (x-1)
h [[=?0 [[0]] (^1 --0)]]

# merged even/odd
rec implicit-y* (g : {}h)

:test (^rec (+5)) ([[0]])
:test (_rec (+5)) ([[1]])

# n % 3
mod3 ^(implicit-y* (zero : (one : {}two)))
	zero [[=?0 (+0) (_1 --0)]]
	one [[=?0 (+1) (^(~1) --0)]]
	two [[=?0 (+2) (^1 --0)]]

:test ((mod3 (+5)) =? (+2)) ([[1]])