Snoc trees: growing trees from the leaves

Neil Ghani; Fredrik Nordvall Forsberg; Samuel Fish

Snoc trees: growing trees from the leaves

Research output: Contribution to conference › Paper › peer-review

Abstract

We introduce snoc-trees which generalise snoc-lists, i.e., backwards lists where new elements are added at the back rather than at the front of the list. We uncover the categorical and computational structure of snoc-trees using both functorial and container-theoretic approaches, and show the power of their associated fold operator. We relate snoc-trees to the usual trees arising from initial algebra semantics, and demonstrate the use of snoc-trees via an example arising from a type theoretic variant of compositional sampling from a probability distribution.

Original language	English
Number of pages	14
Publication status	Published - 6 Jul 2026
Event	9th International Conference on Applied Category Theory - Tallinn, Tallinn, Estonia Duration: 6 Jul 2026 → 10 Jul 2026 Conference number: 9 https://actconf2026.github.io/

Conference

Conference	9th International Conference on Applied Category Theory
Abbreviated title	ACT
Country/Territory	Estonia
City	Tallinn
Period	6/07/26 → 10/07/26
Internet address	https://actconf2026.github.io/

Keywords

snoc tees
snoc lists
semantics

Cite this

@conference{14070fa92fff44b1b98c868116a297ae,

title = "Snoc trees: growing trees from the leaves",

abstract = "We introduce snoc-trees which generalise snoc-lists, i.e., backwards lists where new elements are added at the back rather than at the front of the list. We uncover the categorical and computational structure of snoc-trees using both functorial and container-theoretic approaches, and show the power of their associated fold operator. We relate snoc-trees to the usual trees arising from initial algebra semantics, and demonstrate the use of snoc-trees via an example arising from a type theoretic variant of compositional sampling from a probability distribution.",

keywords = "snoc tees, snoc lists, semantics",

author = "Neil Ghani and \{Nordvall Forsberg\}, Fredrik and Samuel Fish",

year = "2026",

month = jul,

day = "6",

language = "English",

note = "9th International Conference on Applied Category Theory, ACT ; Conference date: 06-07-2026 Through 10-07-2026",

url = "https://actconf2026.github.io/",

}

TY - CONF

T1 - Snoc trees

T2 - 9th International Conference on Applied Category Theory

AU - Ghani, Neil

AU - Nordvall Forsberg, Fredrik

AU - Fish, Samuel

N1 - Conference code: 9

PY - 2026/7/6

Y1 - 2026/7/6

N2 - We introduce snoc-trees which generalise snoc-lists, i.e., backwards lists where new elements are added at the back rather than at the front of the list. We uncover the categorical and computational structure of snoc-trees using both functorial and container-theoretic approaches, and show the power of their associated fold operator. We relate snoc-trees to the usual trees arising from initial algebra semantics, and demonstrate the use of snoc-trees via an example arising from a type theoretic variant of compositional sampling from a probability distribution.

AB - We introduce snoc-trees which generalise snoc-lists, i.e., backwards lists where new elements are added at the back rather than at the front of the list. We uncover the categorical and computational structure of snoc-trees using both functorial and container-theoretic approaches, and show the power of their associated fold operator. We relate snoc-trees to the usual trees arising from initial algebra semantics, and demonstrate the use of snoc-trees via an example arising from a type theoretic variant of compositional sampling from a probability distribution.

KW - snoc tees

KW - snoc lists

KW - semantics

UR - https://actconf2026.github.io/index.html

UR - https://www.eptcs.org/

M3 - Paper

Y2 - 6 July 2026 through 10 July 2026

ER -

Snoc trees: growing trees from the leaves

Abstract

Conference

Keywords

Other files and links

Embargoed Document

Fingerprint

Cite this