Blog › ICP guides

Hope developer on retainer: algebraic data types, pattern matching, polymorphic type inference, higher-order functions, and Hope functional language engineering on monthly retainer

October 28, 2026 · ~17 min read

A Hope functional program querying a binary tree data structure was producing partial function errors for 3 query inputs per day. The system represented its data model using a Hope algebraic data type: data Tree alpha == leaf ++ node(Tree alpha, alpha, Tree alpha). A schema migration added a third constructor to represent pre-balanced subtrees: data Tree alpha == leaf ++ node(Tree alpha, alpha, Tree alpha) ++ balanced(Tree alpha, Tree alpha). The existing traverse function had pattern match arms for leaf and node but not for balanced. When query inputs constructed balanced nodes, Hope’s runtime raised a partial function error: no pattern in traverse matched the balanced constructor. The Hope developer on retainer diagnosed the root cause: the schema migration added a new constructor without auditing all pattern-matching functions over the Tree type for exhaustiveness. Hope does not emit a compile-time exhaustion warning for partial pattern matches — the failure occurs at runtime when the unmatched constructor is presented. The fix added the missing balanced pattern arm to traverse with the correct recursive traversal logic. Partial function errors: 3 per day → 0.

The work log entry read “fixed traversal error for balanced tree nodes, 16h.” It names the symptom and the duration. It cannot explain to a client why the fix required auditing every function that pattern matches over the Tree type (not just traverse — a schema migration may leave multiple functions with missing arms), why Hope’s design choice (partial function error at runtime, not compile-time exhaustion check) reflects the language’s historical context as a research language predating exhaustion analysis in functional language type checkers, why adding a wildcard _ catch-all arm would be incorrect (it would silently discard balanced nodes rather than traversing them), or what the correct traversal semantics for a balanced node are relative to the existing node semantics (the balanced constructor takes two subtrees without a key, so traversal must recurse into both subtrees without producing a key value at this node). The 16 hours of constructor enumeration audit (identifying all functions in the program that mention Tree alpha in their type signatures or pattern match on Tree alpha values), pattern match arm analysis (for each function, verifying that all constructors are covered and adding arms for balanced), correctness reasoning (determining what the correct semantics for each function should be on a balanced node), and regression testing (running the query suite against the updated functions) are not visible in the diff beyond the added pattern arms.

Hope’s algebraic data types, pattern matching, and the exhaustion audit

Hope was developed at Edinburgh University in the late 1970s and early 1980s by Rod Burstall, Dave MacQueen, and Don Sannella. It was one of the first languages to combine algebraic data types (structural sum types with named constructors), pattern matching over those types, and a Hindley-Milner-style polymorphic type inference system — the combination that defines the core design of Standard ML, Haskell, OCaml, and their descendants. Hope’s influence on the functional programming language family makes it a historically significant substrate for understanding the foundations of typed functional programming.

Algebraic data types in Hope are declared with the data keyword. data Tree alpha == leaf ++ node(Tree alpha, alpha, Tree alpha) defines a polymorphic binary tree type parameterized by a type variable alpha. leaf is a nullary constructor (takes no arguments). node(Tree alpha, alpha, Tree alpha) is a ternary constructor taking a left subtree, a key of type alpha, and a right subtree. The ++ operator separates constructors (Hope’s equivalent of | in Haskell or OCaml). Type synonyms: typesynonym Pair alpha beta == alpha # beta defines Pair alpha beta as an alias for the product type alpha # beta (a tuple). Product types use #: alpha # beta is the type of pairs (a, b) where a :: alpha and b :: beta. List types use brackets: [alpha] is the type of lists with elements of type alpha. The empty list is nil; the cons constructor is :: (read as “prepend”): x :: xs prepends x onto list xs.

