Alternative

    _    _   _____ _____ ____  _   _    _  _____ _____     _______ ____
   / \  | | |_   _| ____|  _ \| \ | |  / \|_   _|_ _\ \   / / ____/ ___|
  / _ \ | |   | | |  _| | |_) |  \| | / _ \ | |  | | \ \ / /|  _| \___ \
 / ___ \| |___| | | |___|  _ <| |\  |/ ___ \| |  | |  \ V / | |___ ___) |
/_/   \_\_____|_| |_____|_| \_\_| \_/_/   \_\_| |___|  \_/  |_____|____/

We always have to make choices: willingly or unwillingly, one way or the other, but it comes down to us making a choice or somebody else making a choice for us. Programming mirrors this reality. Sometimes we need multiple options and must pick one. Sometimes computations fail and we need fallback strategies. Sometimes we want to try several approaches and see which succeeds.

For example parsing a complex file format: you might try parsing as JSON, then XML, then CSV until something works. Or consider form validation: you want to collect all errors, not just the first one. Or imagine a search algorithm: you want to explore multiple paths and combine the results.

We need a foundation for choice and failure that can be extended to monadic computations. That foundation shows up in common programming patterns: parsing with fallbacks, validation with error accumulation, and search with multiple strategies.

Let's take a closer look at the tools that deal with the range of situations from simple "this or that" decision to complex parsing pipelines that gracefully handle failure.

Alternative #

Alternative^[2] is a structure that adds choice and failure to applicative functors. While applicative lets us combine multiple wrapped values with pure functions, Alternative gives us the power to choose between alternatives when computations might fail or when we want to try multiple approaches.

Alternative is like a machine for answering the question: "What if this computation fails? What should I try instead?" It provides two fundamental operations: a way to represent failure (empty) and a way to choose between alternatives (<|>).

Formal Definition #

Alternative is a type class that extends applicative functor with two additional operations:

class Applicative f => Alternative f where
  empty :: f a                    -- Identity element (failure/zero)
  (<|>) :: f a -> f a -> f a     -- Associative binary operation (choice)

Laws:

• Identity: empty <|> v = v and v <|> empty = v
• Associativity: (u <|> v) <|> w = u <|> (v <|> w)

The empty element represents failure or "no result", while <|> (pronounced "alt" or "or") provides a way to choose the first successful alternative.

From a category theory perspective, Alternative enriches applicative functors with a monoid-like choice operation for each f a. For a fixed result type a, empty and <|> make f a behave like a monoid: there is a neutral failed computation, and alternatives can be combined associatively.

Monoid Structure: For each result type a, the operations empty and <|> form a monoid on f a:

• Identity element: empty acts as the neutral element for choice
• Associative operation: <|> allows us to chain alternatives without worrying about grouping
• Closure: Combining alternatives of the same type yields another alternative of that type

Category Theory View:
┌─────────────┐    <|>     ┌─────────────┐         ┌─────────────┐
│   f a       │  ------->  │   f a       │  -----> │   f a       │
│ (first try) │            │ (second try)│         │  (result)   │
└─────────────┘            └─────────────┘         └─────────────┘
                                 ↑
                             empty (failure)

External and Internal Choice #

It is useful to separate two kinds of choice: external choice, where the type itself records which branch was taken, and internal choice, where the choice is handled inside a computational context.

External Choice - Coproducts #

External coproducts represent choice between different types. They live in the category Set (or Hask in Haskell) and provide disjoint union:

Category Set:
    A ────────┐
              ├──> A + B  (Either A B)
    B ────────┘


External Coproduct Morphisms:

inL: A → A + B    (Left injection)
inR: B → A + B    (Right injection)
[f,g]: A + B → C  (case analysis)

One straightforward example of external choice in Haskell is Either a b.

-- External choice: different types
data Either a b = Left a | Right b

-- Usage: choosing between fundamentally different computations
parseAsInt :: String -> Either String Int
parseAsFloat :: String -> Either String Float

-- Different result types require explicit handling
result :: Either String (Either Int Float)

Properties:

