Sum Types and Either

A sum type (a.k.a. tagged union or algebraic data type) is a value that is one of several shapes, each carrying its own payload. Turmeric spells these with defdata and takes them apart with match.

(defdata Shape
  (Circle :int)            ; radius
  (Rect   :int :int))      ; width, height

(defn area [s : int] : int
  (match s
    (Circle r)   (* 3 (* r r))
    (Rect  w h)  (* w h)))

Sweet-exp equivalent:

#lang sweet-exp

defdata Shape
  Circle(:int)          ; radius
  Rect(:int :int)       ; width, height

defn area [s : int] : int
  match s
    Circle(r)   *(3 *(r r))
    Rect(w h)   *(w h)

The canonical binary sum is Either L R from stdlib/either.tur: a value is either (Left l) carrying an L, or (Right r) carrying an R.

When to use a sum vs. a struct

Reach for a sum whenever you would otherwise smuggle a "which case is this?" discriminant alongside a payload whose meaning depends on it -- an error code plus a maybe-valid value, a parse result that is either a value or a failure, a protocol step that branches. The sum makes the discriminant and the payload inseparable, so the type checker forces you to handle every case.

Declaring a sum: defdata

(defdata Either :copy [L R]
  (Left L)
  (Right R))

• Name -- the type constructor (Either).
• :copy / :move (optional) -- value discipline. :copy makes a value freely reusable (right for immutable, resource-free sums like Either); the default :move enforces single-use ownership. Put it right after the name.
• Type parameters [L R] (optional) -- a parametric sum. Each constructor may use these in its payload types.
• Constructors (Left L) (Right R) -- one parenthesised arm each. A constructor may take zero payloads ((Nil)), concrete payloads ((Circle :int)), or type-parameter payloads ((Left L)).

Constructors become ordinary callables: (Left 3), (Right "ok").

Record-style variants (named fields)

A variant's payload can be a named-field block instead of positional payloads -- the same [name : type ...] shape defstruct uses. This is the sum-of-records form (Rust's enum Foo { Bar { x: int, y: int } }):

(defdata Shape :copy
  (Circle [radius : float])
  (Rect   [w : float h : float])
  (Square [side : float]))

A record-style variant constructs positionally or by keyword (order free), exactly like a struct:

(Circle 2.0)               ; positional
(Rect :h 4.0 :w 3.0)       ; keyword, reordered

and match binds its fields by position or by name:

(match s
  (Circle r)          (* 2.0 (* 3.14 r))     ; positional
  (Rect :h hv :w wv)  (* 2.0 (+ wv hv))       ; by-name, reordered
  (Square side)       (* 4.0 side))

Positional and record styles can mix across the variants of one defdata; each variant commits to a single style. A positional variant still uses keyword payload types ((Circle :float)); a record variant uses the bare struct field syntax ([radius : float]).

:copy traverses every variant: a :copy sum whose payload includes an owning pointer (rc<T>, ref<T>, weak<T>) is rejected, naming the offending field and variant -- the same rule defstruct :copy enforces, lifted across the sum.

Pattern matching: match

match dispatches on the constructor and binds each payload:

(match e
  (Left  l)  (handle-error l)
  (Right r)  (use r))

Sweet-exp equivalent:

#lang sweet-exp

match e
  Left(l)   handle-error(l)
  Right(r)  use(r)

• Bind a payload to a name (l, r) to use it in that arm's body.
• Use _ to ignore a payload: (Left _).
• Sub-match a payload that is itself a sum by matching again on the bound variable (or, where supported, by nesting the pattern directly).

(match outer
  (Left n)   n
  (Right r)  (match r
               (Nada)   -1
               (Just k) k))

Sweet-exp equivalent:

#lang sweet-exp

match outer
  Left(n)   n
  Right(r)  match r
              Nada()   -1
              Just(k)  k

Updating a record variant inside a match arm

Inside a match arm that has destructured a bare-symbol scrutinee to a specific record variant, the scrutinee is narrowed to that variant for the duration of the arm. That means (with s [field val ...]) can reconstruct through the matched ctor without the caller re-listing every field, and (.field s) reads the variant's field directly:

(defadt Shape :copy
  (Circle [radius : float])
  (Rect   [w : float h : float]))

(defn grow [s : Shape] : Shape
  (match s
    (Circle r) (with s [radius {r * 2.0}])   ; s narrowed to Circle for this arm
    (Rect w h) (with s [w {w * 2.0}])))       ; s narrowed to Rect for this arm

