From: Ramakrishnan Muthukrishnan <ram@rkrishnan.org>
Date: Tue, 23 Dec 2014 13:02:46 +0000 (+0530)
Subject: lecture 7: folds and monoids
X-Git-Url: https://git.rkrishnan.org/?p=yorgey.git;a=commitdiff_plain;h=ed2eed0f94eb01dbb95ad6d14317f41196c74a3f

lecture 7: folds and monoids
---

diff --git a/misc/monoids.hs b/misc/monoids.hs
new file mode 100644
index 0000000..848dab9
--- /dev/null
+++ b/misc/monoids.hs
@@ -0,0 +1,48 @@
+module Monoids where
+
+import Data.Monoid
+
+data Tree a = Empty
+            | Node (Tree a) a (Tree a)
+              deriving (Eq, Show)
+                       
+leaf :: a -> Tree a
+leaf x = Node Empty x Empty
+
+treeSize :: Tree a -> Integer
+treeSize Empty = 0
+treeSize (Node l _ r) = 1 + treeSize l + treeSize r
+
+treeSum :: Tree Integer -> Integer
+treeSum Empty = 0
+treeSum (Node l x r) = x + treeSum l + treeSum r
+
+treeDepth :: Tree a -> Integer
+treeDepth Empty = 0
+treeDepth (Node l _ r) = 1 + max (treeDepth l) (treeDepth r)
+
+flatten :: Tree a -> [a]
+flatten Empty = []
+flatten (Node l x r) = flatten l ++ [x] ++ flatten r
+
+-- treeFold
+-- 0. empty case value
+-- 1. type of the return value.
+-- 2. how to combine the recursive calls.
+
+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)
+
+treeSize' :: Tree a -> Integer
+treeSize' = treeFold 0 (\l _ r -> 1 + l + r)
+
+treeSum' :: Tree Integer -> Integer
+treeSum' = treeFold 0 (\l x r -> x + l + r)
+
+treeDepth' :: Tree a -> Integer
+treeDepth' = treeFold 0 (\l _ r -> 1 + max l r)
+
+flatten' :: Tree a -> [a]
+flatten' = treeFold [] (\l x r -> l ++ [x] ++ r)
+