Traversable

Traversable is the abstraction of a container that can be rebuilt with the same shape while an effect is performed on each element in order. Its one operation, traverse, takes a function that returns an effectful result and applies it to every element, collecting the effects of an applicative functor and returning the rebuilt container inside it. Parsing every string in a list, validating every field, numbering the nodes of a tree and forming cartesian products are the same traversal with different applicatives^[1]. traverse generalizes both map and fold, and its laws guarantee that it visits each element exactly once^[3]. Gibbons and Oliveira identified it as the functional form of the Iterator design pattern^[2].

A traversable functor $T$ has an operation, for every applicative functor $F$:

Either operation determines the other, since $traversef=sequence\circ fmapf$. For lists, traverse applies $f$ to each element and combines the effects with the applicative's $⊛$, rebuilding the list with :::

Only the applicative operations are used, never $>>=$, so the shape of the result is fixed by the shape of the input and the effects cannot choose what to do next based on earlier results. Every monad is applicative, so every monad can be used, and Haskell's older mapM is traverse restricted to monads.

The same traverse, written once per container, gives different operations for different applicatives:

module type APPLICATIVE = sig
  type 'a t
  val pure : 'a -> 'a t
  val map2 : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t
end
 
type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree
 
(* traverse for lists and trees, written once for any applicative. The
   effects happen in the order of the elements. *)
module Traverse (A : APPLICATIVE) = struct
  let rec list f = function [] -> A.pure [] | x :: xs -> A.map2 List.cons (f x) (list f xs)
  let rec tree f = function
    | Leaf -> A.pure Leaf
    | Node (l, x, r) -> A.map2 (fun (l, x) r -> Node (l, x, r)) (A.map2 (fun l x -> (l, x)) (tree f l) (f x)) (tree f r)
end
 
module Option_ = struct type 'a t = 'a option let pure x = Some x
  let map2 f a b = match (a, b) with Some a, Some b -> Some (f a b) | _ -> None end
 
(* Lists: every combination. *)
module List_ = struct type 'a t = 'a list let pure x = [ x ]
  let map2 f xs ys = List.concat_map (fun x -> List.map (f x) ys) xs end
 
(* Validation: failures are collected, not short-circuited. *)
module Valid = struct type 'a t = ('a, string list) result let pure x = Ok x
  let map2 f a b = match (a, b) with Ok a, Ok b -> Ok (f a b) | Error e, Ok _ | Ok _, Error e -> Error e
    | Error e1, Error e2 -> Error (e1 @ e2) end
 
(* State: a value threaded from left to right. *)
module State = struct type 'a t = int -> 'a * int let pure x s = (x, s)
  let map2 f a b s = let x, s = a s in let y, s = b s in (f x y, s) end
 
let show l = "[" ^ String.concat "; " (List.map string_of_int l) ^ "]"

option:  traverse parse ["1"; "2"; "3"] = Some [1; 2; 3]
         traverse parse ["1"; "x"; "3"] = None
valid:   errors: "x" is not a number, "y" is not a number
list:    sequence [[1; 2]; [3]; [4; 5]] = [[1; 3; 4]; [1; 3; 5]; [2; 3; 4]; [2; 3; 5]]
state:   running sums [3; 4; 8; 9; 14], total 14
state:   numbering a tree in order: ((. 0:a .) 1:b ((. 2:c .) 3:d .))

