#Feat — Functional Enumeration of Algebraic Types

Size notion. In this README "size" means whatever the Enumerable instance chooses — usually one pay per constructor, but a user-defined instance can charge differently. The driver only relies on: each part is finite, parts are ordered by increasing size, and recursion is productive (guaranteed by pay).

This package is a building block for MoonBit QuickCheck. It backs the "small check" mode (exhaustive testing for small sizes) and is independently useful whenever you want a deterministic, size-indexed view of a type.

#Why enumeration?

• Random is cheap, finds bugs lurking behind large inputs, but misses corner cases clustered near the "small" end of the space.
• Exhaustive catches every small-input bug but blows up combinatorially.

flowchart LR
  T["Type T"] --> E["Enumerate[T]<br/>LazyList of Finite[T]"]
  E --> P0["part₀ : Finite[T]<br/>(size-0 values)"]
  E --> P1["part₁ : Finite[T]<br/>(size-1 values)"]
  E --> P2["part₂ : Finite[T]<br/>(size-2 values)"]
  E --> Pdots["…"]
  P2 --> Card["fCard : BigInt<br/>(count)"]
  P2 --> Idx["fIndex : BigInt → T<br/>(selector)"]

#Install & Import

moon add moonbitlang/quickcheck

{
  "import": [
    { "path": "moonbitlang/quickcheck/feat", "alias": "feat" }
  ]
}

#The two core types

#Finite[T] — a random-access indexed chunk

///|
pub(all) struct Finite[T] {
  fCard : BigInt
  fIndex : (BigInt) -> T
}

///|
test "hand-rolled finite chunk" {
  let f : @feat.Finite[String] = {
    fCard: 2,
    fIndex: i => {
      if i == 0 {
        "left"
      } else {
        guard i == 1 else { abort("index out of bounds") }
        "right"
      }
    },
  }
  debug_inspect(
    f.to_array(),
    content=(
      #|(2, <List: ["left", "right"]>)
    ),
  )
}

///|
test "disjoint union of two singleton parts" {
  let left = @feat.singleton("left").eval().head()
  let right = @feat.singleton("right").eval().head()
  let joined = left + right
  debug_inspect(
    joined.to_array(),
    content=(
      #|(2, <List: ["left", "right"]>)
    ),
  )
}

///|
test "for x in finite" {
  let acc : Array[BigInt] = []
  let finite : @feat.Finite[BigInt] = { fCard: 4, fIndex: i => i }
  for x in finite {
    acc.push(x)
  }
  @debug.assert_eq(acc, [0, 1, 2, 3])
}

#Enumerate[T] — a lazy list of Finite[T]

///|
pub(all) struct Enumerate[T] {
  parts : LazyList[Finite[T]]
}

///|
test "singleton has size 0" {
  let e = @feat.singleton(42)
  let parts = e.eval()
  // The first (and only) part holds the single value.
  debug_inspect(
    parts.head().to_array(),
    content=(
      #|(1, <List: [42]>)
    ),
  )
}

///|
test "pay shifts everything one size up" {
  // Before pay: part₀ = {42}
  // After pay:  part₀ = {}, part₁ = {42}
  let shifted = @feat.pay(() => @feat.singleton(42))
  let parts = shifted.eval()
  debug_inspect(
    parts.head().to_array(),
    content=(
      #|(0, <List: []>)
    ),
  )
  debug_inspect(
    parts.tail().head().to_array(),
    content=(
      #|(1, <List: [42]>)
    ),
  )
}

#The Enumerable trait — deriving enumerations

This is the main user-facing trait of the package. Implement Enumerable for a type T and you get: indexed access (enumerate()[i]), size-bounded sampling via feat_random, and deterministic prefix testing via small_check. Everything else in this package either consumes or produces an Enumerable.

#Signature

///|
pub(open) trait Enumerable {
  enumerate() -> Enumerate[Self]
}

• pub(open) — anyone can add an instance for their own type.
• The method is nullary: the enumeration of T depends only on T, not on any runtime state.
• Return type Enumerate[Self] is the lazy list-of-parts value documented above — see Enumerate[T].

#The contract

#Built-in instances

#Implementing Enumerable for your own type

flowchart TD
  UserType["your recursive type T"] --> Constructors["one branch per constructor"]
  Constructors --> Leaf["Leaf constructor:<br/>singleton(value)"]
  Constructors --> Recursive["Recursive constructor:<br/>unary or product"]
  Leaf --> Union["+ (union)"]
  Recursive --> Union
  Union --> Pay["pay(() => …)"]
  Pay --> Result["Enumerate[T]"]

