Addendum: Pattern Variations
This page is dedicated to John Azariah, whose excellent blog posts mentioned below deeply inspired this work. Thank you, John, for sharing these ideas with the community!
The Free Monad and Tagless Final patterns originate in Haskell, where they can be expressed directly thanks to language features that F# and C# lack:
Type classes — the foundation of Tagless Final in Haskell (
class Monad m => MyDSL m where ...). F# and C# use interfaces as a substitute, but interfaces cannot abstract over type constructors.Higher-Kinded Types (HKTs) — Haskell can abstract over monadic contexts (
Monad m => m a), which is essential for both patterns. F#/C# generics are first-order: you can writeProgram<'a>but notProgram<M<'a>>whereMitself is a parameter.GADTs (Generalized Algebraic Data Types) — Haskell can give each constructor of a data type its own return type (
CheckStock :: [Item] -> OrderStep StockResult). F# discriminated unions share a single type parameter across all cases; C# approximates GADTs via record inheritance (record CheckStock(...) : OrderStep<StockResult>).
Without these building blocks, F# and C# must emulate these patterns rather than implement them directly — each emulation making its own trade-offs in type safety, verbosity, and flexibility. This page explores these variations along several design axes — instruction typing, parallelism, combinator placement, and the trade-off between generic (versatile, decoupled) and turnkey (integrated, opinionated) designs.
These variations are inspired by John Azariah's blog and the gitbook's own program V3bis experiment.
John Azariah's Resources
Series Tagless Final in F#
Series Intent vs Process — explores the same Intent-vs-Process separation through an Order Processing domain, comparing Free Monad and Tagless Final in C# and F#
Article Choosing Both Sides of the Coin — parallelism via
Bothin Free Monad (C#)Code repository: johnazariah.github.io/code/intent-vs-process — code in C#, F#, and Haskell
The Order Domain
John's core domain types are shared across all encodings — they belong to the domain, not the pattern:
type Item = { Sku: string; Name: string; Quantity: int }
// ...
type OrderRequest = { Items: Item list (*...*) ... }
[<Struct>] type StockResult = { IsAvailable: bool }
[<Struct>] type PriceResult = { Total: decimal; Subtotal: decimal; Discount: decimal }
// ...
type OrderResult =
| Success of transactionId: string
| Failure of reason: stringFree Monad Variations
John's Free Monad (F#)
John's Free Monad uses a flat discriminated union with no generic type parameter — each case holds only the instruction's input data:
The Program type uses obj boxing at the continuation boundary:
Two notable design choices:
Failed of string— the program handles failure directly with a string reason, making it independent of anyResulttype. Theguardfunction below leverages this to short-circuit the program on a boolean condition.Step of OrderStep * ...— the step case references the domain-specificOrderSteptype directly. This means theProgramtype is tied to the Order domain — to use it in another domain, you would need to duplicate or generalize it.
In comparison, the gitbook's V3bis addresses both points differently:
Failure handling: V3bis has no
Failedcase. Instead, it relies on theResulttype — the CE'sBindoverload forProgram<Result<_, _>>short-circuits onError, threading the error throughEnd(Error e). This makes failure handling type-safe and composable (error aggregation viaResult.zip, typed error lifting), but couples the program to theResultandErrortypes.Domain agnosticism: V3bis makes
Program<'a>domain-agnostic by using anIStepinterface instead of a concrete union type. A sub-interfaceIInterpretableStep<'union>then bridges back to the domain's instruction DU, restoring exhaustive pattern matching in the interpreter — at the cost of a type test (match step with :? IInterpretableStep<ProductInstruction> as s -> ...), which is less safe and less performant than a direct match on the DU.
Smart constructors—that I called Program helpers in the GitBook—restore type safety at the call site via unbox:
They are used in the placeOrder program—what is called domain workflow in the GitBook—making use of the program computation expression:
The key advantage: the flat DU makes structural analysis trivial. Each step can be pattern-matched without unwrapping generic interfaces:
John trades type safety at the continuation boundary (obj boxing/unboxing) for inspectability — the flat DU enables structural analysis that would be much harder with generic interfaces.
John's Free Monad (C#)
In C#, John uses a GADT-like pattern that F# discriminated unions cannot express: each step record carries its result type as a generic parameter:
Here, CheckStock is an OrderStep<StockResult> — the return type is encoded in the type itself. This is possible in C# because each step is a separate record inheriting from a generic base, whereas F# discriminated unions share a single type parameter across all cases (no GADTs).
The OrderProgram<T> type mirrors the F# version — Done, Failed, Bind — plus a Both<T> case for parallelism (added in his latest article):
John then provides LINQ extensions that make OrderProgram<T> composable using C#'s query syntax — the equivalent of F#'s computation expression:
The PlaceOrder program reads like a declarative workflow thanks to LINQ:
The interpreter then decides whether to run Both branches sequentially or concurrently — the program structure declares intent, the interpreter chooses strategy.
GitBook V3: Emulating Algebraic Effects
The gitbook's V3 was an attempt to emulate algebraic effects in F# using a free monad and interfaces. The core idea: effects are represented as a functor interface (IProgramEffect<'a>) that the Program type wraps recursively:
Each domain then defines its instructions following a 5-step recipe (see Algebraic Effects — V3 Design). The key building block is Instruction<'arg, 'ret, 'a> — a full typed class capturing the argument, the return type, and a continuation:
Here is John's Order domain adapted to the V3 pattern (showing only CheckStock and CalculatePrice for brevity):
The workflow can use the program computation expression:
GitBook V3bis
The V3bis is a hybrid that combines V3's typed instruction approach with John's obj-boxing flexibility, adding a Parallel case to the Program ADT. The full implementation is available on the program-v3 branch.
Program ADT
The Program<'a> type has three cases — including Parallel for applicative composition:
Like John's approach, the continuation in Step uses obj boxing. Unlike V3, there is no functor interface (IProgramEffect.Map) — this is what makes Parallel possible.
Fully Typed Instructions
Instructions carry both request and response types:
Unlike John's flat OrderStep DU (where the return type is only known at the smart constructor level), Instruction<'req, 'res> makes the response type explicit at the instruction definition. Compare:
Domain Instructions
Each domain defines its instruction set as a DU wrapping typed instructions:
Smart constructors use StepImplBuilder to lift instructions into programs:
Parallel Execution
The map2 combinator creates Parallel nodes by boxing both sub-programs:
This enables the let! ... and! ... syntax in the program CE — exactly like John's Both<T> in C#:
The interpreter transforms the program AST into an Async value, executing each step asynchronously. For the Parallel case, it launches both branches concurrently via Async.StartChild:
Structural Testing
Because the program is an AST, it can be introspected without execution — including parallel structure:
Usage in tests:
Free Monad Comparison
Instruction type
GADT-like OrderStep<T>
Flat DU (no 'a)
DU wrapping Instruction<'req, 'res>
Generic DU with typed continuations
Return type visible
On OrderStep<T> type
In smart constructors only
On instructions (Query<SKU, Prices>)
On Instruction<'arg, 'ret, 'a> type
Continuation
Func<object, OrderProgram<T>>
obj -> Program<'a>
obj -> Program<'a>
Typed: 'ret -> 'a
Structural analysis
Easy (flat records)
Easy (flat DU)
Easy (IStep.Name + Program.describe)
Hard (wrapped in IProgramEffect<'a>)
Parallelism
Both<T> record
Not implemented
Parallel case + map2
Blocked (functor Map requirement)
Functor (Map)
Not needed
Not needed
Not needed
Required on every effect class
Boilerplate
Low
Low
Medium (~20 lines for 7 instructions)
High (~45 lines for 5 instructions)
New domain cost
High (duplicate everything)
High (duplicate everything)
Low (domain-specific only)
Low (domain-specific only)
Notes
New domain cost: John's approaches tie Program<'a>, the CE/LINQ extensions, and the interpreter loop to the Order domain — adding a new domain means duplicating all of them. The gitbook's V3/V3bis make Program<'a>, the CE builder, and the interpreter loop domain-agnostic — only the instruction DU and smart constructors (+ effect classes for V3) are domain-specific.
Inspectability vs type safety: John trades type safety for inspectability. V3 trades inspectability for type safety. V3bis and John C# find middle grounds — V3bis recovers inspectability and parallelism by adopting obj boxing, while John C# uses GADT-like records to keep return types explicit.
Tagless Final Variations
John's Tagless Final (C#)
John's C# version uses an IOrderAlgebra<TResult> interface — the generic TResult parameter represents the output type of the algebra, not the output of individual instructions:
The same approach appears in John's F# Tagless Final series with FrogInterpreter<'a>.
This design opens many interpretation possibilities: TResult can be OrderResult (actual execution), string (narrative), AuditEntry list (dry-run), Task<OrderResult> (async execution), etc. However, instruction signatures like TResult CheckStock(List<Item> items) don't reveal the nominal return type of each instruction (e.g., StockResult). That information only appears at the call site, via alg.Then<StockResult>(...), which specifies what type to cast the result to in the continuation.
Gitbook V4
The gitbook's V4 restores the shared workflow by using an interface as the algebra:
Helpers/smart constructors via DefineProgram type alias that fixes the domain instructions type and enables IntelliSense:
The sequential workflow is identical to V3's CE syntax:
The V4 superpower — parallel execution via let! ... and! ...:
Tagless Final Comparison
Abstraction
FrogInterpreter<'a> record
IOrderAlgebra<TResult> interface
IOrderInstructions interface
Program type
FrogInterpreter<'a> -> 'a
OrderProgram<T> abstract record
'ins -> Async<'ret> (ReaderT)
Result type
Generic 'a
Generic TResult
Fixed: Async<'ret>
Return type visible
At interpreter instantiation
At call site (alg.Then<StockResult>)
On interface member
Composition
CE (frog { ... }) + product combinator
alg.Then<T> / LINQ query
CE (program { ... })
Multiple interpreters
One program, swap interpreter record
One program, swap IOrderAlgebra impl
One program, swap interface impl
Parallelism
Idem F#
Only after ToFreeMonad + interpretation
let! ... and! ... via map2
All three Tagless Final approaches share the workflow once — the key difference is how: John F# uses a generic record whose 'a parameter determines the interpretation mode (string, state, graph…); John C# uses an OO interface with a generic TResult; V4 uses an instruction interface with a fixed Async result type.
Cross-Cutting Analysis
Where Instruction Return Types Are Defined
A key design difference: where does the nominal return type of an instruction (e.g., StockResult for CheckStock) become visible?
Variant
Where 'res is defined
Example
John F# Free Monad
At smart constructor level
let checkStock items : Program<StockResult> = ...
John C# Free Monad
On step type (GADT-like)
record CheckStock(...) : OrderStep<StockResult>
Gitbook V2
In typed continuation
CheckStock of Item list * (StockResult -> 'a)
Gitbook V3
On instruction type
type GetPricesQuery<'a> = Query<SKU, Prices, 'a>
Gitbook V3bis
On instruction type
type GetPricesQuery = Query<SKU, Prices>
John Tagless Final
At use site in combinator
alg.Then<StockResult>(alg.CheckStock(items), ...)
Gitbook V4
On interface member
abstract member CheckStock: (Item list -> Async<StockResult>)
Combinators: Mixed vs Separated
John's IOrderAlgebra<TResult> mixes domain instructions (CheckStock, CalculatePrice) with combinators (Then, Done, Guard) in a single interface. This gives the algebra full control over composition — each interpreter can define its own sequencing semantics.
The gitbook's approach separates them: domain operations live in the instruction interface (IOrderInstructions), while combinators (bind, map, map2) live in the Program module and CE builder. This yields a reusable CE that works with any instruction set, but fixes the monadic structure.
Mixed (John)
Full control per interpreter; can optimize sequencing
Logic must be re-implemented per interpreter (F#); workflow shape coupled to algebra
Separated (Gitbook)
One CE for all domains; workflow syntax is fixed and predictable
Less flexible; monadic structure is fixed (always Async in V4, always free monad tree in V3/V3bis)
Parallelism Approaches
Three different approaches to expressing and executing parallel instructions:
John C# Both<T>
Free Monad (AST)
Parallel() creates Both nodes in the AST
Interpreter (sequential or concurrent)
V3bis Parallel
Free Monad (AST)
map2 creates Parallel nodes in the AST
Interpreter (Async.StartChild)
V4 map2
Tagless Final (function)
map2 directly starts child async
Built into the combinator
The Free Monad approaches (John C# and V3bis) encode parallelism as data — the AST declares the intent, and the interpreter chooses the strategy. The Tagless Final approach (V4) encodes parallelism as behavior — map2 directly calls Async.StartChild, so parallelism is baked into the combinator.
Turnkey vs Generic
The gitbook's implementations (V3, V3bis, V4) are turnkey: the Program type and CE are pre-wired with Result, Async, and the domain Error type. The CE automatically handles error short-circuiting (binding Result values), async threading, and error type lifting. This is convenient for the nominal use case — a domain workflow that performs async I/O and may fail — but it constrains the design. You cannot easily produce a string (narrative) or an AuditEntry list (dry-run) from the same workflow.
John's implementations are generic: the algebra and program types are independent of Result, Async, and any specific error type. IOrderAlgebra<TResult> can be instantiated with any TResult — making test, narrative, dry-run, and async interpreters all possible from the same workflow definition. The trade-off is more wiring for the nominal use case: the caller must handle async, errors, and composition explicitly.
Turnkey (Gitbook)
High — CE handles Result/Async/Error
Low — fixed to Async<Result<'ret, Error>>
Nominal execution + tests (mock interface)
Generic (John)
Lower — manual wiring
High — TResult can be anything
Nominal, narrative, dry-run, audit, structural analysis, ...
Choosing a Pattern: Tagless Final, Free Monad, or Both?
In his article Choosing Both Sides of the Coin, John suggests starting with Tagless Final. The pattern is simpler to adopt: programs are written against a familiar algebra (an interface in C#, a record in F#), composition uses standard language features (LINQ, CEs), and the approach fits naturally with dependency injection — idiomatic in OO languages like C#.
When inspectability becomes necessary — structural analysis, dry-run visualization, pre-execution optimization — the program can be converted to a Free Monad AST via a dedicated interpreter (ToFreeMonadInterpreter). This interpreter implements the algebra but, instead of executing operations, produces AST nodes. The resulting data structure can then be walked, analyzed, or optimized by a second-pass interpreter.
The key insight: you don't have to choose upfront. Start with the ergonomics of Tagless Final, and add the inspectability of a Free Monad only when and where you need it — as just another interpreter.
Conclusion
The fundamental trade-off: initial encoding (Free Monad) gives inspectability and pre-execution optimization; final encoding (Tagless Final) gives simplicity and ergonomics. Neither is universally superior.
V3bis demonstrates a middle ground for the Free Monad: by adopting obj boxing (from John's approach) and adding a Parallel case, it recovers both inspectability and parallel execution while keeping fully typed instructions — something that was impossible with V3's functor-based design.
The gitbook's V4 takes a turnkey Tagless Final path: a domain-agnostic Program type and CE, parameterized by an instruction interface, with built-in Result/Async handling and parallel execution via let! ... and! ... — optimized for the nominal use case at the cost of interpretation flexibility.
John's hybrid approach shows that this is not necessarily an either/or choice: write Tagless Final programs for ergonomics, then convert to a Free Monad AST when you need structural analysis. The design space is rich — each choice reflects a different balance of type safety, flexibility, simplicity, and inspectability.
Last updated