• Work in the category Set or Hask
• Provide tagged unions: Left vs Right
• Require explicit handling of different cases
• Create sum types: A + B

Internal Choice #

Internal choice represents choice between computations with the same result type. The choice mechanism lives inside the functor structure:

Category of Endofunctors:
    f a ────────┐
                ├──> f a  (same type, internal choice)
    f a ────────┘
           <|>


Internal Alternative Operations:

empty: f a               (failure/zero)
<|>: f a × f a → f a     (choice operation)

In Haskell, this internal choice functionality is provided by the Alternative type class itself.

-- Internal choice: same type, different values/computations
parseAsNumber :: String -> Maybe Int
parseAsHex :: String -> Maybe Int

-- Choice happens within the same functor
result :: Maybe Int = parseAsNumber input <|> parseAsHex input

Properties:

• Work inside one functorial context f
• Provide implicit choice: first success wins
• Allow uniform handling: same result type
• Create alternative computations: f a <|> f a

Programming Implications #

This categorical difference has profound programming implications:

• External: Forces explicit case handling, different types, compile-time safety
• Internal: Enables transparent fallbacks, same types, runtime choice

External Example:

-- Must handle both cases explicitly
case parseJSON input of
  Left error -> handleError error
  Right value -> processValue value

Internal Example:

-- Automatic fallback, uniform handling
let result = parseJSON input <|> parseXML input <|> parseCSV input

This is why Alternative is useful for parsing, search, and validation: it provides choice while maintaining type uniformity, allowing complex fallback strategies without explicit case analysis.

Distributivity #

Alternative interacts with Applicative in a principled way:

• empty <*> f = empty (failure propagates)
• (f <|> g) <*> a = (f <*> a) <|> (g <*> a) (choice distributes over application)

For many familiar instances, this resembles a semiring-style interaction: empty behaves like zero, <|> behaves like addition, and applicative application distributes over choice. It should not be read as a full distributive lattice^[1] in general: the Alternative type class does not require all lattice laws.

Natural Transformation Perspective #

Each Alternative instance defines operations that are natural in the result type and preserve the categorical structure while adding choice semantics. The <|> operation is natural in the sense that it commutes with fmap:

fmap f (a <|> b) = fmap f a <|> fmap f b

Alternative examples #

Parser Combinators

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

-- Simple parser type
newtype Parser a = Parser (String -> Maybe (a, String))

instance Functor Parser where
  fmap f (Parser p) = Parser $ \input ->
    case p input of
      Nothing -> Nothing
      Just (a, rest) -> Just (f a, rest)

instance Applicative Parser where
  pure a = Parser $ \input -> Just (a, input)
  Parser pf <*> Parser pa = Parser $ \input ->
    case pf input of
      Nothing -> Nothing
      Just (f, rest1) -> case pa rest1 of
        Nothing -> Nothing
        Just (a, rest2) -> Just (f a, rest2)

instance Alternative Parser where
  empty = Parser $ \_ -> Nothing
  Parser p1 <|> Parser p2 = Parser $ \input ->
    case p1 input of
      Nothing -> p2 input
      result -> result

-- Basic parsers
digit :: Parser Char
digit = Parser $ \input ->
  case input of
    (x:xs) | isDigit x -> Just (x, xs)
    _ -> Nothing

letter :: Parser Char
letter = Parser $ \input ->
  case input of
    (x:xs) | isAlpha x -> Just (x, xs)
    _ -> Nothing

-- Complex parser using Alternative
identifier :: Parser String
identifier = (:) <$> letter <*> many (letter <|> digit)

number :: Parser Int
number = read <$> some digit

-- Parse different types of tokens
token :: Parser String
token = identifier <|> (show <$> number) <|> string "(" <|> string ")"
  where
    string s = Parser $ \input ->
      if take (length s) input == s
        then Just (s, drop (length s) input)
        else Nothing

-- Usage example
parseExpression :: String -> Maybe [String]
parseExpression input = case runParser (many token) input of
  Just (tokens, "") -> Just tokens
  _ -> Nothing
  where
    runParser (Parser p) = p