Pattern matching in Hope uses equational function definitions. A function with multiple patterns is written as multiple equations: dec depth : Tree alpha -> num; declares the function type; --- depth(leaf) <= 0; gives the base case; --- depth(node(left, _, right)) <= 1 + max(depth(left), depth(right)); gives the recursive case. The dec keyword declares a function with its type signature. The --- prefix introduces each equation. The <= separates the pattern (left side) from the expression (right side). The wildcard _ matches any value without binding it. Nested patterns: --- first(node(leaf, x, _)) <= x matches a node whose left subtree is leaf and extracts the key. Pattern matching is exhaustive when every possible constructor combination is covered by some equation. When a function is called with a value that matches none of its patterns, Hope signals a partial function error at runtime. The exhaustion audit after a schema migration: enumerate every data type declaration that was modified (new constructors added); enumerate every dec that mentions that type in its signature; for each such function, verify that every constructor of the modified type has a matching pattern; add equations for any missing constructors.

Hope’s built-in polymorphic equality is a distinctive design feature. The expression a = b in Hope calls the built-in structural equality predicate, which compares values of any type structurally without requiring a user-defined Eq instance. This works for all algebraic data types: node(leaf, 1, leaf) = node(leaf, 1, leaf) returns true because both sides have the same structure. Hope’s equality is the same relation for all types, making it simple to compare tree values, list values, and nested structures without per-type boilerplate. This is in contrast to Haskell’s type-class-based equality (Eq) and OCaml’s polymorphic equality ((=)), both of which have semantic subtleties around function types and mutable references. Hope’s equality is total over its algebraic value universe.

Hope’s type inference, letrec, polymorphism, and higher-order functions

Hope’s type inference is based on the Hindley-Milner algorithm. Every expression in a well-typed Hope program has a principal type that can be inferred without type annotations; the inferred type is the most general (most polymorphic) type consistent with the expression’s use. Function declarations with dec provide type signatures that the type checker verifies against the inferred types. Hope’s type variables are conventionally named alpha, beta, gamma. A polymorphic function: dec identity : alpha -> alpha; --- identity(x) <= x; declares identity with polymorphic type alpha -> alpha. Calling identity(3) instantiates alpha to num; calling identity("hello") instantiates alpha to string. The same definition works for both without code duplication.

Mutual recursion in Hope uses letrec. When two or more functions are mutually recursive, they must be defined in a single letrec block so that Hope’s type inference can see all the definitions simultaneously and infer consistent types. A common retainer mistake: defining mutually recursive functions as separate top-level dec declarations or separate letrec bindings. If even calls odd and odd calls even, and they are defined in separate letrec blocks, Hope’s type checker may fail to resolve the forward reference in the first block because the second definition is not yet in scope. The fix: letrec even(n) == if n = 0 then true else odd(n-1) and odd(n) == if n = 0 then false else even(n-1). The and keyword in a letrec introduces a co-definition, making both names visible to both bodies simultaneously. Similarly, dec declarations for mutually recursive functions must appear before their first use in any expression, or be structured so that the top-level definitions are mutually visible.

Higher-order functions in Hope take other functions as arguments or return functions. The function type alpha -> beta is itself a type in Hope, and functions of this type can be passed as arguments. dec apply : (alpha -> beta) # alpha -> beta; --- apply(f, x) <= f(x); defines a higher-order apply function. Hope’s currying: functions in Hope take all their arguments at once (not automatically curried as in Haskell); partial application requires explicit lambda abstraction using lambda: lambda x . f(x, 3) creates a function that applies f with the fixed second argument 3. List operations in Hope: hd(xs) returns the head of list xs; tl(xs) returns the tail; nil is the empty list; x :: xs prepends x. Hope’s built-in list functions include append for list concatenation and length for list length. The map equivalent is written recursively: dec mymap : (alpha -> beta) # [alpha] -> [beta]; --- mymap(_, nil) <= nil; --- mymap(f, x :: xs) <= f(x) :: mymap(f, xs);.

