Search as an Abstraction: Higher-Order Functions in Action

Higher-order functions—functions that accept or return other functions—are a cornerstone of composable software design. They let you capture the essence of an algorithm while leaving the details open to injection. A particularly elegant demonstration comes from Peter Norvig's PAIP, which shows how different tree-search strategies can be built from a single, highly abstract core. Below is a Clojure reimplementation of that idea.

The key insight is that we never define a concrete tree structure. Instead, a tree is expressed through functions: a state (a node) and a successor function that maps a state to its children. This functional representation allows for lazy evaluation—an infinite tree can be reasoned about and searched without materializing it in memory.

For instance, an infinite binary tree can be represented by a successor function that returns 2N and 2N+1 for any given node N:

(defn binary-tree
  "A successors function representing a binary tree."
  [x]
  (list (* 2 x) (+ 1 (* 2 x))))

This function defines a state space that is conceptually infinite; we can ask for successors of any node, regardless of depth. Yet, no tree data structure exists in memory—only a rule for generating children on demand.

A Generic Search Core

The heart of the system is a single function, tree-search, which encapsulates the meaning of "search a tree" without knowing what the tree contains, its structure, or the order of traversal:

(defn tree-search
  "Finds a state that satisfies goal?-fn; Starts with states, and searches
  according to successors and combiner. If successful, returns the state;
  otherwise returns nil."
  [states goal?-fn successors combiner]
  (cond (empty? states) nil
        (goal?-fn (first states)) (first states)
        :else (tree-search (combiner (successors (first states))
                                     (rest states))
                           goal?-fn
                           successors
                           combiner)))

Its parameters are deliberately abstract:

  • states: a list of starting states, initially containing a single node, which grows as the search progresses.
  • goal?-fn: a predicate that identifies whether a given state is the target.
  • successors: a function that returns the children of a given state.
  • combiner: a function that merges the list of newly discovered successors with the list of states still waiting to be explored. This single parameter determines the entire search strategy.

By varying only combiner, we can define distinct traversal algorithms while keeping all other logic intact.

Breath-first search (BFS) is achieved by using a prepend combiner, which places new successors at the end of the queue of states to explore:

(defn breadth-first-search
  "Search old states first until goal is reached."
  [start goal?-fn successors]
  (tree-search (list start) goal?-fn successors prepend))

(defn prepend
  [x y]
  (concat y x))

This yields a classical layer-by-layer traversal. For example, searching for state 9 progresses through the queue as (1), (2 3), (3 4 5), (4 5 6 7), and so on, eventually finding the target at depth three.

paip.core=> (with-verbose (breadth-first-search 1 #(= % 9) binary-tree))
;; Search: (1)
;; Search: (2 3)
;; Search: (3 4 5)
;; Search: (4 5 6 7)
;; Search: (5 6 7 8 9)
;; Search: (6 7 8 9 10 11)
;; Search: (7 8 9 10 11 12 13)
;; Search: (8 9 10 11 12 13 14 15)
;; Search: (9 10 11 12 13 14 15 16 17)
9

Depth-first search (DFS), by contrast, uses concat as its combiner, placing the successors of the current state ahead of the remaining states:

(defn depth-first-search
  "Search new states first until goal is reached."
  [start goal?-fn successors]
  (tree-search (list start) goal?-fn successors concat))

Since DFS will descend infinitely on an unbounded tree, we typically need a finite tree for demonstration. A clever higher-order function generator, finite-binary-tree, creates a successor function that respects a maximum state value:

(defn finite-binary-tree
  "Returns a successor function that generates a binary tree with n nodes."
  [n]
  (fn [x]
    (filter #(<= % n) (binary-tree x))))

With this, searching for a nonexistent state in a bounded tree would correctly fail, while a state beyond the tree's depth is simply unreachable:

paip.core=> (breadth-first-search 1 #(= % 33) binary-tree)
33

paip.core=> (breadth-first-search 1 #(= % 33) (finite-binary-tree 15))
nil

The same infrastructure can be extended to more nuanced strategies. A best-first search sorts candidate states by a cost function, attempting the most promising ones first. Building this requires two helper generators: diff, which creates a distance function from a target, and sorter, which returns a combiner that concatenates then sorts states by cost:

(defn diff
  "Given n, returns a function that computes the distance of its argument from n."
  [n]
  (fn [x] (Math/abs (- x n))))

(defn sorter
  "Returns a combiner function that sorts according to cost-fn."
  [cost-fn]
  (fn [new old]
    (sort-by cost-fn (concat new old))))

(defn best-first-search
  "Search lowest cost states first until goal is reached."
  [start goal?-fn successors cost-fn]
  (tree-search (list start) goal?-fn successors (sorter cost-fn)))

Using a simple distance heuristic to find 9 works but explores some unnecessary states due to the heuristic's imperfection—a testament to the modularity, not the optimality, of the design.

A practical variant is beam search, which limits the exploration to a fixed-width window of promising states to manage very large spaces. Its combiner sorts the list by cost and truncates it to beam-width entries:

(defn beam-search
  "Search highest scoring states first until goal is reached, but never consider
  more than beam-width states at a time."
  [start goal?-fn successors cost-fn beam-width]
  (tree-search (list start) goal?-fn successors
               (fn [old new]
                 (let [sorted ((sorter cost-fn) old new)]
                   (take beam-width sorted)))))

Beam width is a tuning parameter: find the minimum width that still lets the search reach its goal.

The Essence of Strategy

The elegance here lies in how the difference between BFS and DFS reduces to a single choice—concat versus prepend—in the combiner step. Each search strategy is a thin wrapper over a common core, parameterized not by concrete data structures or loops, but by functions. This is the true power of higher-order abstractions: capturing the essential logic once, and letting callers inject all incidental details.