-- Test cases
main :: IO ()
main = do
  print $ parseExpression "hello123"     -- Just ["hello123"]
  print $ parseExpression "42"           -- Just ["42"]
  print $ parseExpression "func(42)"     -- Just ["func","(","42",")"]
  print $ parseExpression "invalid@"     -- Nothing

Validation with Error Accumulation

// Alternative-like validation in TypeScript

interface Validation<E, A> {
  readonly _tag: 'Success' | 'Failure';
  readonly value?: A;
  readonly errors?: E[];
}

const success = <E, A>(value: A): Validation<E, A> => ({
  _tag: 'Success',
  value
});

const failure = <E, A>(error: E): Validation<E, A> => ({
  _tag: 'Failure',
  errors: [error]
});

// Alternative operations
const empty = <E, A>(): Validation<E, A> => ({
  _tag: 'Failure',
  errors: []
});

const alt = <E, A>(
  first: Validation<E, A>,
  second: Validation<E, A>
): Validation<E, A> => {
  if (first._tag === 'Success') return first;
  if (second._tag === 'Success') return second;

  return {
    _tag: 'Failure',
    errors: [...(first.errors || []), ...(second.errors || [])]
  };
};

// Validation functions
const validateEmail = (email: string): Validation<string, string> => {
  if (email.includes('@')) {
    return success(email);
  }
  return failure('Invalid email format');
};

const validatePhone = (phone: string): Validation<string, string> => {
  if (/^\d{10}$/.test(phone)) {
    return success(phone);
  }
  return failure('Phone must be 10 digits');
};

const validateURL = (url: string): Validation<string, string> => {
  if (url.startsWith('http://') || url.startsWith('https://')) {
    return success(url);
  }
  return failure('URL must start with http:// or https://');
};

// Contact validation with multiple alternatives
interface Contact {
  name: string;
  contact: string;
}

const validateContact = (name: string, contact: string): Validation<string, Contact> => {
  const contactValidation = alt(
    alt(validateEmail(contact), validatePhone(contact)),
    validateURL(contact)
  );

  if (contactValidation._tag === 'Success') {
    return success({ name, contact: contactValidation.value! });
  }

  return {
    _tag: 'Failure',
    errors: contactValidation.errors || ['No valid contact method']
  };
};

// Usage examples
console.log(validateContact('John', 'john@email.com'));
// Success: { name: 'John', contact: 'john@email.com' }

console.log(validateContact('Jane', '1234567890'));
// Success: { name: 'Jane', contact: '1234567890' }

console.log(validateContact('Bob', 'https://bob.dev'));
// Success: { name: 'Bob', contact: 'https://bob.dev' }

console.log(validateContact('Invalid', 'bad-contact'));
// Failure: errors about email, phone, and URL formats

// Define union type for parsed data
type ParsedData = number | boolean | Record<string, unknown>;

// Multiple validation attempts
const tryParseData = (input: string): Validation<string, ParsedData> => {
  const asJSON = (() => {
    try {
      return success<string, ParsedData>(JSON.parse(input) as ParsedData);
    } catch {
      return failure<string, ParsedData>('Not valid JSON');
    }
  })();

  const asNumber = (() => {
    const num = Number(input);
    return isNaN(num) ? failure<string, ParsedData>('Not a valid number') : success<string, ParsedData>(num);
  })();

  const asBoolean = (() => {
    if (input === 'true') return success<string, ParsedData>(true);
    if (input === 'false') return success<string, ParsedData>(false);
    return failure<string, ParsedData>('Not a valid boolean');
  })();

  return alt(alt(asJSON, asNumber), asBoolean);
};

console.log(tryParseData('{"key":"value"}')); // Success: object
console.log(tryParseData('42'));              // Success: 42
console.log(tryParseData('true'));            // Success: true
console.log(tryParseData('invalid'));         // Failure: all three errors

Configuration Loading with Fallbacks

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

// Unit type for void-like operations
public struct Unit
{
    public static readonly Unit Value = new Unit();
}

// Alternative-like pattern in C# using interface
public interface IOption<T>
{
    TResult Match<TResult>(
        Func<T, TResult> onSome,
        Func<TResult> onNone);
}

