# Functional Programming - Fold [[Functional Programming]] Fold is an ubiquitous operation. It is closely linked to [[Monoid]], and monoids are ubiquitous in our thinking. > [!quote] The Foldable class represents data structures that can be reduced to a summary value one element at a time. Strict left-associative folds are a good fit for space-efficient reduction, while lazy right-associative folds are a good fit for corecursive iteration, or for folds that short-circuit after processing an initial subsequence of the structure's elements. > [Data.Foldable](https://hackage.haskell.org/package/base-4.17.0.0/docs/Data-Foldable.html) ## Haskell The definition of Foldable in [[Haskell]], goes into quite a bit of detail: - [Haskell/Foldable - Wikibooks, open books for an open world](https://en.wikibooks.org/wiki/Haskell/Foldable) - [Foldable and Traversable - HaskellWiki](https://wiki.haskell.org/Foldable_and_Traversable) ## See also - [[DRAFT - 2022-05-31 - The surprising link between UX design, redux, functional programming, event sourcing, accounting and E-Commerce 1]]. - [[2022-08-23 - Category Theory Catacombs - Week 3#Are state machines monoids]] ## Links This seems to be exactly the discussion I was looking for when fielding [[2022-08-23 - Category Theory Catacombs - Week 3]]: - [haskell - Foldable, Monoid and Monad - Stack Overflow](https://stackoverflow.com/questions/39951758/foldable-monoid-and-monad) This video shows all the different places Foldables appear. - [[VIDEO - Beautiful Folds - Video]] This article describes how beginners think that `fold` is mostly about reducing lists. Experts think of it as a way to consume a data structure into a single value. It says that fold is a "lossless interface" because we can pass fold a function that recreates the original input. - [Haskell for all: Folds are constructor substitution](https://www.haskellforall.com/2021/02/folds-are-constructor-substitution.html?m=1) I'm actually not sure if this is relevant at all. It was linked here before [[2022-08-27]], but I don't know why I added it. - [John Baez: "Symmetric Monoidal Categories A Rosetta Stone" - YouTube](https://www.youtube.com/watch?v=DAGJw7YBy8E) The canonical article by [[Graham Hutton]] about the universality of fold: - [https://www.cs.nott.ac.uk/~pszgmh/fold.pdf](https://www.cs.nott.ac.uk/~pszgmh/fold.pdf) ## Logs [[2022-08-27]] - Cleanup of the definition, cleanup of the links