MonadPlus

 __  __  ___  _   _    _    ____  ____    ____  _    _   _ ____
|  \/  |/ _ \| \ | |  / \  |  _ \/ ___|  |  _ \| |  | | | / ___|
| |\/| | | | |  \| | / _ \ | | | \___ \  | |_) | |  | | | \___ \
| |  | | |_| | |\  |/ ___ \| |_| |___) | |  __/| |__| |_| |___) |
|_|  |_|\___/|_| \_/_/   \_\____/|____/  |_|   |_____\___/|____/

Alternative^[1] gives applicative functors a way to express choice and failure with empty and <|>. MonadPlus^[2] carries that same idea into monadic computations, where later steps may depend on earlier results.

MonadPlus is where parsing truly shines. Consider a complex parser that needs to handle multiple syntax variants, backtrack on failure, or implement lookahead: Alternative handles the choice between alternatives, but MonadPlus adds the ability to sequence those choices with early termination when parsing fails.

Think of MonadPlus as Alternative with dependency. Where Alternative can choose between independent computations, MonadPlus can chain dependent computations together while preserving the ability to fail gracefully and try alternatives.

MonadPlus Formal Definition #

MonadPlus combines the structure of a monad with the choice operations of Alternative:

class (Monad m, Alternative m) => MonadPlus m where
  mzero :: m a              -- Identity element (same as empty)
  mplus :: m a -> m a -> m a -- Associative operation (same as <|>)

Laws:

Monoid Laws (inherited from Alternative):

• Left Identity: mzero `mplus` m = m
• Right Identity: m `mplus` mzero = m
• Associativity: (l `mplus` m) `mplus` r = l `mplus` (m `mplus` r)

Monad Laws (inherited from Monad):

• Left Identity: return a >>= f = f a
• Right Identity: m >>= return = m
• Associativity: (m >>= f) >>= g = m >>= (\x -> f x >>= g)

Common MonadPlus laws (interaction between monad and choice):

• Left Zero: mzero >>= f = mzero
• Left Distribution: (m `mplus` n) >>= f = (m >>= f) `mplus` (n >>= f)

Some instances also satisfy a right-zero law, m >> mzero = mzero, but this law is not valid for every useful MonadPlus-like structure. The key insight is that mzero acts as a left absorbing element for monadic bind (>>=), meaning that a computation that is already failed will short-circuit and propagate the failure.

From a category theory viewpoint, MonadPlus adds monoid-like choice to monadic computations. This gives us:

MonadPlus Structure:
┌─────────────────┐
│   m a >>= f     │  ─┐
│  (sequencing)   │   │
└─────────────────┘   │
                      ├──> MonadPlus Laws
┌─────────────────┐   │
│   m `mplus` n   │   │
│   (choice)      │  ─┘
└─────────────────┘

Natural Transformation Properties:

The MonadPlus choice operation is natural in the result type and preserves the intended choice semantics:

Haskell

-- Naturality of mplus
fmap f (m `mplus` n) = fmap f m `mplus` fmap f n

-- Monad-Choice interaction
(m `mplus` n) >>= f = (m >>= f) `mplus` (n >>= f)

This naturality ensures that MonadPlus provides a principled way to combine monadic computations with choice, enabling complex patterns like parser combinators, search algorithms, and error recovery mechanisms.

MonadPlus Examples #

A parser with backtracking, showing how MonadPlus enables different parsing strategies with automatic failure handling and choice between different parsing approaches.