public class Some<T> : IOption<T>
{
    private readonly T _value;
    public Some(T value) => _value = value;

    public TResult Match<TResult>(
        Func<T, TResult> onSome,
        Func<TResult> onNone) => onSome(_value);
}

public class None<T> : IOption<T>
{
    public TResult Match<TResult>(
        Func<T, TResult> onSome,
        Func<TResult> onNone) => onNone();
}

// Static factory methods
public static class Option
{
    public static IOption<T> Some<T>(T value) => new Some<T>(value);
    public static IOption<T> None<T>() => new None<T>();
}

// Alternative operations
public static class OptionExtensions
{
    public static IOption<T> OrElse<T>(this IOption<T> first, IOption<T> second)
    {
        return first.Match(
            onSome: _ => first,
            onNone: () => second);
    }

    public static IOption<T> OrElse<T>(this IOption<T> first, Func<IOption<T>> secondFactory)
    {
        return first.Match(
            onSome: _ => first,
            onNone: secondFactory);
    }
}

// Configuration loading with multiple fallback strategies
public class ConfigurationLoader
{
    private readonly List<string> _searchPaths;

    public ConfigurationLoader()
    {
        _searchPaths = new List<string>
        {
            "./config.json",
            "./appsettings.json",
            "%APPDATA%/MyApp/config.json",
            "%PROGRAMDATA%/MyApp/config.json"
        };
    }

    // Try loading from file
    private IOption<string> LoadFromFile(string path)
    {
        try
        {
            var expandedPath = Environment.ExpandEnvironmentVariables(path);
            if (File.Exists(expandedPath))
            {
                var content = File.ReadAllText(expandedPath);
                return Option.Some(content);
            }
        }
        catch (Exception ex)
        {
            Console.WriteLine($"Failed to load config from {path}: {ex.Message}");
        }

        return Option.None<string>();
    }

    // Try loading from command line arguments
    private IOption<string> LoadFromArgs(string[] args)
    {
        var configArg = args
            .Where(arg => arg.StartsWith("--config="))
            .FirstOrDefault();

        if (configArg != null)
        {
            var path = configArg.Substring("--config=".Length);
            return LoadFromFile(path);
        }

        return Option.None<string>();
    }

    // Try loading from environment variable
    private IOption<string> LoadFromEnvironment()
    {
        var envPath = Environment.GetEnvironmentVariable("APP_CONFIG_PATH");
        return envPath != null ? LoadFromFile(envPath) : Option.None<string>();
    }

    // Try loading from multiple search paths
    private IOption<string> LoadFromSearchPaths()
    {
        return _searchPaths
            .Select(LoadFromFile)
            .Aggregate(Option.None<string>(), (acc, option) => acc.OrElse(option));
    }

    // Try loading default configuration
    private IOption<string> LoadDefault()
    {
        return Option.Some(@"{
            ""database"": {
                ""connectionString"": ""Data Source=localhost""
            },
            ""logging"": {
                ""level"": ""Info""
            }
        }");
    }

    // Main configuration loading with Alternative pattern
    public string LoadConfiguration(string[] args)
    {
        var config = LoadFromArgs(args)
            .OrElse(() => LoadFromEnvironment())
            .OrElse(() => LoadFromSearchPaths())
            .OrElse(() => LoadDefault());

        return config.Match(
            onSome: content => content,
            onNone: () => throw new InvalidOperationException("Could not load configuration")
        );
    }
}

// Connection string fallback example
public class DatabaseConnectionManager
{
    public IOption<string> GetConnectionString()
    {
        return TryProductionConnection()
            .OrElse(() => TryStagingConnection())
            .OrElse(() => TryDevelopmentConnection())
            .OrElse(() => TryLocalConnection());
    }

    private IOption<string> TryProductionConnection()
    {
        var connStr = Environment.GetEnvironmentVariable("PROD_DB_CONNECTION");
        return !string.IsNullOrEmpty(connStr) ?
            Option.Some(connStr) :
            Option.None<string>();
    }

