nLab list monad

Idea

The list monad or free monoid monad is the monad on Sets (or generally on a distributive monoidal category)

$$\array{ \mathllap{List \;\colon\;} Set &\longrightarrow& Set \\ S &\mapsto& \displaystyle{ \underset{n \colon \mathbb{N}}{\textstyle{\coprod}} } S^{\times n} }$$

which sends a set $S$ to the underlying set $U\big(F(S)\big)$ of the free monoid $F(S) \equiv S^\ast$ on $S$, hence the set of lists (strings) of elements of $S$, hence of $n$-tuples $(s_1, s_2, \cdots, s_n) \colon S^{\times n}$ for any natural number $n$.

Its join operation is by concatenating a list-of-lists to a single list,

and its unit assigns to an element of $S$ the list consisting of that single element:

The Eilenberg-Moore category of modules over the list monad is the category of monoids $Mon$:

Related pages

• monoid, free monoid

• list, string (computer science)

• writer monad

• nondeterministic computation

References

Discussion of the list monad as a monad in computer science (in Haskell):

• Philip Wadler, §2.1 in: Comprehending Monads, in: Conference on Lisp and functional programming, ACM Press (1990) [pdf, doi:10.1145/91556.91592]

• Philip Wadler, §5.1 in: Monads for functional programming, in M. Broy (eds.) Program Design Calculi NATO ASI Series, 118 Springer (1992) [doi;10.1007/978-3-662-02880-3_8, pdf]

• Philip Wadler, §2.7 in: The essence of functional programming, POPL ‘92: Principles of programming languages (1992) 1-14 [doi:10.1145/143165.143169, pdf]

• Bartosz Milewski, The List Monad, School of Haskell (2014) [web]

• Bartosz Milewski, pp. 304 in: Category Theory for Programmers, Blurb (2019) [pdf, github, webpage, ISBN:9780464243878]