sml-recscheme

Recursion schemes — catamorphisms, anamorphisms, paramorphisms and hylomorphisms — over the fixpoint of a functor, in pure Standard ML.

No dependencies, no FFI, no threads, no clock, no randomness: the same inputs always produce the same outputs under MLton and Poly/ML.

Recursion schemes without higher-kinded types

In Haskell, cata :: Functor f => (f a -> a) -> Fix f -> a quantifies over an arbitrary functor f and folds a single generic Fix f. Standard ML has no higher-kinded types, so we cannot abstract over f directly. Two layers recover the same power:

1. A generic engine, written once. cata/ana/para/hylo are parameterised by the functor's out/inn projection and its fmap, which are passed in explicitly — the Functor/Fix dictionary supplied by hand:

   fun cata out fmap alg = let fun c m = alg (fmap c (out m)) in c end
   fun ana  inn fmap coalg = let fun a s = inn (fmap a (coalg s)) in a end
   fun para out fmap alg = let fun p m = alg (fmap (fn t => (t, p t)) (out m)) in p end
   fun hylo fmap alg coalg = let fun h s = alg (fmap h (coalg s)) in h end

2. Concrete instances that bake in a base functor and its fixpoint mu, giving the schemes clean fully-applied types. Two are provided to show the pattern generalises:

   • ListR — the list functor datatype 'a base = NilF | ConsF of int * 'a
   • TreeR — a binary-tree functor LeafF of int | BranchF of 'a * 'a

hylo is cata after ana fused: it never materialises the intermediate structure (factorial/sumRange below build no list/tree at all).

API

structure Recscheme : sig
  (* generic engine: functor dictionary (out/inn, fmap) passed explicitly *)
  val cata : ('s -> 'fs) -> (('s -> 'a) -> 'fs -> 'fa) -> ('fa -> 'a) -> 's -> 'a
  val ana  : ('fs -> 's) -> (('b -> 's) -> 'fb -> 'fs) -> ('b -> 'fb) -> 'b -> 's
  val para : ('s -> 'fs) -> (('s -> 's * 'a) -> 'fs -> 'fsa) -> ('fsa -> 'a) -> 's -> 'a
  val hylo : (('b -> 'c) -> 'fb -> 'fc) -> ('fc -> 'c) -> ('b -> 'fb) -> 'b -> 'c

  structure ListR : sig
    datatype 'a base = NilF | ConsF of int * 'a
    type mu
    val inn  : mu base -> mu
    val out  : mu -> mu base
    val fmap : ('a -> 'b) -> 'a base -> 'b base
    val cata : ('a base -> 'a) -> mu -> 'a
    val ana  : ('a -> 'a base) -> 'a -> mu
    val para : ((mu * 'a) base -> 'a) -> mu -> 'a
    val hylo : ('a base -> 'a) -> ('b -> 'b base) -> 'b -> 'a
    val fromList : int list -> mu     val toList : mu -> int list
    val range : int -> mu
    val sum : mu -> int   val product : mu -> int   val length : mu -> int
    val tails : mu -> int list list   (* para *)
    val factorial : int -> int        (* hylo *)
  end

  structure TreeR : sig
    datatype 'a base = LeafF of int | BranchF of 'a * 'a
    type mu
    val inn  : mu base -> mu
    val out  : mu -> mu base
    val fmap : ('a -> 'b) -> 'a base -> 'b base
    val cata : ('a base -> 'a) -> mu -> 'a
    val ana  : ('a -> 'a base) -> 'a -> mu
    val para : ((mu * 'a) base -> 'a) -> mu -> 'a
    val hylo : ('a base -> 'a) -> ('b -> 'b base) -> 'b -> 'a
    val leaf : int -> mu   val branch : mu * mu -> mu
    val fromRange : int * int -> mu   val toList : mu -> int list
    val sum : mu -> int   val product : mu -> int
    val depth : mu -> int   val leaves : mu -> int
    val sumRange : int * int -> int   (* hylo *)
  end
end

Example

structure L = Recscheme.ListR
structure T = Recscheme.TreeR

val 55  = L.sum (L.range 10)              (* cata over [1..10] *)
val 120 = L.product (L.range 5)
val xs  = L.tails (L.fromList [1,2,3])    (* para -> [[1,2,3],[2,3],[3],[]] *)
val 720 = L.factorial 6                   (* hylo: builds no intermediate list *)

val 36  = T.sum (T.fromRange (1, 8))      (* ana a balanced tree, then cata *)
val 5050 = T.sumRange (1, 100)            (* hylo: builds no intermediate tree *)

(* the generic engine, dictionary passed by hand *)
val gsum = Recscheme.cata L.out L.fmap (fn L.NilF => 0 | L.ConsF (x,a) => x + a)

Running examples/demo.sml with make example prints:

List functor (NilF | ConsF of int * 'a):
  range 10            = [1,2,3,4,5,6,7,8,9,10]
  cata sum            = 55
  cata product [1..5] = 120
  para tails [1,2,3]  = [[1,2,3],[2,3],[3],[]]
  hylo factorial 6    = 720 (no intermediate list)

Binary-tree functor (LeafF of int | BranchF of 'a * 'a):
  fromRange(1,8) leaves = [1,2,3,4,5,6,7,8]
  cata sum              = 36
  cata depth            = 4
  cata leaf count       = 8
  hylo sumRange(1,100)  = 5050 (no intermediate tree)

Build & test

Requires MLton and/or Poly/ML.

make test        # build + run the suite under MLton
make test-poly   # run the suite under Poly/ML
make all-tests   # both
make example     # build + run the demo
make clean

Installing with smlpkg

smlpkg add github.com/sjqtentacles/sml-recscheme
smlpkg sync

Reference lib/github.com/sjqtentacles/sml-recscheme/recscheme.mlb from your own .mlb (MLton / MLKit), or feed sources.mlb to tools/polybuild (Poly/ML).

Layout

sml.pkg                                         smlpkg manifest
Makefile                                        MLton + Poly/ML targets
.github/workflows/ci.yml                        CI: MLton + Poly/ML
lib/github.com/sjqtentacles/sml-recscheme/
  recscheme.sig   RECSCHEME signature
  recscheme.sml   generic engine + ListR / TreeR instances
  sources.mlb     ordered source list
  recscheme.mlb   public basis
examples/
  demo.sml        list- and tree-functor walkthrough
test/
  harness.sml     shared assertion harness
  test.sml        cata/ana/para/hylo vectors (47 checks)
  entry.sml / main.sml
tools/polybuild   Poly/ML build wrapper

Tests

47 deterministic checks: cata sum/product/length over [1..10], ana range with ana-then-cata round-trips, para computing tails, and hylo computing factorial/sumRange cross-checked against direct recursion (and confirmed to allocate no intermediate structure); the same schemes over a binary-tree functor; plus the generic engine driven directly with each functor's out/inn/fmap. Run make all-tests to verify identical output under both compilers.

License

MIT. See LICENSE.