Monad

Overview

Suppose a user ID leads to a user, then to their team, and finally to the team manager's email address. The user or team might be missing, and the email might not be registered, so each lookup returns an Option<T> that distinguishes a present value, Some, from an absent one, None.

Using the functor operation Map creates a problem here. FindTeam already returns Option<Team>, so applying Map(FindTeam) to Option<User> wraps that result again as Option<Option<Team>>; every additional step adds another layer that the caller has to unpack.

A monad puts this connection in bind. When a value is present, bind passes it to the next function and uses the Option that function returns directly; when it is absent, the function is not called. A monad combines bind with return, also called unit, which places a value in a context, and three laws governing those operations. A context carries something about the computation along with its value: possible absence, failure, multiple results, or asynchronous completion.

The name varies by language: Haskell uses >>=, JavaScript arrays and Scala use flatMap, and C# LINQ uses SelectMany. The custom Option<T> below calls its method Bind.

Flow

Loading animated diagram...

Map wraps the function's result again, whereas Bind passes that Option through, keeping one layer as the chain grows. If a step produces None, the remaining functions are not called.

History

In his 1991 paper "Notions of computation and monads," Eugenio Moggi distinguished the object A of values from the object TA of computations, calling the type constructor T a notion of computation. His examples cover partiality, nondeterminism, side effects, exceptions, continuations, and interactive input/output. The paper develops semantics and logic for proving program equivalence.¹

Philip Wadler brought the same technique to the structure of functional programs. His invited POPL 1992 paper "The essence of functional programming" adds error messages, state, output, and nondeterministic choice to a small interpreter using monads. "Monads for functional programming," first written for the 1992 Marktoberdorf summer school, sets out left identity, right identity, and associativity, explains how join flattens two layers of computation into one, and shows that lists form a monad. A revised version appeared in Advanced Functional Programming, LNCS 925, in 1995.²³

Haskell 1.3, published in May 1996, made the Monad class with >>=, >>, and return a central part of the language and standardized both do notation for monadic sequencing and monadic I/O.⁴⁵

Why use it?

Bind holds the rule "stop when the value is absent" in one place. Each step describes what to do with a present value, leaving the caller with fewer repeated if checks between steps.

This connection also appears outside Option. SelectMany on IEnumerable<T> joins the sequences produced for each element, while bind on a result type stops at the first error; what counts as a value to pass on depends on the context, but the shape of the connection is the same.

The three laws let us regroup a chain without changing its meaning. Left identity says that Unit(a).Bind(f) equals f(a); right identity says that m.Bind(Unit) equals m; associativity says that m.Bind(f).Bind(g) equals m.Bind(x => f(x).Bind(g)). Associativity lets us extract part of the chain into a separate function without changing the result. The C# compiler does not check these laws, so a custom type needs tests for them.⁶

C# query syntax supports this pattern directly. The specification translates query expressions into calls named Select and SelectMany before type binding and overload resolution, and those calls may target either instance methods or extension methods. A query with a second from clause becomes SelectMany(x1 => e2, (x1, x2) => v). Defining Select and SelectMany on our Option<T> therefore makes from ... from ... select available to it.⁷

Option records absence but discards its reason, so the design still has to decide which failures to distinguish and what to tell the caller. Use a result type carrying an error value when the reason matters.

Combining different monads takes more work in C#. To connect Task<Option<T>> values, for example, we need await for one layer and Bind for the other. Haskell stacks contexts with monad transformers, but C# generics cannot take a type constructor such as Option<> or Task<> itself as a type parameter, preventing a single Bind interface for all monads. C# query expressions likewise follow a pattern of method names and signatures rather than an interface.

async/await resembles bind in continuing with the previous operation's result once it is ready. In the C# specification, however, await follows the awaiter pattern defined by GetAwaiter, IsCompleted, and GetResult, rather than translating to SelectMany. The standard Task<T> has neither Select nor SelectMany, so from x in task select x produces compiler error CS1936.⁸

Example

Connect ParseInt, which parses a string as an integer, to Half, which halves even numbers only. Both can fail and return Option<int>. C# has no standard Option type, so the example defines Some and None as records and distinguishes them with switch-expression pattern matching; record value equality also lets us use == when checking the laws.

using System;
using System.Linq;

// Parse an integer, returning Option because parsing can fail.
static Option<int> ParseInt(string s) =>
    int.TryParse(s, out var n) ? new Some<int>(n) : new None<int>();

// Halve even numbers only. This step can fail too.
static Option<int> Half(int n) =>
    n % 2 == 0 ? new Some<int>(n / 2) : new None<int>();

// Place a value in the context: return, also called unit.
static Option<int> Unit(int n) => new Some<int>(n);

Option<Option<int>> nested = ParseInt("8").Map(Half);
Console.WriteLine($"Map:  {nested}");
Console.WriteLine($"Bind: {ParseInt("8").Bind(Half)}");
Console.WriteLine($"Bind: {ParseInt("7").Bind(Half)}");
Console.WriteLine($"Bind: {ParseInt("x").Bind(Half)}");

