From c3dd066e66f230a26988aac2c8ebebcc8f74c69e Mon Sep 17 00:00:00 2001
From: Edoardo La Greca
Date: Sun, 7 Sep 2025 21:18:56 +0200
Subject: add partial notes for lecture 7 (up to and excluding the "Monoids"
 section)

---
 lec07/notes.md | 56 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 56 insertions(+)
 create mode 100644 lec07/notes.md

diff --git a/lec07/notes.md b/lec07/notes.md
new file mode 100644
index 0000000..04b7640
--- /dev/null
+++ b/lec07/notes.md
@@ -0,0 +1,56 @@
+# Lecture 7: Folds and Monoids
+
+## Folds, again
+
+We've seen folds, how to use them, and how to implement them as well. However, so far we've only seen them working on lists. Not all data structures are lists, though! What if we needed to fold a tree? Although this section focuses on trees, the principles are appliable to data structures of any form.
+
+First of all, the definition of `Tree` and `leaf`:
+
+	data Tree a = Empty
+	            | Node (Tree a) a (Tree a)
+	  deriving (Show, Eq)
+
+	leaf :: a -> Tree a
+	leaf x = Node Empty x Empty
+
+Our starting point is going to be an ad hoc function to compute the size of a tree. In other words, we're going to calculate how many elements the tree has.
+
+	treeSize :: Tree a -> Integer
+	treeSize Empty = 0
+	treeSize (Node l _ r) = 1 + treeSize l + treeSize r
+
+What about flattening a tree into a list?
+
+	treeFlatten :: Tree a -> [a]
+	treeFlatten Empty = []
+	treeFlatten (Node l x r) = flatten l ++ [x] ++ flatten r
+
+Using just these two function definitions we can spot their differences and use this information to generalize and create a generic fold function for trees. What changes between them? We're going to create our fold for trees step by step below, by comparing each line of the two functions.
+
+Let's start with the first line of these two functions, specifically their type signature: both functions take a parameter of the same type (a generic `Tree`), which is the main subject of the computation, but they return entirely different things depending on what the computation itself actually does. We could say that, although they start at the same point, they travel and end up in substantially different places. This means that our generalized fold is going to have a `Tree` as one of its parameters, but the final return type is unknown. Note that the type of `Tree` and the return type are independent!
+
+	treeFold :: Tree a -> b
+
+Now, let's go on with the second line of these functions. Both do pattern matching on the `Empty` constructor and return something. However, since their final return type is unknown and depends on the computation, like we just said, this value is going to be specified as another parameter in the generic fold's type signature. It can't be otherwise!
+
+	treeFold :: b -> Tree a -> b
+	treeFold e Empty = e
+
+Finally, let's take a look at the third line. This is the case where the `Tree` is non-empty: the heart of our computation! In this part, the two functions behave completely differently. Since their behavior depends on the parameters of the `Node` constructor, it makes sense to replace such behavior with a function, rather than a value. After all those expressions *do* something, rather than *being* something. What is the type signature of this function going to be? The same as the `Node` constructor: a sub-tree, followed by a value, followed by another sub-tree.
+
+	treeFold :: b -> (b -> a -> b -> b) -> Tree a -> b
+	treeFold e _ Empty = e
+	treeFold e f (Node l x r) = f (treeFold e f l) x (treeFold e f r)
+
+If we rewrite `treeSize` and `treeFlatten` with our brand-new `treeFold`, we get:
+
+	treeSize' :: Tree a -> Integer
+	treeSize' = treeFold 0 (\l _ r -> 1 + l + r)
+
+	treeFlatten' :: Tree a -> [a]
+	treeFlatten' = treeFold [] (\l x r -> l ++ [x] ++ r)
+
+### Folds in general
+
+The reason why we just implemented a fold for trees is that folds are not necessarily restricted to lists, but they can be applied to many more data structures. In general, fold functions for any type `T` take one argument for each of `T`'s constructors, each being a function which instructs the fold about how to translate the respective constructor into a value suitable for the final result. Many functions are expressible as simple folds.
+
-- 
cgit v1.2.3