Hope’s list comprehensions provide a concise syntax for list transformations with filtering. The general form is [expression : generator1, generator2, ..., guard1, guard2, ...]. A generator has the form x <- xs (draw values from list xs, binding each to x). A guard is a boolean expression that filters out drawn values. Example: [x * x : x <- numbers, x > 0] produces the squares of all positive numbers in numbers. Multiple generators: [(x, y) : x <- xs, y <- ys, x < y] produces all pairs from xs and ys where the first element is smaller. The guards in a list comprehension must be total functions: a guard that fails with a partial function error on some elements will abort the entire comprehension. The common retainer pattern: a guard predicate that calls a function with a pattern match over an algebraic type; if that function has a partial match (missing a constructor), queries that produce those constructors will fail. The fix: audit every function called in comprehension guards for pattern match exhaustiveness.

Hope’s I/O model uses dialogues: a Hope program that performs I/O is a function of type [Response] -> [Request] where Request and Response are algebraic types representing I/O actions and their results. This dialogue model (also called the stream-based I/O model) was influential in early functional I/O design and is a direct predecessor of the I/O approaches explored in Miranda and early Haskell before the introduction of monadic I/O. A Hope program defines a dec main : [Response] -> [Request] function that constructs a list of requests (ReadLine, WriteLine, etc.) based on the list of responses it has received. The Hope runtime evaluates the dialogue lazily, interleaving requests and responses.

How HourTab tracks Hope developer retainer hours

Hope retainer work shares the invisible-work problem with all algebraically-typed functional language retainers, with the additional challenge that Hope’s most common retainer tasks — exhaustive pattern match completion for new constructors after schema migration, letrec mutual recursion block restructuring for type inference, polymorphic type variable function signature design, list comprehension guard totality audit — produce diffs whose surface area is small relative to the analytical work required. Adding a balanced pattern arm to traverse is a diff with three lines; the value is correct traversal for all balanced nodes in all query inputs in perpetuity, with no partial function errors at runtime. The analytical work — identifying all other functions that also match over Tree alpha and verifying their exhaustiveness, reasoning about the correct semantics for balanced nodes in each function, and verifying that the new arms produce correct results by running the full query test suite — is the 16 hours that are not in the diff. Restructuring two separate letrec definitions of mutually recursive functions into a single letrec ... and ... block is a diff with two lines; the value is correct type inference for both functions’ mutual references, elimination of all type errors caused by the forward reference, and a program that compiles and runs correctly for all inputs. The analytical work — understanding which functions are mutually recursive, understanding why Hope’s type inference algorithm requires co-definitions to be in the same letrec block, and verifying that the restructured block infers the correct types — is the 10 hours not in the diff.

HourTab gives Hope developers a public retainer-hours URL they send to clients — typically programming language research groups using Hope for its historical role in the development of typed functional programming, institutions with legacy Hope codebases from the Edinburgh functional programming research period, and functional programming educators using Hope as a pedagogical vehicle for teaching algebraic data types and Hindley-Milner type inference — at the start of an engagement. For Hope retainers, each work log entry should name the mechanism (exhaustive pattern match audit for all functions using a data type after new constructor addition; pattern match arm addition for new constructor with correct traversal logic; letrec mutual recursion block restructuring with and co-definition for correct type inference; polymorphic type variable function signature design; list comprehension guard totality audit and pattern completion; typesynonym alias design; infix operator associativity and precedence declaration; Hope built-in polymorphic equality design for structural comparison; dialogue-based I/O model design for interactive programs), the specific data type and constructor name and the partial function failure, and the before/after observable metric. Hope retainers are often compared to Standard ML developer retainers for Hindley-Milner type system work (Hope and ML share the same type-theoretic foundation), to Haskell developer retainers for exhaustive pattern match and algebraic data type engineering (Haskell’s design directly inherits from Hope and Miranda), and to Scheme developer retainers for minimalist functional language platform work from the same research era. The distinction from Standard ML and Haskell is the partial function error behavior: both SML and GHC Haskell can emit compile-time warnings for non-exhaustive patterns, while Hope’s runtime-only detection makes the schema migration audit even more critical because no compiler catches missed constructor additions. HourTab’s work log makes the exhaustion audit and letrec restructuring visible to clients who would otherwise see only the symptom — partial function errors on specific query inputs — and not understand why the fix required auditing every function over the modified type rather than just the one that failed.

FAQ: Hope developer retainers