// Check the three laws on sample values, rather than proving them.
int[] values = [8, 7];
Option<int>[] ms = [ParseInt("8"), ParseInt("6"), ParseInt("x")];
Console.WriteLine("left identity:  " + values.All(a => Unit(a).Bind(Half) == Half(a)));
Console.WriteLine("right identity: " + ms.All(m => m.Bind(Unit) == m));
Console.WriteLine("associativity:  " + ms.All(m =>
    m.Bind(Half).Bind(Half) == m.Bind(x => Half(x).Bind(Half))));

abstract record Option<T>;
sealed record Some<T>(T Value) : Option<T>
{
    public override string ToString() => $"Some({Value})";
}
sealed record None<T> : Option<T>
{
    public override string ToString() => "None";
}

static class OptionExtensions
{
    // Map applies f to a present value and wraps the result in Some.
    public static Option<U> Map<T, U>(this Option<T> option, Func<T, U> f) => option switch
    {
        Some<T>(var value) => new Some<U>(f(value)),
        _ => new None<U>(),
    };

    // Bind passes a present value to f and uses its returned Option directly.
    public static Option<U> Bind<T, U>(this Option<T> option, Func<T, Option<U>> f) => option switch
    {
        Some<T>(var value) => f(value),
        _ => new None<U>(),
    };
}

Text

Map:  Some(Some(4))
Bind: Some(4)
Bind: None
Bind: None
left identity:  True
right identity: True
associativity:  True

Map produces two layers, as in Some(Some(4)). For "7", Bind returns the None produced by Half; for "x", it returns None without calling Half.

A broader example

The lookup chain from the overview is written three ways: nested if statements, direct Bind calls, and LINQ query syntax. The query version uses Select and the two-argument SelectMany extension on Option<T>. User 1 succeeds throughout, user 2 has no team, user 3 has no manager email, and user 99 does not exist. The final query applies the same syntax to IEnumerable<T>, where list bind joins all the combinations.

using System;
using System.Collections.Generic;
using System.Linq;

var users = new Dictionary<int, User>
{
    [1] = new("Alice", "core"),
    [2] = new("Bob", null),
    [3] = new("Dave", "ops"),
};
var teams = new Dictionary<string, Team>
{
    ["core"] = new("Core", "carol"),
    ["ops"] = new("Ops", "erin"),
};
// erin has no registered email address.
var emails = new Dictionary<string, string> { ["carol"] = "carol@example.com" };

Option<User> FindUser(int id) =>
    users.TryGetValue(id, out var user) ? new Some<User>(user) : new None<User>();
Option<Team> FindTeam(User user) =>
    user.TeamId is string teamId && teams.TryGetValue(teamId, out var team)
        ? new Some<Team>(team) : new None<Team>();
Option<string> FindEmail(Team team) =>
    emails.TryGetValue(team.ManagerId, out var email) ? new Some<string>(email) : new None<string>();

// 1. Nested if statements add another indentation level for each lookup.
Option<string> WithIfs(int id)
{
    if (users.TryGetValue(id, out var user))
    {
        if (user.TeamId is string teamId && teams.TryGetValue(teamId, out var team))
        {
            if (emails.TryGetValue(team.ManagerId, out var email))
            {
                return new Some<string>($"{user.Name} -> {email}");
            }
        }
    }
    return new None<string>();
}

// 2. Direct Bind calls nest lambdas to keep user available at the end.
Option<string> WithBind(int id) =>
    FindUser(id).Bind(user =>
        FindTeam(user).Bind(team =>
            FindEmail(team).Map(email => $"{user.Name} -> {email}")));

// 3. The compiler translates the query from clauses into SelectMany calls.
Option<string> WithQuery(int id) =>
    from user in FindUser(id)
    from team in FindTeam(user)
    from email in FindEmail(team)
    select $"{user.Name} -> {email}";

foreach (var id in new[] { 1, 2, 3, 99 })
{
    var a = WithIfs(id);
    var b = WithBind(id);
    var c = WithQuery(id);
    Console.WriteLine($"id {id}: {c}, all three equal: {a == b && b == c}");
}

// SelectMany on IEnumerable<T> uses the same syntax, joining the sequences from each element.
var pairs =
    from team in new[] { "Core", "Ops" }
    from role in new[] { "dev", "qa" }
    select $"{team}/{role}";
Console.WriteLine(string.Join(", ", pairs));

record User(string Name, string? TeamId);
record Team(string Name, string ManagerId);

abstract record Option<T>;
sealed record Some<T>(T Value) : Option<T>
{
    public override string ToString() => $"Some({Value})";
}
sealed record None<T> : Option<T>
{
    public override string ToString() => "None";
}

static class OptionExtensions
{
    public static Option<U> Map<T, U>(this Option<T> option, Func<T, U> f) => option switch
    {
        Some<T>(var value) => new Some<U>(f(value)),
        _ => new None<U>(),
    };

    public static Option<U> Bind<T, U>(this Option<T> option, Func<T, Option<U>> f) => option switch
    {
        Some<T>(var value) => f(value),
        _ => new None<U>(),
    };

