Type-level branches: a dependent-if deep read
Gabriella Gonzalez’s September 2 Haskell essay shows how Church-encoded booleans, RebindableSyntax, and ordinary type inference can preserve different result types through one conditional.
Gabriella Gonzalez published "Dependent if expressions without dependent types" on September 2, 2026. The post takes a familiar Haskell restriction—both branches of an ordinary
if must return the same type—and turns it into a small lesson in information flow: encode booleans as functions, let RebindableSyntax redirect if to a local function, and let Hindley-Milner inference record which branch type reaches the result. 1The final trick
Gonzalez builds toward this example:
{-# LANGUAGE RebindableSyntax #-}
example bool = if bool then 5 else "hi!"The expression returns an
Int when bool is true and a String when bool is false. A conventional Haskell if expression uses one result type for both branches, so the compiler tries to make 5 and "hi!" share a type. The numeric literal then produces an error because the compiler is trying to treat a String as a numeric type. 1The source changes the meaning of the syntax before it changes the types. GHC's
RebindableSyntax extension makes a conditional mean ifThenElse condition thenBranch elseBranch, using whichever ifThenElse is in scope. The extension also implies NoImplicitPrelude, and GHC warns that the feature has fewer checks than ordinary syntax. 2That gives the program a function-shaped escape hatch:
ifThenElse condition thenBranch elseBranch =
condition thenBranch elseBranchThe remaining question is what
condition should be. Gonzalez answers that question with Church encoding.Church encoding makes a boolean choose
A Church encoding represents a data structure through the operations that consume it. Gonzalez uses the compact form below for booleans:
type Bool = forall a. a -> a -> a
true thenBranch elseBranch = thenBranch
false thenBranch elseBranch = elseBranchThe encoded
true receives two branches and returns the first. The encoded false receives the same two branches and returns the second. The boolean has become a pre-formed conditional: the function already knows which branch to select, while the caller supplies the branch values. 1The first version still has an ordinary limitation. The
a in type Bool = forall a. a -> a -> a forces both branches and the result to share one type. A function such as this one works:ifThenElse :: Bool -> a -> a -> a
ifThenElse condition thenBranch elseBranch =
condition thenBranch elseBranchThe condition can choose between two strings or two integers. The condition cannot choose an integer on one path and a string on the other because the type variable
a represents one type for all three positions. 1RebindableSyntax connects this function to familiar Haskell spelling. With the extension enabled, the compiler treatsif condition then thenBranch else elseBranchas a call to the
ifThenElse that the module provides. The syntax still looks like an if; its type-checking and execution follow the replacement function. 2Inference carries the branch type
The surprising step is deleting the type declarations and signatures from the Church-encoded version. The definitions remain small:
true thenBranch elseBranch = thenBranch
false thenBranch elseBranch = elseBranch
ifThenElse condition thenBranch elseBranch =
condition thenBranch elseBranchWith no restrictive signatures, GHC infers these types:
true :: thenBranch -> elseBranch -> thenBranch
false :: thenBranch -> elseBranch -> elseBranchThe two arguments may now have different types. The result type follows the argument selected by the boolean. Gonzalez names the generalized shape like this:
type Bool thenBranch elseBranch result =
thenBranch -> elseBranch -> result
ifThenElse
:: Bool thenBranch elseBranch result
-> thenBranch
-> elseBranch
-> resultThe
result parameter records the information that an ordinary Bool hides. A true value has the shape Bool thenBranch elseBranch thenBranch; a false value has the shape Bool thenBranch elseBranch elseBranch. Applying ifThenElse to true unifies the result with the thenBranch type. Applying it to false unifies the result with the elseBranch type. 1
The mechanism resembles a small dependent function. In a dependently typed notation, the intended type might look like this:
example :: (bool :: Bool) -> if bool then Int else StringThe encoding takes a different route. The boolean carries three type parameters: the type offered by the first branch, the type offered by the second branch, and the type that emerges after selection. The compiler refines the third parameter through ordinary unification. The program gets dependent-looking behavior from how types flow through functions, rather than from a dependent type language feature. 1
The
example function can therefore keep the two result types separate:example :: Bool Int String result -> result
example bool = if bool then 5 else "hi!"Calling
example true gives the inferred type Int. Calling example false gives the inferred type String. The implementation still has the surface shape of an ordinary conditional because RebindableSyntax directs the syntax to the generalized ifThenElse function. 1The operators preserve information flow
The same type parameters make the boolean operators describe what they do. Negation swaps the two branch types while leaving the result type alone:
not
:: Bool thenBranch elseBranch result
-> Bool elseBranch thenBranch result
not bool thenBranch elseBranch =
bool elseBranch thenBranchThe implementation swaps the two arguments. The type signature records that swap. A caller can see the operation's effect on the type-level flow without reading the function body. 1
Conjunction and disjunction use an intermediate result. For conjunction, the first boolean decides whether the program continues to the second boolean or takes the
else branch immediately:(&&)
:: Bool intermediateResult elseBranch result
-> Bool thenBranch elseBranch intermediateResult
-> Bool thenBranch elseBranch resultThe
intermediateResult variable connects the result of the second boolean to the branch consumed by the first boolean. Disjunction has the same structure with the first boolean's thenBranch on the early path:(||)
:: Bool thenBranch intermediateResult result
-> Bool thenBranch elseBranch intermediateResult
-> Bool thenBranch elseBranch resultThese signatures are more difficult to read than the implementations. That cost buys a precise account of how each branch's type moves through the composition. The source refactors the definitions so each local variable corresponds directly to one type variable:
thenBranch, elseBranch, or intermediateResult. 1Refinement has a boundary
The encoding keeps its precision when the program knows which encoded boolean it has. A container introduces a different constraint. A Haskell list needs one element type for every element, so a list containing both
true and false loses the distinction between their selected branches:bools :: [Bool result result result]
bools = [true, false]The list can work with a function that returns the same type from either branch. The following call is valid because
toString returns String for both cases:toString :: Bool String String result -> result
toString bool = if bool then "true" else "false"
map toString [true, false]The
example function has different branch types, so the same list cannot satisfy its input type:map example [true, false]The compiler sees one list element that produces
Int and another that produces String. A homogeneous list has no single result type to use for both calls. The refinement therefore degrades to Bool result result result, and a consumer must return one common type. 1This boundary keeps the idea honest. The encoding carries compile-time information when the program's control value is represented by a specific function. A collection of alternatives with different result types needs another design, such as a sum type or a common existential wrapper. The source demonstrates the first design rather than claiming that ordinary Hindley-Milner inference has become full dependent typing.
Assertions from the same pattern
Gonzalez extends the type flow into a small assertion mechanism. The assertion function accepts a condition whose false branch has a special
AssertionFailed type:data AssertionFailed = AssertionFailed
type family Successful result :: Constraint where
Successful AssertionFailed =
Unsatisfiable (\"Assertion failed\")
Successful _ = ()
assert
:: Successful result
=> Bool result AssertionFailed result
-> result
-> resultA statically known
true condition produces a normal result and satisfies Successful. A statically known false condition produces AssertionFailed, which the type family turns into a compiler error. The runtime implementation can remain a simple conditional; the type-level result makes the known failure visible while the program is being checked. 1The assertion example needs more language machinery than the dependent
if: DataKinds, TypeFamilies, and the type-error facilities from GHC.TypeLits. The extra extensions matter because the program is asking the compiler to turn a type-level result into a diagnostic. The core trick remains the same: a function's result type records which branch information reaches the end. 1What the trick gives you
The source's result is a compact technique for library and API design. A function can accept a value that carries evidence about how it selects its branches, and the result type can preserve that evidence. The technique gives the compiler something to check and gives the reader a type-level description of information flow.
The technique also comes with a clear cost.
RebindableSyntax changes several built-in forms and replaces the ordinary Prelude bindings with whatever names are in scope. GHC describes the extension as experimental and recommends Core Lint when a program relies on the desugared result. A local module that uses the trick therefore takes responsibility for its custom syntax and its altered assumptions about literals, conditionals, and imports. 2Gonzalez's article earns its title through the distinction between the surface behavior and the mechanism underneath. The program returns branch-dependent types. Its type system remains ordinary Hindley-Milner inference plus a few type-level parameters. The result is a useful piece of functional-programming craft: a representation can expose information that the built-in data type would have erased.
Verbatim quotes
"Church encoding" is a technique for encoding data structures and operations on those data structures using pure functions and nothing else.— Gabriella Gonzalez, "Dependent if expressions without dependent types".
The reason this all works is because our newBooltype tracks information flow at the type-level.— Gabriella Gonzalez, "Dependent if expressions without dependent types".
This is all possible with ≈20 lines of ordinary functional code making use of vanilla type system features.— Gabriella Gonzalez, "Dependent if expressions without dependent types".
References
- 1Dependent if expressions without dependent types
haskellforall.com
- 2Rebindable syntax and the implicit Prelude import
ghc.gitlab.haskell.org
This story was produced automatically by a channel. One sentence is all it takes for Neodrop to keep producing for you.