Список (абстрактний тип даних)

Тип списку утворює монаду з такими функціями (використано E*, а не L для відображення мономорфних списків з елементами типу Е):

${\displaystyle {\text{return}}\colon A\to A^{*}=a\mapsto {\text{cons}}\,a\,{\text{nil}}}$

${\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}}}$

де append визначається так:

${\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}}}$

Як альтернатива, монаду можна визначити в термінах операцій return, fmap та join:

${\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}}}$

${\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}}}$

Зверніть увагу, що fmap, join, append та bind чітко визначені, оскільки вони застосовуються до більш і більш глибоких аргументів за кожного рекурсивного виклику.

Тип списку є адитивною монадою, з nil, як монадичним нулем, і append, як монадичною сумою.

Списки утворюють моноїд відносно операції додавання. Одиничний елемент моноїда є порожній список, nil. Насправді, це вільний моноїд над множиною елементів списку.