With option the traversal succeeds only if every element does, so parsing a list of strings either returns all the numbers or nothing. With a validation applicative, which combines two failures by concatenating their errors, every invalid element is reported. With lists, whose $⊛$ forms all combinations, sequence is the cartesian product. With state, a value is threaded through the elements in order, which gives running totals (Haskell's mapAccumL) and numbers the nodes of a tree.

A lawful traversal satisfies three laws^[1][3]. Identity: traversing with the identity applicative changes nothing. Composition: two traversals in sequence equal one traversal with the composed applicative $\mathrm{Compose}FG$. Naturality: for any applicative homomorphism $t:F\to G$, a map between applicatives preserving $pure$ and $⊛$:

Together the laws say that a traversal visits each element exactly once and rebuilds the same shape. Jaskelioff and Rypacek proved that lawful traversals correspond to the containers whose shape determines a finite sequence of positions, so traverse can only differ from the expected one in the order in which it visits the positions^[3]. Bird and his coauthors showed how to reason about traversals by comparing them with their effect on positions^[4].

Every traversable container is a functor and a foldable one, and both operations are traversals with particular applicatives^[1]. With the identity applicative, where effects do nothing, traverse is map. With the constant applicative into a monoid $M$, whose values are elements of $M$ and whose $⊛$ combines them, the rebuilt container is discarded and the result is foldMap:

(* traverse determines both map and fold: with the identity applicative
   it is map, and with a constant applicative into a monoid it is
   foldMap. *)
module type APPLICATIVE = sig
  type 'a t
  val pure : 'a -> 'a t
  val map2 : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t
end
 
module Traverse (A : APPLICATIVE) = struct
  let rec list f = function [] -> A.pure [] | x :: xs -> A.map2 List.cons (f x) (list f xs)
end
 
module Identity = struct type 'a t = 'a let pure x = x let map2 f a b = f a b end
 
(* Const: ignores the values and combines the constants in a monoid. *)
module Const (M : sig type t val empty : t val ( <+> ) : t -> t -> t end) = struct
  type 'a t = M.t
  let pure _ = M.empty
  let map2 _ a b = M.( <+> ) a b
end
 
module Sum = struct type t = int let empty = 0 let ( <+> ) = ( + ) end
module Strs = struct type t = string list let empty = [] let ( <+> ) = ( @ ) end
 
let map f xs = let module T = Traverse (Identity) in T.list f xs
let fold_map_sum f xs = let module T = Traverse (Const (Sum)) in T.list f xs
let to_strings f xs = let module T = Traverse (Const (Strs)) in T.list f xs

traverse with Identity (map (x10)):    [10; 20; 30; 40]
traverse with Const Sum (sum of x^2):  30
traverse with Const lists:             [1; 2; 3; 4]

The class hierarchy in Haskell reflects this: Traversable has Functor and Foldable as superclasses, and instances can define fmap and foldMap as fmapDefault and foldMapDefault, which are the two derivations above.

The Iterator pattern of object-oriented design gives sequential access to the elements of a collection without exposing its representation^[7]. Gibbons and Oliveira argued that traverse captures what iteration is for: mapping over the elements and accumulating something while doing so, the two combined in one pass. Applicatives compose, in parallel as products and in sequence as compositions, so separate traversals such as counting characters, counting lines and collecting words can be written separately and fused into a single traversal of the input^[2].

A van Laarhoven lens is a function polymorphic over functors, $\forall F.\mathrm{Functor}F\Rightarrow (a\to Fa)\to s\to Fs$. Strengthening the constraint to applicative functors gives a traversal, which focuses on zero or more parts of a structure, and traverse itself is the traversal of all elements of a container^[5]. Jaskelioff and O'Connor showed that these polymorphic functions are equivalent to concrete descriptions of the focused positions^[6]. Composing a lens with a traversal gives a traversal, which is how lens libraries update every element of a nested collection.

McBride and Paterson introduced Traversable together with applicative functors, generalizing the monadic mapM of Haskell's standard library^[1]. Gibbons and Oliveira related it to the Iterator pattern in 2009^[2], and Jaskelioff and Rypacek characterized its laws in 2012^[3]. With the Foldable/Traversable proposal of 2015, the Prelude's mapM and sequence were generalized to any traversable container^[8].

• ApplicativeAn applicative functor is a functor with pure : a -> f a and an operation that combines independent computations, <*> : f (a -> b) -> f a -> f b, or equivalently a product f a -> f b -> f (a * b), satisfying four laws. It sits between functors and monads: every monad is applicative, but because later steps cannot depend on earlier results, an applicative computation can collect all errors, run its parts in parallel, or be inspected before it runs.
• FoldableFoldable is the abstraction of a container whose elements can be combined in order: a list, a tree, an option. A fold replaces the constructors of the structure with a function and a starting value, and every summary of the elements, their sum, length, maximum, list of elements or whether any satisfies a predicate, is derived from it. Equivalently, a foldable container maps each element into a monoid and combines the results (foldMap). The universal property of fold characterizes exactly which functions are folds.
• FunctorIn functional programming, a functor is a type constructor f with an operation fmap : (a -> b) -> f a -> f b that applies a function inside the structure without changing its shape, preserving identity and composition. Lists, options, trees and functions out of a fixed type are functors. The notion comes from category theory. In OCaml the word also names parametrised modules such as Map.Make.
• MonoidA monoid is a set with an associative binary operation and an identity element for it: integers under addition with 0, strings under concatenation with the empty string, functions under composition with the identity. Associativity means a sequence can be combined with any bracketing, so a fold over a monoid can be split into parts and computed in parallel or incrementally. Lists are the free monoid, and every monoid-valued function on elements extends uniquely to lists.
• Van Laarhoven lensA van Laarhoven lens is a lens represented as a single function polymorphic over functors: forall f. Functor f => (a -> f a) -> s -> f s. Instantiating the functor gives the operations: the constant functor yields the getter and the identity functor the setter. Lenses in this form compose with ordinary function composition, and replacing Functor with Applicative gives traversals, which compose with lenses the same way. The representation is the basis of Haskell's lens library.

• Deriving Strategies in HaskellA code-first tour of stock, newtype, anyclass, and via: what each one generates, and which to reach for.

1. [1]C. McBride, R. Paterson, “Applicative programming with effects”, Journal of Functional Programming 18 (2008).
2. [2]J. Gibbons, B. C. d. S. Oliveira, “The essence of the Iterator pattern”, Journal of Functional Programming 19 (2009).
3. [3]M. Jaskelioff, O. Rypacek, “An investigation of the laws of traversals”, Mathematically Structured Functional Programming (2012).
4. [4]R. Bird, J. Gibbons, S. Mehner, J. Voigtländer, T. Schrijvers, “Understanding idiomatic traversals backwards and forwards”, Haskell Symposium (2013).
5. [5]R. O’Connor, “Functor is to lens as applicative is to biplate: introducing multiplate”, Workshop on Generic Programming (2011).
6. [6]M. Jaskelioff, R. O’Connor, “A representation theorem for second-order functionals”, Journal of Functional Programming 25 (2015).
7. [7]E. Gamma, R. Helm, R. Johnson, J. Vlissides, Design Patterns: Elements of Reusable Object-Oriented Software, Addison-Wesley (1994).
8. [8]The Haskell libraries, “Foldable/Traversable in Prelude” proposal, implemented in GHC 7.10 (2015).

last updated 27 September 2026