Exploring Recursive Types in Go: Tries, Finite Automata, Stacks, Pointers, Balanced Braces, Y Combinator, and Church Numerals

Go's type system currently lacks generics but supports non‑pointer recursive type definitions, allowing a type T to refer to itself directly rather than using *T. This is similar to C++'s std::enable_shared_from_this.

With recursive type support we can write more interesting code, such as defining a trie using a map of Char to Trie instead of a struct.

Trie

A trie (prefix tree) is commonly implemented with a struct, but here we use a recursively defined map type to define Trie more conveniently.

type (
  Char = rune
  Trie map[Char]Trie
)

Using this Trie type we can add nodes and search using the map's [] operator.

Implementation:

func (t Trie) AddString(s string) {
  for _, ch := range []Char(s) {
    if t[ch] != nil {
      t = t[ch]
    } else {
      prevT := t
      t = make(Trie)
      prevT[ch] = t
    }
  }
}

func dfs(t Trie, prefix []Char, suggestions []string) []string {
  for ch, newT := range t {
    prefix := append(prefix, ch)
    if len(newT) == 0 {
      suggestions = append(suggestions, string(prefix))
    } else {
      suggestions = dfs(newT, prefix, suggestions)
    }
  }
  return suggestions
}

func (t Trie) Suggest(prefix string) []string {
  prefixBytes := []Char(prefix)
  for _, ch := range prefixBytes {
    t = t[ch]
  }
  return dfs(t, prefixBytes, nil)
}

Simple test:

func ExampleTrie() {
  t := make(Trie)
  for _, s := range []string{"abandon", "absorb", "academy", "accuse", "accumulate", "banana"} {
    t.AddString(s)
  }
  for _, prefix := range []string{"ab", "ac", "acc"} {
    fmt.Printf("%s: %v
", prefix, t.Suggest(prefix))
  }
}

Finite Automaton

Since we can implement a trie, by relaxing edge constraints we can turn the tree into a graph and represent a finite automaton. The implementation uses a map‑based state representation.

type (
  Char = rune
  State map[Char]State
)

State machine construction uses the map's [] operation for transitions, which is simpler than struct‑based approaches.

const EOS = Char(-1)

func NewFinalState() State {
  return State{EOS: nil}
}

func isFinalState(st State) bool {
  _, found := st[EOS]
  return found
}

func Match(s string, st State) bool {
  for _, ch := range []Char(s) {
    st = st[ch]
  }
  return isFinalState(st)
}

Example for the regular expression ((a|b)?c)* and its automaton diagram (image omitted).

Construction and verification:

func ExampleFiniteAutomata() {
  St1 := NewFinalState()
  St2 := make(State)

  St1['a'] = St2
  St1['b'] = St2
  St1['c'] = St1
  St2['c'] = St1

  for _, s := range []string{"acbc", "acbca"} {
    fmt.Println(Match(s, St1))
  }
}

Stack

Functional programming can implement a stack using closures: Push creates a new closure, and calling the closure returns the top element and the rest of the stack.

type (
  T     = int
  Stack func() (T, Stack)
)

Push implementation:

func Push(stk Stack, x T) Stack {
  return func() (T, Stack) {
    return x, stk
  }
}

IterateStack

allows traversing the immutable stack.

func IterateStack(stk Stack, visit func(T)) {
  rest := stk
  for rest != nil {
    var x T
    x, rest = rest()
    visit(x)
  }
}

func ExampleStack() {
  stk1 := Push(nil, 1)
  stk2 := Push(stk1, 2)
  stk3 := Push(stk2, 3)
  for i := 0; i < 2; i++ {
    // always prints: 3 2 1
    IterateStack(stk3, func(x T) { fmt.Print(x) })
  }
}

Pointer

Go allows defining a recursive pointer type where the type name and its pointer type refer to each other, enabling a pointer that is not nil without using new or unsafe.Pointer. type Pointer *Pointer Example assignment demonstrates that &p, p, *p, **p, ***p all refer to the same value.

var p *Pointer
p = (*Pointer)(&p)

Alternative form using a non‑pointer variable:

var p Pointer
p = &p

The compiler treats Pointer and *Pointer as the same underlying type, leading to specific embedding restrictions.

type InvalidStructDef struct {
  Pointer // compile error: embedded type cannot be a pointer
}

Balanced Braces

A “good bracket sequence” can be represented by a recursive slice type. type BalancedBraces []BalancedBraces Example literal: arr := BalancedBraces{{}, {{}, {}}, {}} Printing yields a nested slice representation such as [[] [[] []] []].

Y Combinator

The Y combinator enables recursion using only anonymous functions. Go's recursive types allow a direct definition of the combinator.

type (
  Fun     func(int) int
  Functor func(Functor) Fun
)

func Y(f func(Fun) Fun) Fun {
  return func(g Functor) Fun {
    return g(g)
  }(func(r Functor) Fun {
    return func(n int) int {
      return f(r(r))(n)
    }
  })
}

Example using factorial:

func ExampleY() {
  fact := Y(func(r Fun) Fun {
    return func(n int) int {
      if n == 0 {
        return 1
      }
      return n * r(n-1)
    }
  })
  fmt.Println(fact(5)) // Output: 120
}

Church Numerals

Church numerals encode natural numbers as higher‑order functions. The article shows zero, successor, addition, multiplication, exponentiation, and predecessor implementations using recursive types.

type (
  X   = int
  Fun func(X) X
  Nat func(Fun) Fun
)

func Identity(x X) X { return x }

func Zero(Fun) Fun { return Identity }

func Succ(n Nat) Nat {
  return func(f Fun) Fun {
    return func(x X) X { return f(n(f)(x)) }
  }
}

func Plus(n, m Nat) Nat {
  return func(f Fun) Fun {
    return func(x X) X { return m(f)(n(f)(x)) }
  }
}

func Mult(n, m Nat) Nat {
  return func(f Fun) Nat { return m(n(f)) }
}

func Exp(n, m Nat) Nat { return m(n) }

func Konst(x Nat) Nat { return func(Nat) Nat { return x } }

func Pred(n Nat) Nat {
  return func(f Fun) Fun {
    return func(x X) X {
      return n(func(g Nat) Nat {
        return func(h Nat) Nat { return Mult(g, h)(f) }
      })(Konst(x))(Identity)
    }
  }
}

func Lift(f func()) Nat {
  return func(x Nat) Nat { f(); return x }
}

func Repeat(n Nat, f func()) { n(Lift(f))(nil) }

Testing examples demonstrate the operations.

func ExampleChurchNumerals() {
  f := func(x X) X { return x + 1 }
  One := Succ(Zero)
  Two := Succ(One)
  Three := Succ(Two)
  fmt.Println(Plus(Two, Three)(f)(0)) // Output: 5
  fmt.Println(Mult(Three, Two)(f)(0)) // Output: 6
}

func ExampleChurchNumerals2() {
  f := func() { fmt.Println("f()") }
  One := Succ(Zero)
  Two := Succ(One)
  Three := Succ(Two)
  fmt.Println("===== Plus(2, 3) =====")
  Repeat(Plus(Two, Three), f) // prints 5 lines of f()
  fmt.Println("===== Mult(2, 3) =====")
  Repeat(Mult(Two, Three), f) // prints 6 lines of f()
  fmt.Println("===== Exp(2, 3) =====")
  Repeat(Exp(Two, Three), f) // prints 8 lines of f()
  fmt.Println("===== Pred(3) =====")
  Repeat(Pred(Three), f) // prints 2 lines of f()
}