tur/fix
Fix type: the fixed-point of a functor, with cata and ana.
Fix f is the least fixed point of f. Provides catamorphism (cata) and anamorphism (ana) for structured recursion.
Since: Phase B1
Fix
(defdata Fix [^f] (Roll :int))
the fixed-point type of a functor.
Fix f is the least fixed point of the functor f, i.e. Fix f ~= f (Fix f). The single constructor Roll wraps one layer of f.
roll
(roll [layer :int] :int)
wrap one layer of f into a Fix value.
| layer | a value of type (f (Fix f)) |
A Fix value wrapping layer.
(roll my-layer) ; => (Roll my-layer)
Since: Phase RF2
unroll
(unroll [fix :int] :int)
unwrap one layer of Fix to expose the inner functor value.
| fix | a Fix value |
The inner f (Fix f) value.
(unroll (roll x)) ; => x
Since: Phase RF2
cata
(cata [alg :fn fix :int] :int)
catamorphism: fold a Fix value using an F-algebra.
A catamorphism (or "fold") collapses a Fix-encoded recursive structure by applying an algebra function alg at each layer.
| alg | a typed fat-closure (function from (f a) to a) stored as :fn | |
| fix | a Fix value to fold |
The result of applying alg to the unwrapped layer.
(cata my-alg leaf-fix)
Updated: fn-first-class-application -- a :fn value is now directly callable, so the algebra is applied with plain (alg ...) instead of the hand-rolled fat-pointer extraction in inline-C.
Since: Phase RF2
ana
(ana [coalg :fn seed :int] :int)
anamorphism: unfold a seed value into a Fix value using a co-algebra.
| coalg | a typed fat-closure (function from a to (f a)) stored as :fn | |
| seed | the initial seed value |
A Fix value built by applying coalg to seed.
(ana my-coalg seed-value)
Updated: fn-first-class-application -- a :fn value is now directly callable, so the co-algebra is applied with plain (coalg ...) instead of the hand-rolled fat-pointer extraction in inline-C.
Since: Phase RF2