    private IOption<string> TryStagingConnection()
    {
        var connStr = Environment.GetEnvironmentVariable("STAGING_DB_CONNECTION");
        return !string.IsNullOrEmpty(connStr) ?
            Option.Some(connStr) :
            Option.None<string>();
    }

    private IOption<string> TryDevelopmentConnection()
    {
        return Option.Some("Data Source=dev-server;Initial Catalog=DevDB");
    }

    private IOption<string> TryLocalConnection()
    {
        return Option.Some("Data Source=localhost;Initial Catalog=LocalDB");
    }
}

// Usage example
class Program
{
    static void Main(string[] args)
    {
        var configLoader = new ConfigurationLoader();
        try
        {
            var config = configLoader.LoadConfiguration(args);
            Console.WriteLine("Configuration loaded:");
            Console.WriteLine(config);
        }
        catch (Exception ex)
        {
            Console.WriteLine($"Failed to load configuration: {ex.Message}");
        }

        var dbManager = new DatabaseConnectionManager();
        var connectionString = dbManager.GetConnectionString();
        connectionString.Match<Unit>(
            onSome: conn => {
                Console.WriteLine($"Using connection: {conn}");
                return Unit.Value;
            },
            onNone: () => {
                Console.WriteLine("No database connection available");
                return Unit.Value;
            }
        );
    }
}

Visualizing alternatives #

1. Alternative Pattern:

Input:     f a ──┐
                 ├──> f a (result)
Input:     f a ──┘
           <|>

Failure Handling:

empty ──> ∅ (no result)

Choice Chain:

parser1 <|> parser2 <|> parser3 <|> ...
   │         │         │
   ▼         ▼         ▼
 fail?    success?   fallback
   │         │         │
   ├─────────┴─────────┤
   │                   │
   ▼                   ▼
 try next           return result

Monoid Laws:

empty <|> v = v        (left identity)
v <|> empty = v        (right identity)
(u <|> v) <|> w = u <|> (v <|> w)  (associativity)


2. Fallback chain

Alternatives can be chained without caring about grouping:

(u <|> v) <|> w = u <|> (v <|> w)

parserJson <|> parserXml <|> parserCsv
    |
    v
try JSON
    |
    +-- success -----------> return JSON result
    |
    +-- failure ---> try XML
                     |
                     +-- success ----> return XML result
                     |
                     +-- failure ---> try CSV
                                      |
                                      +-- success -> return CSV result
                                      |
                                      +-- failure -> empty


3. External choice vs internal choice

External choice records the branch in the value:

A --------\
          +------> A + B
B --------/

Either A B = Left A | Right B

The caller must inspect the tag.


Internal choice keeps the result type fixed
and moves the choice into the context:

F(A) ------\
            <|> ------> F(A)
F(A) ------/

The caller receives one contextual result.
The branching policy belongs to the Alternative instance.


4. Applicative interaction

Choice can distribute through applicative application:

(f <|> g) <*> a = (f <*> a) <|> (g <*> a)

          f : F(A -> B) ----\
                             <|> ----\
          g : F(A -> B) ----/        |
                                      <*> ----> F(B)
          a : F(A) ------------------/

Equivalent view:

          f <*> a ----\
                       <|> ----> F(B)
          g <*> a ----/

The same argument a is applied to whichever function branch succeeds.

Conclusion #

Alternative gives applicative computations a principled language for choice and failure. With empty and <|>, we can express fallback strategies, parser alternatives, validation paths, and search branches without leaving the computational context.

The important constraint is uniformity: internal choice combines computations with the same result type. When the next step depends on a previous result, we need monadic sequencing as well.

Source code #

Reference implementation (opens in a new tab)

References

1. Distributive lattice (opens in a new tab) · Back
2. Alternative and MonadPlus (opens in a new tab) · Back

Continue exploring

• MonadPlus Choice and failure for monadic computations Shared tags: alternative, functional-programming · Same collection · Same subsection
• Applicative functor Applying functions inside a context Shared tags: applicative-functor, category-theory · Same collection · Same subsection
• Monoid Associative combination with identity Shared tags: functional-programming, category-theory · Same collection · Same subsection