1. One + summand per constructor. Leaf constructors become singleton(...); constructors that carry children use unary(pair => Cons(pair.0, pair.1)) or product(...).
2. Wrap the whole thing in a pay(...). The pay is what gives the fixpoint a chance to suspend before recursing into T::enumerate() again — this is the productivity guarantee (contract item 2).
3. Reach child enumerations through Enumerable::enumerate(), not by re-constructing them. That way the compiler's inference picks up user-defined instances and built-ins uniformly.

///|
enum Tree {
  Leaf
  Node(Tree, Tree)
}

///|
impl @feat.Enumerable for Tree with enumerate() {
  // One size unit per constructor; the recursive children are reached via
  // `unary`, which goes through the built-in `Enumerable` instance for
  // `(Tree, Tree)`. That instance itself inserts a `pay`, which is what keeps
  // the fixpoint productive.
  @feat.pay(() => {
    @feat.singleton(Leaf) +
    @feat.unary((pair : (Tree, Tree)) => Node(pair.0, pair.1))
  })
}

///|
impl Show for Tree with output(self, logger) {
  match self {
    Leaf => logger.write_string("Leaf")
    Node(l, r) => {
      logger.write_string("Node(")
      l.output(logger)
      logger.write_string(", ")
      r.output(logger)
      logger.write_string(")")
    }
  }
}

///|
test "enumerate the first few binary trees" {
  let trees : @feat.Enumerate[Tree] = Enumerable::enumerate()
  inspect(trees[0], content="Leaf")
  inspect(trees[1], content="Node(Leaf, Leaf)")
}

#Common pitfalls

#Where the trait is consumed

• unary(f) requires the input type of f to be Enumerable.
• feat_random(size) takes T : Enumerable and turns it into a Gen[T] by drawing uniformly from parts 0..=size.
• small_check and its silent/error variants live in this package and use the same Enumerable ordering for deterministic prefix testing.

#Using an enumeration

#Indexing

///|
test "index into Bool's enumeration" {
  // Enumerable::enumerate() for Bool yields [true, false] (inside pay).
  let e : @feat.Enumerate[Bool] = Enumerable::enumerate()
  inspect(e[0], content="true")
  inspect(e[1], content="false")
}

///|
test "index into a list enumeration" {
  let e : @feat.Enumerate[@list.List[Bool]] = Enumerable::enumerate()
  // Sizes grow as more cons cells are added.
  debug_inspect(
    e[0],
    content=(
      #|<List: []>
    ),
  )
  debug_inspect(
    e[1],
    content=(
      #|<List: [true]>
    ),
  )
  debug_inspect(
    e[2],
    content=(
      #|<List: [false]>
    ),
  )
}

#Sampling the whole of size k

///|
test "materialize every Bool at size 1" {
  let parts = (Enumerable::enumerate() : @feat.Enumerate[Bool]).eval()
  // part 0 is empty (Bool is defined with a pay).
  debug_inspect(
    parts.head().to_array(),
    content=(
      #|(0, <List: []>)
    ),
  )
  // part 1 holds both booleans.
  debug_inspect(
    parts.tail().head().to_array(),
    content=(
      #|(2, <List: [true, false]>)
    ),
  )
}

#Mapping and combining

///|
test "fmap rewrites every element in place" {
  let bools : @feat.Enumerate[Bool] = Enumerable::enumerate()
  let labels = bools.fmap(b => if b { "yes" } else { "no" })
  assert_eq(labels[0], "yes")
  assert_eq(labels[1], "no")
}

///|
test "product generates every pair in part order" {
  let pairs = @feat.product(zero_or_one_part(), zero_or_one_part())
  debug_inspect(pairs[0], content="(0, 0)")
  debug_inspect(pairs[1], content="(0, 1)")
  debug_inspect(pairs[2], content="(1, 0)")
  debug_inspect(pairs[3], content="(1, 1)")
}

///|
fn zero_or_one_part() -> @feat.Enumerate[BigInt] {
  { parts: Cons({ fCard: 2, fIndex: i => i }, @lazy.LazyRef::from_value(Nil)) }
}

#When to reach for Feat vs. random QuickCheck

#API Reference (quick scan)

#Values

#Types

#Further reading

• Jonas Duregård, Patrik Jansson, Meng Wang. Feat: functional enumeration of algebraic types. Haskell Symposium, 2012.
• The MoonBit QuickCheck paper / README for the integration with random generation and shrinking.

#License