disco-0.1.0.0: example/catalan.disco

import list
import oeis

-- The type of binary tree shapes: empty tree, or a pair of subtrees.
type BT = Unit + BT*BT

-- Generate the list of all binary tree shapes of a given size.
treesOfSize : N -> List(BT)
treesOfSize(0)   = [left(■)]
treesOfSize(k+1) =
  [ right (l,r) | x <- [0 .. k], l <- treesOfSize(x), r <- treesOfSize(k .- x) ]

-- Compute first few Catalan numbers by brute force.
catalan1 : List(N)
catalan1 = each(\k. length(treesOfSize(k)), [0..4])

-- Extend the sequence via the OEIS.
catalan : List(N)
catalan = extendSequence(catalan1)