Theory

In type theory and functional programming, abstract lists are usually defined inductively by two operations: nil that yields the empty list, and cons, which adds an item at the beginning of a list.

The list type forms a monad with the following functions (using E* rather than L to represent monomorphic lists with elements of type E):

return : A → A ∗ = a ↦ cons a nil {\displaystyle {\text{return}}\colon A\to A^{*}=a\mapsto {\text{cons}}\,a\,{\text{nil}}}

bind : A ∗ → ( A → B ∗ ) → B ∗ = l ↦ f ↦ { nil if   l = nil append ( f a ) ( bind l ′ f ) if   l = cons a l ′ {\displaystyle {\text{bind}}\colon A^{*}\to (A\to B^{*})\to B^{*}=l\mapsto f\mapsto {\begin{cases}{\text{nil}}&{\text{if}}\ l={\text{nil}}\\{\text{append}}\,(f\,a)\,({\text{bind}}\,l'\,f)&{\text{if}}\ l={\text{cons}}\,a\,l'\end{cases}}}

where append is defined as:

append : A ∗ → A ∗ → A ∗ = l 1 ↦ l 2 ↦ { l 2 if   l 1 = nil cons a ( append l 1 ′ l 2 ) if   l 1 = cons a l 1 ′ {\displaystyle {\text{append}}\colon A^{*}\to A^{*}\to A^{*}=l_{1}\mapsto l_{2}\mapsto {\begin{cases}l_{2}&{\text{if}}\ l_{1}={\text{nil}}\\{\text{cons}}\,a\,({\text{append}}\,l_{1}'\,l_{2})&{\text{if}}\ l_{1}={\text{cons}}\,a\,l_{1}'\end{cases}}}

Alternatively, the monad may be defined in terms of operations return, fmap and join, with:

fmap : ( A → B ) → ( A ∗ → B ∗ ) = f ↦ l ↦ { nil if   l = nil cons ( f a ) ( fmap f l ′ ) if   l = cons a l ′ {\displaystyle {\text{fmap}}\colon (A\to B)\to (A^{*}\to B^{*})=f\mapsto l\mapsto {\begin{cases}{\text{nil}}&{\text{if}}\ l={\text{nil}}\\{\text{cons}}\,(f\,a)({\text{fmap}}f\,l')&{\text{if}}\ l={\text{cons}}\,a\,l'\end{cases}}}

join : A ∗ ∗ → A ∗ = l ↦ { nil if   l = nil append a ( join l ′ ) if   l = cons a l ′ {\displaystyle {\text{join}}\colon {A^{*}}^{*}\to A^{*}=l\mapsto {\begin{cases}{\text{nil}}&{\text{if}}\ l={\text{nil}}\\{\text{append}}\,a\,({\text{join}}\,l')&{\text{if}}\ l={\text{cons}}\,a\,l'\end{cases}}}

Copyright © 2021 List
Powered by List