    // A single from ... select query is translated to this Select method.
    public static Option<U> Select<T, U>(this Option<T> option, Func<T, U> f) => option.Map(f);

    // A second from clause uses this overload: Bind, then apply the result selector.
    public static Option<V> SelectMany<T, U, V>(
        this Option<T> option, Func<T, Option<U>> f, Func<T, U, V> resultSelector) =>
        option.Bind(t => f(t).Map(u => resultSelector(t, u)));
}

Text

id 1: Some(Alice -> carol@example.com), all three equal: True
id 2: None, all three equal: True
id 3: None, all three equal: True
id 99: None, all three equal: True
Core/dev, Core/qa, Ops/dev, Ops/qa

All three versions return the same values, but users 2, 3, and 99 all appear as None, hiding which lookup stopped and why. Keeping the reason requires a context such as a result type and a decision about which failures to distinguish. Direct Bind calls nest lambdas so that the first user remains available at the end. Query syntax carries earlier range variables through the intermediate steps where they are needed, which the specification describes with transparent identifiers. Anonymous objects are a common implementation, but the specification permits other mechanisms, so this does not imply one object allocation at every stage. These are synchronous lookups in in-memory dictionaries; the example does not combine them with asynchronous queries.

TypeScript example

TypeScript uses a union distinguished by kind for Option and defines bind explicitly. Without C# query syntax, callbacks nest when an earlier value is needed at the end, while the standard array flatMap makes the difference from map visible directly.

TypeScript

type Option<T> = { kind: "some"; value: T } | { kind: "none" };
const some = <T>(value: T): Option<T> => ({ kind: "some", value });
const none: Option<never> = { kind: "none" };
const show = <T>(o: Option<T>): string => (o.kind === "some" ? `Some(${o.value})` : "None");

// Pass a present value to f and use its returned Option directly.
function bind<T, U>(o: Option<T>, f: (value: T) => Option<U>): Option<U> {
  return o.kind === "some" ? f(o.value) : none;
}

type User = { name: string; teamId: string | null };
type Team = { name: string; managerId: string };
const users = new Map<number, User>([
  [1, { name: "Alice", teamId: "core" }],
  [2, { name: "Bob", teamId: null }],
  [3, { name: "Dave", teamId: "ops" }],
]);
const teams = new Map<string, Team>([
  ["core", { name: "Core", managerId: "carol" }],
  ["ops", { name: "Ops", managerId: "erin" }],
]);
// erin has no registered email address.
const emails = new Map<string, string>([["carol", "carol@example.com"]]);

const fromMap = <K, V>(map: Map<K, V>, key: K): Option<V> =>
  map.has(key) ? some(map.get(key) as V) : none;
const findUser = (id: number): Option<User> => fromMap(users, id);
const findTeam = (user: User): Option<Team> =>
  user.teamId === null ? none : fromMap(teams, user.teamId);
const findEmail = (team: Team): Option<string> => fromMap(emails, team.managerId);

for (const id of [1, 2, 3, 99]) {
  const result = bind(findUser(id), (user) =>
    bind(findTeam(user), (team) =>
      bind(findEmail(team), (email) => some(`${user.name} -> ${email}`))));
  console.log(`id ${id}: ${show(result)}`);
}

// For arrays, map nests the results; flatMap joins them into one layer.
const nested = ["Core", "Ops"].map((team) => ["dev", "qa"].map((role) => `${team}/${role}`));
const flat = ["Core", "Ops"].flatMap((team) => ["dev", "qa"].map((role) => `${team}/${role}`));
console.log(JSON.stringify(nested));
console.log(JSON.stringify(flat));

Text

id 1: Some(Alice -> carol@example.com)
id 2: None
id 3: None
id 99: None
[["Core/dev","Core/qa"],["Ops/dev","Ops/qa"]]
["Core/dev","Core/qa","Ops/dev","Ops/qa"]

map creates arrays within an array, while flatMap joins them into one layer. The Option bind reports users 2, 3, and 99 as the same None, just as the C# example does.

Footnotes

Moggi, Eugenio. "Notions of computation and monads". Information and Computation 93(1): 55-92 (1991). Example 1.1. ↩
Wadler, Philip. "The essence of functional programming". POPL '92, pp. 1-14 (1992). Wadler monads page. ↩
Wadler, Philip. "Monads for functional programming". Advanced Functional Programming, LNCS 925, pp. 24-52 (1995). Revised version of the 1992 Marktoberdorf summer-school notes. §3 Monad laws; §5.1 Lists. Author's copy. ↩
Changes from Haskell 1.2 to Haskell 1.3. Monads, Monadic I/O, do expressions. ↩
The Haskell definition. "The Haskell version 1.3 report from May 1996". ↩
base 4.22.0.0, Control.Monad, class Monad. Left identity, Right identity, Associativity. ↩
C# language specification. §12.23.3 Query expression translation, §12.23.3.5, §12.23.4 The query-expression pattern. ↩
C# language specification. §12.9.9 Await expressions, §12.9.9.2 Awaitable expressions. ↩

→ 현재 버전 보기

Monad

Overview

Flow

History

Why use it?

Example

A broader example

TypeScript example

See also

Footnotes