{-# LANGUAGE OverloadedStrings #-}
import Control.Monad
import Control.Applicative
import Data.Char (isDigit, isAlpha, isSpace)

-- Parser with MonadPlus
newtype Parser a = Parser (String -> [(a, String)])

runParser :: Parser a -> String -> [(a, String)]
runParser (Parser p) = p

instance Functor Parser where
  fmap f (Parser p) = Parser $ \input ->
    [(f a, rest) | (a, rest) <- p input]

instance Applicative Parser where
  pure a = Parser $ \input -> [(a, input)]
  Parser pf <*> Parser pa = Parser $ \input ->
    [(f a, rest2) | (f, rest1) <- pf input, (a, rest2) <- pa rest1]

instance Alternative Parser where
  empty = Parser $ \_ -> []
  Parser p1 <|> Parser p2 = Parser $ \input ->
    case p1 input of
      [] -> p2 input      -- Only try second if first fails completely
      result -> result    -- Use first parser's result if it succeeds

instance Monad Parser where
  Parser p >>= f = Parser $ \input ->
    [(b, rest2) | (a, rest1) <- p input, (b, rest2) <- runParser (f a) rest1]

instance MonadPlus Parser where
  mzero = empty
  mplus = (<|>)

-- Basic parsers
satisfy :: (Char -> Bool) -> Parser Char
satisfy predicate = Parser $ \input ->
  case input of
    (x:xs) | predicate x -> [(x, xs)]
    _ -> []

char :: Char -> Parser Char
char c = satisfy (== c)

string :: String -> Parser String
string [] = return []
string (c:cs) = do
  _ <- char c
  _ <- string cs
  return (c:cs)

-- Whitespace handling
spaces :: Parser ()
spaces = void $ many $ satisfy isSpace

lexeme :: Parser a -> Parser a
lexeme p = do
  result <- p
  spaces
  return result

-- Number parsing with different formats
decimal :: Parser Int
decimal = read <$> some (satisfy isDigit)

hexadecimal :: Parser Int
hexadecimal = do
  _ <- string "0x" <|> string "0X"
  digits <- some (satisfy (\c -> isDigit c || c `elem` ("abcdefABCDEF" :: String)))
  return $ read ("0x" ++ digits)

binary :: Parser Int
binary = do
  _ <- string "0b" <|> string "0B"
  digits <- some (satisfy (`elem` ("01" :: String)))
  return $ foldl (\acc d -> acc * 2 + read [d]) 0 digits

-- MonadPlus: try different number formats
number :: Parser Int
number = lexeme $ hexadecimal <|> binary <|> decimal

-- Expression parsing with backtracking
data Expr = Num Int | Add Expr Expr | Mul Expr Expr | Var String
  deriving (Show, Eq)

variable :: Parser String
variable = lexeme $ do
  first <- satisfy isAlpha
  rest <- many (satisfy (\c -> isAlpha c || isDigit c))
  return (first:rest)

factor :: Parser Expr
factor = (Num <$> number) <|> (Var <$> variable) <|> parens expr

parens :: Parser a -> Parser a
parens p = do
  _ <- lexeme $ char '('
  result <- p
  _ <- lexeme $ char ')'
  return result

term :: Parser Expr
term = chainl1 factor (Mul <$ lexeme (char '*'))

expr :: Parser Expr
expr = chainl1 term (Add <$ lexeme (char '+'))

-- Helper for left-associative operators
chainl1 :: Parser a -> Parser (a -> a -> a) -> Parser a
chainl1 p op = do
  x <- p
  rest x
  where
    rest x = (do f <- op
                 y <- p
                 rest (f x y)) <|> return x

-- Parse with multiple strategies and error recovery
parseExpression :: String -> Either String Expr
parseExpression input =
  case runParser (spaces >> expr) input of
    [(result, "")] -> Right result
    [(_, remaining)] -> Left $ "Unexpected input: " ++ remaining
    [] -> Left "Parse error: no valid parse"
    _ -> Left "Parse error: ambiguous parse"

-- Usage examples
main :: IO ()
main = do
  print $ parseExpression "42"                   -- Right (Num 42)
  print $ parseExpression "0xFF"                 -- Right (Num 255)
  print $ parseExpression "0b1010"               -- Right (Num 10)
  print $ parseExpression "x + 42"               -- Right (Add (Var "x") (Num 42))
  print $ parseExpression "(a + 0x10) * b"       -- Right (Mul (Add (Var "a") (Num 16)) (Var "b"))
  print $ parseExpression "invalid@"             -- Left "Unexpected input: @"

Async operation chaining with service fallbacks, demonstrating how MonadPlus patterns help build resilient distributed systems with multiple retry strategies.

// MonadPlus-like pattern for async operations with fallbacks

interface AsyncResult<E, A> {
  readonly _tag: 'Success' | 'Failure';
  readonly value?: A;
  readonly error?: E;
}

class AsyncMonad<E, A> {
  constructor(private computation: () => Promise<AsyncResult<E, A>>) {}

  // Monad operations
  static of<E, A>(value: A): AsyncMonad<E, A> {
    return new AsyncMonad(() => Promise.resolve({
      _tag: 'Success',
      value
    }));
  }

  async flatMap<B>(f: (a: A) => AsyncMonad<E, B>): Promise<AsyncMonad<E, B>> {
    const result = await this.computation();
    if (result._tag === 'Failure') {
      return new AsyncMonad(() => Promise.resolve({
        _tag: 'Failure',
        error: result.error
      }));
    }
    return f(result.value!);
  }

  // MonadPlus operations
  static mzero<E, A>(): AsyncMonad<E, A> {
    return new AsyncMonad(() => Promise.resolve({
      _tag: 'Failure',
      error: undefined as unknown as E
    }));
  }

  mplus(other: AsyncMonad<E, A>): AsyncMonad<E, A> {
    return new AsyncMonad(async () => {
      const result = await this.computation();
      if (result._tag === 'Success') {
        return result;
      }
      return other.computation();
    });
  }

  async run(): Promise<AsyncResult<E, A>> {
    return this.computation();
  }
}

// API service interfaces
interface User {
  id: number;
  name: string;
  email: string;
}

interface UserService {
  getUser(id: number): AsyncMonad<string, User>;
}

// Different API implementations
class PrimaryUserService implements UserService {
  getUser(id: number): AsyncMonad<string, User> {
    return new AsyncMonad(async () => {
      try {
        // Simulate primary API call
        await new Promise(resolve => setTimeout(resolve, 100));

        if (Math.random() > 0.7) { // 30% failure rate
          return {
            _tag: 'Success',
            value: { id, name: `User${id}`, email: `user${id}@primary.com` }
          };
        }

        return {
          _tag: 'Failure',
          error: 'Primary service unavailable'
        };
      } catch (error) {
        return {
          _tag: 'Failure',
          error: 'Primary service error'
        };
      }
    });
  }
}

class BackupUserService implements UserService {
  getUser(id: number): AsyncMonad<string, User> {
    return new AsyncMonad(async () => {
      try {
        // Simulate backup API call
        await new Promise(resolve => setTimeout(resolve, 200));

        if (Math.random() > 0.3) { // 70% success rate
          return {
            _tag: 'Success',
            value: { id, name: `BackupUser${id}`, email: `user${id}@backup.com` }
          };
        }

        return {
          _tag: 'Failure',
          error: 'Backup service unavailable'
        };
      } catch (error) {
        return {
          _tag: 'Failure',
          error: 'Backup service error'
        };
      }
    });
  }
}

class CacheUserService implements UserService {
  private cache = new Map<number, User>();

  constructor() {
    // Pre-populate cache
    this.cache.set(1, { id: 1, name: 'CachedUser1', email: 'user1@cache.local' });
    this.cache.set(2, { id: 2, name: 'CachedUser2', email: 'user2@cache.local' });
  }

  getUser(id: number): AsyncMonad<string, User> {
    return new AsyncMonad(async () => {
      const user = this.cache.get(id);
      if (user) {
        return {
          _tag: 'Success',
          value: user
        };
      }

      return {
        _tag: 'Failure',
        error: 'User not found in cache'
      };
    });
  }
}

// Service orchestrator using MonadPlus pattern
class UserServiceOrchestrator {
  constructor(
    private primary: UserService,
    private backup: UserService,
    private cache: UserService
  ) {}

  async getUserWithFallback(id: number): Promise<AsyncResult<string, User>> {
    // MonadPlus chain: try primary, then backup, then cache
    const result = this.primary.getUser(id)
      .mplus(this.backup.getUser(id))
      .mplus(this.cache.getUser(id));

    return result.run();
  }

  async getUserProfile(id: number): Promise<AsyncResult<string, { user: User; profile: string }>> {
    const userMonad = this.primary.getUser(id)
      .mplus(this.backup.getUser(id))
      .mplus(this.cache.getUser(id));

    // Monadic composition: chain dependent operations
    const profileMonad = await userMonad.flatMap(user =>
      new AsyncMonad(async () => {
        // Simulate profile enrichment
        await new Promise(resolve => setTimeout(resolve, 50));
        return {
          _tag: 'Success' as const,
          value: {
            user,
            profile: `Enhanced profile for ${user.name}`
          }
        };
      })
    );

    return profileMonad.run();
  }
}

// Usage example
async function demonstrateMonadPlus() {
  const orchestrator = new UserServiceOrchestrator(
    new PrimaryUserService(),
    new BackupUserService(),
    new CacheUserService()
  );

  console.log('Testing MonadPlus fallback chain:');

  for (let i = 1; i <= 5; i++) {
    const result = await orchestrator.getUserWithFallback(i);

    if (result._tag === 'Success') {
      console.log(`User ${i}:`, result.value);
    } else {
      console.log(`Failed to get user ${i}:`, result.error);
    }
  }

  console.log('\nTesting monadic composition:');

  const profileResult = await orchestrator.getUserProfile(1);
  if (profileResult._tag === 'Success') {
    console.log('User profile:', profileResult.value);
  } else {
    console.log('Failed to get profile:', profileResult.error);
  }
}

// Run the demonstration
demonstrateMonadPlus().catch(console.error);

Database query system with retry logic, showing how MonadPlus enables robust data access patterns with automatic fallback between different data sources.

using System;
using System.Collections.Generic;
using System.Threading.Tasks;

// MonadPlus-like pattern in C#
public interface IAsyncOption<T>
{
    Task<TResult> MatchAsync<TResult>(
        Func<T, Task<TResult>> onSuccess,
        Func<Task<TResult>> onFailure);
}

public class AsyncSuccess<T> : IAsyncOption<T>
{
    private readonly T _value;
    public AsyncSuccess(T value) => _value = value;

    public async Task<TResult> MatchAsync<TResult>(
        Func<T, Task<TResult>> onSuccess,
        Func<Task<TResult>> onFailure)
    {
        return await onSuccess(_value);
    }
}

public class AsyncFailure<T> : IAsyncOption<T>
{
    private readonly Exception error;
    public AsyncFailure(Exception error) => this.error = error;

    public async Task<TResult> MatchAsync<TResult>(
        Func<T, Task<TResult>> onSuccess,
        Func<Task<TResult>> onFailure)
    {
        return await onFailure();
    }
}

// MonadPlus operations
public static class AsyncOption
{
    public static IAsyncOption<T> Success<T>(T value) => new AsyncSuccess<T>(value);
    public static IAsyncOption<T> Failure<T>(Exception error) => new AsyncFailure<T>(error);
    public static IAsyncOption<T> MZero<T>() => new AsyncFailure<T>(new InvalidOperationException("MZero"));
}

public static class AsyncOptionExtensions
{
    // Monadic bind
    public static async Task<IAsyncOption<TResult>> FlatMapAsync<T, TResult>(
        this IAsyncOption<T> option,
        Func<T, Task<IAsyncOption<TResult>>> selector)
    {
        return await option.MatchAsync(
            onSuccess: selector,
            onFailure: () => Task.FromResult(AsyncOption.Failure<TResult>(new InvalidOperationException("Previous operation failed")))
        );
    }

    // MonadPlus choice (mplus equivalent)
    public static IAsyncOption<T> OrElse<T>(this IAsyncOption<T> first, Func<Task<IAsyncOption<T>>> second)
    {
        return new AsyncChoice<T>(first, second);
    }
}

// Lazy evaluation for choice
public class AsyncChoice<T> : IAsyncOption<T>
{
    private readonly IAsyncOption<T> _first;
    private readonly Func<Task<IAsyncOption<T>>> _second;

    public AsyncChoice(IAsyncOption<T> first, Func<Task<IAsyncOption<T>>> second)
    {
        _first = first;
        _second = second;
    }

    public async Task<TResult> MatchAsync<TResult>(
        Func<T, Task<TResult>> onSuccess,
        Func<Task<TResult>> onFailure)
    {
        var firstResult = await _first.MatchAsync(
            onSuccess: async value => (true, await onSuccess(value)),
            onFailure: () => Task.FromResult((false, default(TResult)!))
        );

        if (firstResult.Item1)
        {
            return firstResult.Item2;
        }

        var secondOption = await _second();
        return await secondOption.MatchAsync(onSuccess, onFailure);
    }
}

// Database entities
public class Customer
{
    public int Id { get; set; }
    public string Name { get; set; } = string.Empty;
    public string Email { get; set; } = string.Empty;
    public DateTime CreatedAt { get; set; }
}

// Database connection interfaces
public interface IDatabase
{
    Task<IAsyncOption<Customer>> GetCustomerAsync(int id);
    Task<IAsyncOption<List<Customer>>> GetCustomersAsync(string namePrefix);
}

// Primary database connection
public class PrimaryDatabase : IDatabase
{
    public async Task<IAsyncOption<Customer>> GetCustomerAsync(int id)
    {
        try
        {
            await Task.Delay(100); // Simulate network delay

            // Simulate occasional failures
            if (new Random().NextDouble() > 0.6)
            {
                return AsyncOption.Success(new Customer
                {
                    Id = id,
                    Name = $"Customer {id}",
                    Email = $"customer{id}@primary.db",
                    CreatedAt = DateTime.Now
                });
            }

            return AsyncOption.Failure<Customer>(new TimeoutException("Primary database timeout"));
        }
        catch (Exception ex)
        {
            return AsyncOption.Failure<Customer>(ex);
        }
    }

    public async Task<IAsyncOption<List<Customer>>> GetCustomersAsync(string namePrefix)
    {
        try
        {
            await Task.Delay(150);

            if (new Random().NextDouble() > 0.5)
            {
                var customers = new List<Customer>();
                for (int i = 1; i <= 3; i++)
                {
                    customers.Add(new Customer
                    {
                        Id = i,
                        Name = $"{namePrefix}Customer{i}",
                        Email = $"{namePrefix.ToLower()}{i}@primary.db",
                        CreatedAt = DateTime.Now
                    });
                }
                return AsyncOption.Success(customers);
            }

            return AsyncOption.Failure<List<Customer>>(new InvalidOperationException("Primary database overloaded"));
        }
        catch (Exception ex)
        {
            return AsyncOption.Failure<List<Customer>>(ex);
        }
    }
}

// Secondary database connection
public class SecondaryDatabase : IDatabase
{
    public async Task<IAsyncOption<Customer>> GetCustomerAsync(int id)
    {
        try
        {
            await Task.Delay(200);

            if (new Random().NextDouble() > 0.3)
            {
                return AsyncOption.Success(new Customer
                {
                    Id = id,
                    Name = $"SecondaryCustomer {id}",
                    Email = $"customer{id}@secondary.db",
                    CreatedAt = DateTime.Now.AddDays(-1)
                });
            }

            return AsyncOption.Failure<Customer>(new InvalidOperationException("Secondary database unavailable"));
        }
        catch (Exception ex)
        {
            return AsyncOption.Failure<Customer>(ex);
        }
    }

    public async Task<IAsyncOption<List<Customer>>> GetCustomersAsync(string namePrefix)
    {
        try
        {
            await Task.Delay(250);

            var customers = new List<Customer>
            {
                new Customer { Id = 10, Name = $"{namePrefix}SecondaryCustomer", Email = $"{namePrefix.ToLower()}@secondary.db", CreatedAt = DateTime.Now.AddDays(-1) }
            };
            return AsyncOption.Success(customers);
        }
        catch (Exception ex)
        {
            return AsyncOption.Failure<List<Customer>>(ex);
        }
    }
}

// Cache layer
public class CacheDatabase : IDatabase
{
    private readonly Dictionary<int, Customer> _cache = new Dictionary<int, Customer>
    {
        { 1, new Customer { Id = 1, Name = "CachedCustomer 1", Email = "cached1@cache.local", CreatedAt = DateTime.Now.AddMinutes(-5) } },
        { 2, new Customer { Id = 2, Name = "CachedCustomer 2", Email = "cached2@cache.local", CreatedAt = DateTime.Now.AddMinutes(-3) } }
    };

    public async Task<IAsyncOption<Customer>> GetCustomerAsync(int id)
    {
        await Task.Delay(10); // Simulate cache lookup time

        if (_cache.TryGetValue(id, out var customer))
        {
            return AsyncOption.Success(customer);
        }

        return AsyncOption.Failure<Customer>(new KeyNotFoundException($"Customer {id} not found in cache"));
    }

    public async Task<IAsyncOption<List<Customer>>> GetCustomersAsync(string namePrefix)
    {
        await Task.Delay(5);

        var customers = new List<Customer>(_cache.Values);
        return AsyncOption.Success(customers);
    }
}

// Service using MonadPlus pattern
public class CustomerService
{
    private readonly IDatabase primary;
    private readonly IDatabase secondary;
    private readonly IDatabase cache;

    public CustomerService(
        IDatabase primary,
        IDatabase secondary,
        IDatabase cache)
    {
        this.primary = primary;
        this.secondary = secondary;
        this.cache = cache;
    }

    // MonadPlus: Try multiple data sources with fallback
    public async Task<Customer> GetCustomerAsync(int id)
    {
        var primaryResult = await primary.GetCustomerAsync(id);
        var result = primaryResult
            .OrElse(() => secondary.GetCustomerAsync(id))
            .OrElse(() => cache.GetCustomerAsync(id));

        return await result.MatchAsync(
            onSuccess: customer => Task.FromResult(customer),
            onFailure: () => throw new InvalidOperationException($"Customer {id} not found in any data source")
        );
    }

    // Monadic composition: Chain dependent operations
    public async Task<string> GetCustomerReportAsync(int id)
    {
        var primaryCustomer = await primary.GetCustomerAsync(id);
        var customerOption = primaryCustomer
            .OrElse(() => secondary.GetCustomerAsync(id))
            .OrElse(() => cache.GetCustomerAsync(id));

        var reportOption = await customerOption.FlatMapAsync(async customer =>
        {
            // Simulate report generation
            await Task.Delay(100);
            var report = $"Customer Report:\nID: {customer.Id}\nName: {customer.Name}\nEmail: {customer.Email}\nCreated: {customer.CreatedAt:yyyy-MM-dd}";
            return AsyncOption.Success(report);
        });

        return await reportOption.MatchAsync(
            onSuccess: report => Task.FromResult(report),
            onFailure: () => throw new InvalidOperationException($"Could not generate report for customer {id}")
        );
    }
}

// Usage example
class Program
{
    static async Task Main(string[] args)
    {
        var customerService = new CustomerService(
            new PrimaryDatabase(),
            new SecondaryDatabase(),
            new CacheDatabase()
        );

        Console.WriteLine("Testing MonadPlus database fallback:");

        for (int i = 1; i <= 5; i++)
        {
            try
            {
                var customer = await customerService.GetCustomerAsync(i);
                Console.WriteLine($"Customer {i}: {customer.Name} ({customer.Email})");
            }
            catch (Exception ex)
            {
                Console.WriteLine($"Failed to get customer {i}: {ex.Message}");
            }
        }

        Console.WriteLine("\nTesting monadic composition (reports):");

        try
        {
            var report = await customerService.GetCustomerReportAsync(1);
            Console.WriteLine(report);
        }
        catch (Exception ex)
        {
            Console.WriteLine($"Failed to generate report: {ex.Message}");
        }
    }
}

MonadFail #

While MonadPlus provides choice and fallback mechanisms for monadic computations, sometimes we need more precise control over why a computation fails. Pattern matching failures, partial functions, and explicit error conditions all require a way to signal failure with meaningful error messages. This is where MonadFail comes into play.

MonadFail separates the concern of explicit failure from the choice operations of MonadPlus. Where MonadPlus focuses on trying alternatives until one succeeds, MonadFail provides a principled way to signal that a computation has failed with a specific reason, enabling better error reporting and debugging.

MonadFail provides a single operation for explicit failure with error messages:

class Monad m => MonadFail m where
  fail :: String -> m a

Laws:

• Absorption: fail s >>= f = fail s (failure propagates)
• Left zero: fail s >> m = fail s (failure short-circuits)

The fail function creates a monadic computation that represents failure with an error message. This is particularly useful for pattern match failures and explicit error conditions where you want to provide context about what went wrong.

The motivation for MonadFail stems from how Haskell's do-notation handles refutable pattern matches. Consider what happens when you write a pattern match that may fail:

do (x:xs) <- items
   return (x + sum xs)

This code gets desugared into something more complex:

let handle (x:xs) = return (x + sum xs)
    handle _      = fail "Pattern match failure"
in items >>= handle

The problem becomes clear: a refutable pattern in do-notation requires a fail function. Without an explicit type-class constraint, that failure capability is hidden.

Consider these common monads where fail cannot be sensibly implemented:

• Either: What error should we put in Left?
• IO: Should pattern failures throw runtime exceptions?
• Reader: Should we terminate the entire context-dependent computation?

Before MonadFail separated this behavior, failed pattern matches in do-notation could fall back to error, turning pattern match failures into runtime crashes. This meant that seemingly polymorphic monadic code could suddenly terminate your program:

-- This looks safe and polymorphic...
processItems :: Monad m => m [Int] -> m Int
processItems items = do
  (x:xs) <- items  -- But this pattern match could crash!
  return (x + sum xs)

-- Using with IO: crashes on empty list
result1 <- processItems (return [])  -- Runtime error!

-- Using with Either: also crashes
let result2 = processItems (Right [])  -- Runtime error!

MonadFail solves this by making failure capabilities explicit in the type signature. Now the compiler can track which computations might fail and ensure that fail is only available when the monad can handle it meaningfully:

-- Now the type signature tells the truth
processItems :: MonadFail m => m [Int] -> m Int
processItems items = do
  (x:xs) <- items  -- Pattern match requires MonadFail
  return (x + sum xs)

-- Safe usage with Maybe (has MonadFail instance)
result1 = processItems (Just [])      -- Nothing

-- Safe usage with IO (has MonadFail instance)
result2 <- processItems (return [])   -- IOException

-- Won't compile with plain Either (no MonadFail instance)
-- let result3 = processItems (Right [])  -- Compile error!

This design makes refutable pattern failure explicit: if do-notation needs to handle pattern match failures, the MonadFail m constraint makes that requirement visible in the type.

Visualization #

1. MonadPlus Structure

MonadPlus Pattern:

Monadic Bind + Choice:
m >>= f ──┐
          ├──> m a (sequential composition)
n >>= f ──┘
mplus

Failure Propagation:

mzero >>= f = mzero    (left zero)
m >> mzero = mzero     (right zero, for instances that satisfy it)

Parser Backtracking:

        ┌─ try hexNumber ──> success? ──> return result
input ──┤
        ├─ try binary ────> success? ──> return result
        └─ try decimal ───> success? ──> return result
                            │
                            ▼
                         failure ──> mzero

Left Distribution:

(m `mplus` n) >>= f = (m >>= f) `mplus` (n >>= f)

     m ──┐         m >>= f ──┐
         ├─ mplus            ├─ mplus ──> result
     n ──┘         n >>= f ──┘
         │              │
         ▼              ▼
      >>= f          distribute


2. MonadFail Structure

Explicit Failure:

fail :: String -> m a

Type Safety:

Monad m      => no refutable do-patterns
MonadFail m  => may fail (explicit in type)

Failure Flow:

computation ──> pattern match ──> success? ──┐
                     │                       │
                     ▼                       ▼
                  failure                continue
                     │                       │
                     ▼                       ▼
              fail "message"             more code

Absorption Laws:

fail s >>= f = fail s    (failure propagates)
fail s >> m = fail s     (failure short-circuits)

Before MonadFail (dangerous):

processItems :: Monad m => m [Int] -> m Int
                ├── could crash! ──┤

After MonadFail (safe):

processItems :: MonadFail m => m [Int] -> m Int
                ├── explicit failure capability ──┤


3. Hierarchy Relationships

Type Class Hierarchy:

    Functor
       │
       ▼
   Applicative ──┐
       │         │
       ▼         ▼
     Monad   Alternative
       │         │
       ├─────────┤
       ▼         ▼
   MonadFail  MonadPlus
       │         │
       └────┬────┘
            ▼
      Combined Power:
   - Sequential composition (Monad)
   - Choice operations (Alternative)
   - Explicit failure (MonadFail)
   - Backtracking (MonadPlus)

Capability Matrix #

Conclusion #

Programming is fundamentally about making choices. Sometimes we need fallback strategies when our first attempt fails. Sometimes we need to sequence dependent operations while preserving the ability to backtrack. Sometimes we need explicit control over why and how computations fail.

Alternative gives us choice within applicative computations. With empty and <|>, we could express fallback strategies and try multiple approaches until one succeeded. This alone changes parsing, validation, and search algorithms by providing a principled way to handle failure and choice.

MonadPlus elevates these concepts to the monadic level. By combining the sequential composition of monads with the choice operations of Alternative, we gained the power of backtracking - the ability to explore multiple computational paths with full context awareness. This is why MonadPlus shines in complex parsing scenarios, where each parsing decision depends on previous results, yet we still need the ability to backtrack and try alternatives.

MonadFail addressed a subtle but crucial problem: making failure capabilities explicit and safe. By separating explicit failure from general monadic operations, MonadFail ensures that type signatures tell the truth about what can fail and why.

From a category theory standpoint, we've witnessed the emergence of increasingly sophisticated structures:

• Alternative enriches applicative functors with monoid-like choice for each result type
• MonadPlus combines monadic sequencing with Alternative-style choice operations
• MonadFail makes refutable do-pattern failure explicit in the type

As software systems grow more complex and distributed, the need for principled approaches to choice, failure, and recovery only increases. Alternative, MonadPlus, and MonadFail provide a solid foundation for building reliable systems that gracefully handle the inevitable failures and choices that define real-world computing. A system that combines all three - choice operations, sequential composition, explicit failure, and backtracking - can handle complex scenarios with surprisingly simple code. This is the essence of functional programming: finding the right abstractions that make the complex simple, while preserving the flexibility to handle edge cases and unexpected situations.

Source code #

Reference implementation (opens in a new tab)