• The scrutinee must be a bare symbol (match s ...), not a compound expression. Compound scrutinees have no name to narrow.
• The ADT (and the matched variant) must be :copy. Move-only ADTs still reject at TUR-E0296.
• The matched variant must be record-style. Narrowing to a positional variant rejects with a message pointing at the missing field names.
• Narrowing is per-arm: once the arm exits, the scrutinee's type widens back to the full ADT, so a later (with s ...) outside the arm still needs its own narrowing context.
• A when-guarded arm narrows through the guard too, and a bare (with s ...) on a multi-variant ADT outside any arm rejects with TUR-E0302 telling you to wrap the update in a match arm.

Exhaustiveness

A match whose scrutinee is a known sum type must cover every constructor (or include a wildcard). A missing arm is a hard error:

match: non-exhaustive patterns -- constructor 'Left' of 'Either' not covered

This is deliberate: the compiler will not let a new constructor silently slip past existing matches.

Opting out: #fx{NonExhaustive}

When you have proven a case cannot occur by other means, place the #fx{NonExhaustive} marker immediately after match (before the scrutinee) to suppress the diagnostic:

(defn unwrap-right [e : int] : int
  (match #{NonExhaustive} e
    (Right r) r))      ; Left is statically impossible here, by construction

Sweet-exp equivalent:

#lang sweet-exp

defn unwrap-right [e : int] : int
  match #{NonExhaustive} e
    Right(r)  r         ; Left is statically impossible here, by construction

The marker is the only escape hatch; without it a non-exhaustive match does not compile. Use it sparingly and leave a comment explaining why the missing arm is unreachable.

Note: this guide's plan (sum-types-either-plan) originally specced exhaustiveness as a warning. The implementation keeps it a hard error (the stronger, pre-existing behaviour) and adds #fx{NonExhaustive} as the deliberate opt-out -- see that plan's ADR for the rationale.

The Either module

stdlib/either.tur is not auto-loaded; pull it in explicitly:

(load "stdlib/either.tur")

It provides:

Either is right-biased by convention: Right is the "success"/"main" arm and Left the "error"/"other" arm, so either-map and the Functor instance act on Right and leave Left untouched -- matching Haskell's Either.

(load "stdlib/either.tur")

(defn inc [x : int] : int (+ x 1))

(defn main [] : int
  (println (from-right -1 (fmap (Right 41) inc)))  ; => 42
  (println (from-left  -1 (fmap (Left 9)  inc)))   ; =>  9  (Left untouched)
  0)

Worked migration: parsing with error detail

str->int / cstr->parse-int fold every failure -- a NULL pointer, an empty string, trailing garbage -- into the sentinel 0, indistinguishable from a legitimately parsed 0. str->int-checked (also in stdlib/str.tur) returns an Either instead, so the failure detail survives:

(load "stdlib/str.tur")

(from-right -1 (str->int-checked "42"))   ; => 42
(right? (str->int-checked "0"))           ; => true   (a real zero, not failure)
(left?  (str->int-checked "12x"))         ; => true   (Left 1: trailing garbage)
(left?  (str->int-checked ""))            ; => true   (Left 0: empty/NULL)

FFI layout

A defdata lowers to a single, type-erased tagged struct. For Either:

typedef struct tur_adt_Either {
    int tag;                       /* 0 = Left, 1 = Right */
    union {
        struct { int64_t _0; } Left;
        struct { int64_t _0; } Right;
    } as;
} tur_adt_Either;

• tag is the discriminant: 0 for the first constructor, 1 for the second, and so on for n-ary sums.
• Payloads are erased to int64_t at the C boundary (the same way Option[A] and Result[A B] erase theirs); the elaborator restores the proper type on extraction.
• Each constructor has a ctor_<Name> factory (ctor_Left, ctor_Right) that heap-allocates the struct, sets the tag, and returns an int64_t handle.

Inline-C blocks can therefore construct and destructure sum values directly:

(defn right-payload [e : int] #{Unsafe} : int
  ```c
  tur_adt_Either *p = (tur_adt_Either *)(intptr_t)e;
  return p->as.Right._0;
  ```)

Writing a typeclass instance over a sum

A type constructor with a free parameter can carry a typeclass instance. For a binary sum, fix one parameter with a partially-applied head -- (Either E) leaves the kind-(* -> *) functor over the Right arm:

(definstance Functor [(Either E)]
  (fmap [container fn]
    ```c
    tur_adt_Either *p = (tur_adt_Either *)(intptr_t)container;
    if (p->tag != 1) return container;          /* Left: identity */
    return ctor_Right(fn.fn(fn.env, p->as.Right._0));
    ```))

The instance is not an orphan when it lives in the module that defines the sum (here, stdlib/either.tur), even though Functor is declared elsewhere -- the owning module of either the class or a type argument may host the instance.

See also

• sum-types-either-plan -- the design plan and ADR.
• stdlib/result.tur / stdlib/option.tur -- the unary-payload tagged structs that predate Either.
• [[data-literals-guide]] -- literal construction syntax that composes with sum payloads.