Folding Cheat Sheet # 9 - List Unfolding 𝑢𝑛𝑓𝑜𝑙𝑑 as the Computational Dual of 𝑓𝑜𝑙𝑑 and how 𝑢𝑛𝑓𝑜𝑙𝑑 relates to 𝑖𝑡𝑒𝑟𝑎𝑡𝑒

In this deck we look at the following:
* How unfolding lists is the computational dual of folding lists
* Different variants of the function for unfolding lists
* How they relate to the iterate function

Keywords: "folding","unfolding","fold","unfold","fold'","unfold'","iterate","anamorphism","catamorphism","infinite list","lazy list","functional programming","scala","haskell"

Transcript

1. CHEAT-SHEET Folding #9 ∶ / \ 𝒂𝟎 ∶ / \ 𝒂𝟏 ∶ / \ 𝒂𝟐 ∶ / \ 𝒂𝟑 𝒇 / \ 𝒂𝟎 𝒇 / \ 𝒂𝟏 𝒇 / \ 𝒂𝟐 𝒇 / \ 𝒂𝟑 𝒆 List Unfolding 𝑢𝑛𝑓𝑜𝑙𝑑 as the Computational Dual of 𝑓𝑜𝑙𝑑 and how 𝑢𝑛𝑓𝑜𝑙𝑑 relates to 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 @philip_schwarz slides by https://fpilluminated.org/
2. This cheat sheet is based on the following deck, which it aims to condense, partly by focusing on a single running example, and partly by choosing, rather than to provide excerpts from referenced sources, to simply present salient points made by the sources. @philip_schwarz
3. Here is a function called digits which takes an integer number, and returns a list of integers corresponding to the number’s digits (yes, we are not handling cases like n=0 or negative n). The digits function makes use of a function called iterate. See the next two slides for the Haskell and Scala definitions of iterate. The Haskell version of digits is defined in point-free style, uses the function composition function, and uses backticks to specify the infix version of functions mod and div. If you find it at all cryptic, see the slide after the next two for alternative definitions that are less succinct. digits :: Int -> [Int] digits = reverse . map (`mod` 10) . takeWhile (/= 0) . iterate (`div` 10) def digits(n: Int): List[Int] = LazyList.iterate(n)(_ / 10 ) .takeWhile(_ != 0) .map( _ % 10 ) .toList .reverse 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 ∷ 𝛼 → 𝛼 → 𝛼 → 𝛼 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑓 𝑥 = 𝑥 ∶ 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑓 (𝑓 𝑥) > digits 2718 [2,7,1,8] scala> digits(2718) val res0: List[Int] = List(2, 7, 1, 8)
4. 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 ∷ 𝛼 → 𝛼 → 𝛼 → 𝛼 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑓 𝑥 = 𝑥 ∶ 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑓 (𝑓 𝑥)
5. 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 ∷ 𝛼 → 𝛼 → 𝛼 → 𝛼 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑓 𝑥 = 𝑥 ∶ 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑓 (𝑓 𝑥)
6. digits :: Int -> [Int] digits n = reverse ( map (\x -> mod x 10) ( takeWhile (\x -> x /= 0) ( iterate (\x -> div x 10) n ) ) ) digits :: Int -> [Int] digits n = reverse $ map (\x -> mod x 10) $ takeWhile (\x -> x > 0) $ iterate (\x -> div x 10) $ n digits :: Int -> [Int] digits n = n & iterate (\x -> div x 10) & takeWhile (\x -> x > 0) & map (\x -> mod x 10) & reverse digits :: Int -> [Int] digits = reverse . map (\x -> mod x 10) . takeWhile (\x -> x > 0) . iterate (\x -> div x 10) digits :: Int -> [Int] digits n = n & iterate (`div` 10) & takeWhile (/= 0) & map (`mod` 10) & reverse digits :: Int -> [Int] digits n = reverse $ map (`mod` 10) $ takeWhile (/= 0) $ iterate (`div` 10) $ n digits :: Int -> [Int] digits n = reverse ( map (`mod` 10) ( takeWhile (/= 0) ( iterate (`div` 10) n ) ) ) digits :: Int -> [Int] digits = reverse . map (`mod` 10) . takeWhile (/= 0) . iterate (`div` 10)
7. If you would like to know more about how the digits function works then see either the following deck, or the one mentioned at the beginning of this deck.
8. digits :: Int -> [Int] digits = reverse . map (`mod` 10) . takeWhile (/= 0) . iterate (`div` 10) def digits(n: Int): List[Int] = LazyList iterate(n)(_ / 10) .takeWhile (_ != 0) .map (_ % 10) .toList .reverse The digits function composes map, takeWhile and iterate in sequence. One often finds such a pattern of computation, which may be captured as a generic function called unfold. 𝑢𝑛𝑓𝑜𝑙𝑑 ∷ (𝛽 → 𝛼) → 𝛽 → 𝑩𝒐𝒐𝒍 → (𝛽 → 𝛽) → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 𝑢𝑛𝑓𝑜𝑙𝑑 ℎ 𝑝 𝑡 = 𝑚𝑎𝑝 ℎ ∘ 𝑡𝑎𝑘𝑒𝑤ℎ𝑖𝑙𝑒 𝑝 ∘ 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑡 unfold :: (b -> a) -> (b -> Bool) -> (b -> b) -> b -> [a] unfold h p t = map h . takeWhile p . iterate t def unfold[A,B](h: B => A, p: B => Boolean, t: B => B, b: B): LazyList[A] = LazyList.iterate(b)(t).takeWhile(p).map(h)
9. digits :: Int -> [Int] digits = reverse . unfold (`mod` 10) (/= 0) (`div` 10) def digits(n: Int): List[Int] = unfold[Int,Int](_ % 10, _ != 0, _ / 10, n).toList.reverse digits :: Int -> [Int] digits = reverse . map (`mod` 10) . takeWhile (/= 0) . iterate (`div` 10) def digits(n: Int): List[Int] = LazyList iterate(n)(_ / 10) .takeWhile (_ != 0) .map (_ % 10) .toList .reverse Let’s simplify the implementation of digits using the unfold function. 𝑢𝑛𝑓𝑜𝑙𝑑 ∷ (𝛽 → 𝛼) → 𝛽 → 𝑩𝒐𝒐𝒍 → (𝛽 → 𝛽) → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 𝑢𝑛𝑓𝑜𝑙𝑑 ℎ 𝑝 𝑡 = 𝑚𝑎𝑝 ℎ ∘ 𝑡𝑎𝑘𝑒𝑤ℎ𝑖𝑙𝑒 𝑝 ∘ 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑡
10. Here is a more efficient variant of unfold that fuses together the map, takewhile and iterate. The signature is slightly different in that there is some renaming and reordering of parameters, and the condition tested by predicate function 𝑝 is inverted. 𝑢𝑛𝑓𝑜𝑙𝑑 ∷ 𝛽 → 𝑩𝒐𝒐𝒍 → (𝛽 → 𝛼) → (𝛽 → 𝛽) → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 𝑢𝑛𝑓𝑜𝑙𝑑 𝑝 𝑓 𝑔 𝑏 = 𝐢𝐟 𝑝 𝑏 𝐭𝐡𝐞𝐧 𝑵𝒊𝒍 𝐞𝐥𝐬𝐞 𝑪𝒐𝒏𝒔 (𝑓 𝑏) (𝑢𝑛𝑓𝑜𝑙𝑑 𝑝 𝑓 𝑔 (𝑔 𝑏)) 𝑢𝑛𝑓𝑜𝑙𝑑 ∷ (𝛽 → 𝛼) → 𝛽 → 𝑩𝒐𝒐𝒍 → (𝛽 → 𝛽) → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 𝑢𝑛𝑓𝑜𝑙𝑑 ℎ 𝑝 𝑡 = 𝑚𝑎𝑝 ℎ ∘ 𝑡𝑎𝑘𝑒𝑤ℎ𝑖𝑙𝑒 𝑝 ∘ 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑡 digits :: Int -> [Int] digits = reverse . unfold (== 0) (`mod` 10) (`div` 10) digits :: Int -> [Int] digits = reverse . unfold (`mod` 10) (/= 0) (`div` 10) def digits(n: Int): List[Int] = unfold[Int,Int](_ == 0, _ % 10, _ / 10, n).toList.reverse def digits(n: Int): List[Int] = unfold[Int,Int](_ % 10, _ != 0, _ / 10, n).toList.reverse
11. 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 ∷ 𝛼 → 𝛼 → 𝛼 → 𝛼 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑓 = 𝑢𝑛𝑓𝑜𝑙𝑑 𝑐𝑜𝑛𝑠𝑡 𝐹𝑎𝑙𝑠𝑒 𝑖𝑑 𝑓 Just for completeness, here is how iterate can be defined in terms of unfold. 𝑢𝑛𝑓𝑜𝑙𝑑 ∷ 𝛽 → 𝑩𝒐𝒐𝒍 → (𝛽 → 𝛼) → (𝛽 → 𝛽) → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 𝑢𝑛𝑓𝑜𝑙𝑑 𝑝 𝑓 𝑔 𝑏 = 𝐢𝐟 𝑝 𝑏 𝐭𝐡𝐞𝐧 𝑵𝒊𝒍 𝐞𝐥𝐬𝐞 𝑪𝒐𝒏𝒔 (𝑓 𝑏) (𝑢𝑛𝑓𝑜𝑙𝑑 𝑝 𝑓 𝑔 (𝑔 𝑏)) 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 ∷ 𝛼 → 𝛼 → 𝛼 → 𝛼 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑓 𝑥 = 𝑥 ∶ 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑓 (𝑓 𝑥)
12. 𝑢𝑛𝑓𝑜𝑙𝑑 ∷ 𝛽 → 𝑩𝒐𝒐𝒍 → (𝛽 → 𝛼) → (𝛽 → 𝛽) → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 𝑢𝑛𝑓𝑜𝑙𝑑 𝑝 𝑓 𝑔 𝑏 = 𝐢𝐟 𝑝 𝑏 𝐭𝐡𝐞𝐧 𝑵𝒊𝒍 𝐞𝐥𝐬𝐞 𝑪𝒐𝒏𝒔 (𝑓 𝑏) (𝑢𝑛𝑓𝑜𝑙𝑑 𝑝 𝑓 𝑔 (𝑔 𝑏)) The unfold function is not available in Haskell and Scala. What is available, is an alternative variant which (for reasons that will become apparent later) we shall refer to as unfold’. In Haskell, unfold’ is called unfoldr (a right unfold). In Scala it is called unfold. Let’s reimplement digits using the unfold’ function. 𝑢𝑛𝑓𝑜𝑙𝑑′ ∷ 𝛽 → 𝑴𝒂𝒚𝒃𝒆 (𝛼, 𝛽) → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 𝑢𝑛𝑓𝑜𝑙𝑑′ 𝑓 𝑢 = 𝐜𝐚𝐬𝐞 𝑓 𝑢 𝐨𝐟 𝑵𝒐𝒕𝒉𝒊𝒏𝒈 → 𝑵𝒊𝒍 𝑱𝒖𝒔𝒕 (𝑥, 𝑣) → 𝑪𝒐𝒏𝒔 𝑥 (𝑢𝑛𝑓𝑜𝑙𝑑′ 𝑓 𝑣) unfoldr unfold digits :: Int -> [Int] digits = reverse . unfoldr gen where gen 0 = Nothing gen d = Just (d `mod` 10, d `div` 10) def digits(n: Int): List[Int] = LazyList.unfold(n): case 0 => None case x => Some(x % 10, x / 10) .toList.reverse digits :: Int -> [Int] digits = reverse . unfold (== 0) (`mod` 10) (`div` 10) def digits(n: Int): List[Int] = unfold[Int,Int](_ == 0, _ % 10, _ / 10, n).toList.reverse
13. The next two slides show Haskell and Scala documentation for their equivalent of 𝑢𝑛𝑓𝑜𝑙𝑑′.
14. 𝑢𝑛𝑓𝑜𝑙𝑑′ ∷ 𝛽 → 𝑴𝒂𝒚𝒃𝒆 (𝛼, 𝛽) → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 𝑢𝑛𝑓𝑜𝑙𝑑′ 𝑓 𝑢 = 𝐜𝐚𝐬𝐞 𝑓 𝑢 𝐨𝐟 𝑵𝒐𝒕𝒉𝒊𝒏𝒈 → 𝑵𝒊𝒍 𝑱𝒖𝒔𝒕 (𝑥, 𝑣) → 𝑪𝒐𝒏𝒔 𝑥 (𝑢𝑛𝑓𝑜𝑙𝑑′ 𝑓 𝑣) The function passed to unfoldr takes a seed value that it uses either to generate Nothing or to generate both a new result item and a new seed value. unfoldr unfold
15. 𝑢𝑛𝑓𝑜𝑙𝑑′ ∷ 𝛽 → 𝑴𝒂𝒚𝒃𝒆 (𝛼, 𝛽) → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 𝑢𝑛𝑓𝑜𝑙𝑑′ 𝑓 𝑢 = 𝐜𝐚𝐬𝐞 𝑓 𝑢 𝐨𝐟 𝑵𝒐𝒕𝒉𝒊𝒏𝒈 → 𝑵𝒊𝒍 𝑱𝒖𝒔𝒕 (𝑥, 𝑣) → 𝑪𝒐𝒏𝒔 𝑥 (𝑢𝑛𝑓𝑜𝑙𝑑′ 𝑓 𝑣) The function passed to unfold takes a state value that it uses either to generate None or to generate both a new result item and a new state value. unfoldr unfold
16. 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 ∷ 𝛼 → 𝛼 → 𝛼 → 𝛼 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑓 = 𝑢𝑛𝑓𝑜𝑙𝑑′ 𝜆𝑥. 𝑱𝒖𝒔𝒕 (𝑥, 𝑓 𝑥) Just for completeness, here is how iterate can be defined in terms of unfold’. 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 ∷ 𝛼 → 𝛼 → 𝛼 → 𝛼 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑓 𝑥 = 𝑥 ∶ 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑓 (𝑓 𝑥) 𝑢𝑛𝑓𝑜𝑙𝑑′ ∷ 𝛽 → 𝑴𝒂𝒚𝒃𝒆 (𝛼, 𝛽) → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 𝑢𝑛𝑓𝑜𝑙𝑑′ 𝑓 𝑢 = 𝐜𝐚𝐬𝐞 𝑓 𝑢 𝐨𝐟 𝑵𝒐𝒕𝒉𝒊𝒏𝒈 → 𝑵𝒊𝒍 𝑱𝒖𝒔𝒕 (𝑥, 𝑣) → 𝑪𝒐𝒏𝒔 𝑥 (𝑢𝑛𝑓𝑜𝑙𝑑′ 𝑓 𝑣) unfoldr unfold
17. The dual of the digits function is the decimal function, which given a list of digits, returns the integer number with such digits. As seen below, the decimal function is neatly and efficiently implemented using a left fold (if you want to know more then see folding cheat-sheet #4). decimal :: [Int] -> Int decimal = foldl (⊕) 0 (⊕) :: Int -> Int -> Int n ⊕ d = 10 * n + d def decimal(ds: List[Int]): Int = ds.foldLeft(0)(_⊕_) extension (n: Int) def ⊕(d Int): Int = 10 * n + d > decimal(List(2,7,1,8)) val res0: Int = 2718 > decimal [2,7,1,8] 2718
18. Given the following… • decimal is the computational dual of digits • decimal can be implemented using unfold’ (a right unfold) • the computational dual of unfold’ is fold’ (a right fold) …let’s see if decimal can be implemented using fold’. Because fold’ is not available in Haskell and Scala, we implement it ourselves. 𝑢𝑛𝑓𝑜𝑙𝑑′ ∷ 𝛽 → 𝑴𝒂𝒚𝒃𝒆 (𝛼, 𝛽) → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 𝑢𝑛𝑓𝑜𝑙𝑑′ 𝑓 𝑢 = 𝐜𝐚𝐬𝐞 𝑓 𝑢 𝐨𝐟 𝑵𝒐𝒕𝒉𝒊𝒏𝒈 → 𝑵𝒊𝒍 𝑱𝒖𝒔𝒕 (𝑥, 𝑣) → 𝑪𝒐𝒏𝒔 𝑥 (𝑢𝑛𝑓𝑜𝑙𝑑′ 𝑓 𝑣) 𝑓𝑜𝑙𝑑′ ∷ (𝑴𝒂𝒚𝒃𝒆 (𝛼, 𝛽) → 𝛽) → 𝑳𝒊𝒔𝒕 𝛼 → 𝛽 𝑓𝑜𝑙𝑑′ 𝑓 𝑵𝒊𝒍 = 𝑓 𝑵𝒐𝒕𝒉𝒊𝒏𝒈 𝑓𝑜𝑙𝑑′ 𝑓 𝑪𝒐𝒏𝒔 𝑥 𝑥𝑠 = 𝑓 (𝑱𝒖𝒔𝒕 𝑥, 𝑓𝑜𝑙𝑑′ 𝑓 𝑥𝑠) unfoldr unfold dual dual digits :: Int -> [Int] digits = reverse . unfoldr gen where gen 0 = Nothing gen d = Just (d `mod` 10, d `div` 10) def digits(n: Int): List[Int] = LazyList.unfold(n): case 0 => None case x => Some(x % 10, x / 10) .toList.reverse dual fold' :: (Maybe (a, b) -> b) -> [a] -> b fold' f [] = f Nothing fold' f (x:xs) = f (Just (x, fold' f xs)) decimal :: [Int] -> Int decimal = fst . fold' f where f Nothing = (0, 0) f (Just (d, (n,e))) = (d * (10 ^ e) + n, e + 1) def decimal(ds: List[Int]): Int = foldp[Int,(Int,Int)](ds){ case None => (0,0) case Some(d, (n, e)) => (d * (pow(10, e)).toInt + n, e + 1) }(0) def foldp[A,B](as: List[A])(f: Option[(A,B)] => B): B = as match case Nil => f(None) case x :: xs => f(Option(x, foldp(xs)(f))) decimal digits duals 𝑢𝑛𝑓𝑜𝑙𝑑′ 𝑓𝑜𝑙𝑑′ duals uses uses
19. Let’s now switch from fold’ to the more customary right fold, which is provided by Haskell and Scala. 𝑓𝑜𝑙𝑑′ ∷ (𝑴𝒂𝒚𝒃𝒆 (𝛼, 𝛽) → 𝛽) → 𝑳𝒊𝒔𝒕 𝛼 → 𝛽 𝑓𝑜𝑙𝑑′ 𝑓 𝑵𝒊𝒍 = 𝑓 𝑵𝒐𝒕𝒉𝒊𝒏𝒈 𝑓𝑜𝑙𝑑′ 𝑓 𝑪𝒐𝒏𝒔 𝑥 𝑥𝑠 = 𝑓 (𝑱𝒖𝒔𝒕 𝑥, 𝑓𝑜𝑙𝑑′ 𝑓 𝑥𝑠) 𝑓𝑜𝑙𝑑 ∷ 𝛼 → 𝛽 → 𝛽 → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 → 𝛽 𝑓𝑜𝑙𝑑 𝑓 𝑒 𝑵𝒊𝒍 = 𝑒 𝑓𝑜𝑙𝑑 𝑓 𝑒 𝑪𝒐𝒏𝒔 𝑥 𝑥𝑠 = 𝑓 𝑥 𝑓𝑜𝑙𝑑 𝑓 𝑒 𝑥𝑠 foldr foldRight decimal :: [Int] -> Int decimal = fst . foldr f (0, 0) where f d (n, e) = (d * (10 ^ e) + n, e + 1) decimal :: [Int] -> Int decimal = fst . fold' f where f Nothing = (0, 0) f (Just (d, (n,e))) = (d * (10 ^ e) + n, e + 1) def decimal(ds: List[Int]): Int = foldp[Int,(Int,Int)](ds){ case None => (0,0) case Some(d, (n, e)) => (d * (pow(10, e)).toInt + n, e + 1) }(0) def decimal(ds: List[Int]): Int = ds.foldRight(0,0){ case (d, (n, e)) => (d * (pow(10, e)).toInt + n, e + 1) }(0)
20. digits = reverse . map (`mod` 10) . takeWhile (/= 0) . iterate (`div` 10) digits = reverse . unfold (`mod` 10) (/= 0) (`div` 10) digits = reverse . unfold (== 0) (`mod` 10) (`div` 10) digits = reverse . unfoldr gen where gen 0 = Nothing gen d = Just (d `mod` 10, d `div` 10) def digits(n: Int): List[Int] = LazyList iterate(n)(_ / 10 ).takeWhile(_ != 0).map( _ % 10 ).toList.reverse def digits(n: Int): List[Int] = unfold[Int,Int](_ % 10, _ != 0, _ / 10, n).toList.reverse def digits(n: Int): List[Int] = unfold[Int,Int](_ == 0, _ % 10, _ / 10, n).toList.reverse def digits(n: Int): List[Int] = def digits(n: Int): List[Int] = LazyList.unfold(n): LazyList.unfold(n): x => case 0 => None Option.unless(x==0)(x % 10, x / 10) case x => Some(x % 10, x / 10) .toList.reverse .toList.reverse Here are the four different implementations of digits that we have considered. 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑢𝑛𝑓𝑜𝑙𝑑 𝑣1 𝑢𝑛𝑓𝑜𝑙𝑑 𝑣2 𝑢𝑛𝑓𝑜𝑙𝑑′ 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑢𝑛𝑓𝑜𝑙𝑑 𝑣1 𝑢𝑛𝑓𝑜𝑙𝑑 𝑣2 𝑢𝑛𝑓𝑜𝑙𝑑′
21. decimal = foldl (⊕) 0 n ⊕ d = 10 * n + d decimal = fst . fold' f where f Nothing = (0, 0) f (Just (d, (n,e))) = (d * (10 ^ e) + n, e + 1) decimal = fst . foldr f (0, 0) where f d (n, e) = (d * (10 ^ e) + n, e + 1) def decimal(ds: List[Int]): Int = ds.foldLeft(0)(_⊕_) extension (n: Int) def ⊕(d Int): Int = 10 * n + d def decimal(ds: List[Int]): Int = foldp[Int,(Int,Int)](ds){ case None => (0,0) case Some(d, (n, e)) => (d * (pow(10, e)).toInt + n, e + 1) }(0) def decimal(ds: List[Int]): Int = ds.foldRight(0,0){ case (d, (n, e)) => (d * (pow(10, e)).toInt + n, e + 1) }(0) And here are the three different implementations of decimal that we have considered. 𝑙𝑒𝑓𝑡 𝑓𝑜𝑙𝑑 𝑓𝑜𝑙𝑑′ 𝑓𝑜𝑙𝑑 𝑙𝑒𝑓𝑡 𝑓𝑜𝑙𝑑 𝑓𝑜𝑙𝑑′ 𝑓𝑜𝑙𝑑
22. The next slide is the penultimate one and suggests that • the introduction of fold’ and unfold’ makes the duality between folding and unfolding very clear • the names of fold’ and unfold’ are primed because the two functions are less convenient for programming than fold and unfold. The slide after that is the last one and introduces the terms catamorphism and anamorphism.
23. 𝑢𝑛𝑓𝑜𝑙𝑑′ ∷ 𝛽 → 𝑴𝒂𝒚𝒃𝒆 (𝛼, 𝛽) → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 𝑢𝑛𝑓𝑜𝑙𝑑′ 𝑓 𝑢 = 𝐜𝐚𝐬𝐞 𝑓 𝑢 𝐨𝐟 𝑵𝒐𝒕𝒉𝒊𝒏𝒈 → 𝑵𝒊𝒍 𝑱𝒖𝒔𝒕 (𝑥, 𝑣) → 𝑪𝒐𝒏𝒔 𝑥 (𝑢𝑛𝑓𝑜𝑙𝑑′ 𝑓 𝑣) 𝑢𝑛𝑓𝑜𝑙𝑑 ∷ 𝛽 → 𝑩𝒐𝒐𝒍 → (𝛽 → 𝛼) → (𝛽 → 𝛽) → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 𝑢𝑛𝑓𝑜𝑙𝑑 𝑝 𝑓 𝑔 𝑏 = 𝐢𝐟 𝑝 𝑏 𝐭𝐡𝐞𝐧 𝑵𝒊𝒍 𝐞𝐥𝐬𝐞 𝑪𝒐𝒏𝒔 (𝑓 𝑏) (𝑢𝑛𝑓𝑜𝑙𝑑 𝑝 𝑓 𝑔 (𝑔 𝑏)) 𝑓𝑜𝑙𝑑 ∷ 𝛼 → 𝛽 → 𝛽 → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 → 𝛽 𝑓𝑜𝑙𝑑 𝑓 𝑒 𝑵𝒊𝒍 = 𝑒 𝑓𝑜𝑙𝑑 𝑓 𝑒 𝑪𝒐𝒏𝒔 𝑥 𝑥𝑠 = 𝑓 𝑥 𝑓𝑜𝑙𝑑 𝑓 𝑒 𝑥𝑠 𝑓𝑜𝑙𝑑′ ∷ (𝑴𝒂𝒚𝒃𝒆 (𝛼, 𝛽) → 𝛽) → 𝑳𝒊𝒔𝒕 𝛼 → 𝛽 𝑓𝑜𝑙𝑑′ 𝑓 𝑵𝒊𝒍 = 𝑓 𝑵𝒐𝒕𝒉𝒊𝒏𝒈 𝑓𝑜𝑙𝑑′ 𝑓 𝑪𝒐𝒏𝒔 𝑥 𝑥𝑠 = 𝑓 (𝑱𝒖𝒔𝒕 𝑥, 𝑓𝑜𝑙𝑑′ 𝑓 𝑥𝑠) 𝑴𝒂𝒚𝒃𝒆 (𝛼, 𝛽) 𝛽 𝑳𝒊𝒔𝒕 𝛼 𝑓 𝑢𝑛𝑓𝑜𝑙𝑑′ 𝑓 𝑳𝒊𝒔𝒕 𝛼 𝑓𝑜𝑙𝑑′ 𝑓 𝛽 𝑴𝒂𝒚𝒃𝒆 (𝛼, 𝛽) 𝑓 While they may sometimes be less convenient for programming with, 𝑓𝑜𝑙𝑑′ and 𝑢𝑛𝑓𝑜𝑙𝑑′, the primed versions of 𝑓𝑜𝑙𝑑 and 𝑢𝑛𝑓𝑜𝑙𝑑, make the duality between the fold and the unfold very clear The two diagrams are based on ones in Conal Elliott’s deck Folds and Unfolds all around us: http://conal.net/talks/folds-and-unfolds.pdf foldr foldRight unfoldr unfold
24. 𝑢𝑛𝑓𝑜𝑙𝑑 ∷ 𝛽 → 𝑩𝒐𝒐𝒍 → (𝛽 → 𝛼) → (𝛽 → 𝛽) → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 𝑓𝑜𝑙𝑑 ∷ 𝛼 → 𝛽 → 𝛽 → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 → 𝛽 Functions that ‘destruct’ a list – they have been called catamorphisms, from the Greek proposition κατά, meaning ‘downwards’ as in ‘catastrophe’. Functions that ‘generate’ a list of items of type 𝛼 from a seed of type 𝛽 – they have been called anamorphisms, from the Greek proposition ἀνά, meaning ‘upwards’ as in ‘anabolism’. 𝑢𝑛𝑓𝑜𝑙𝑑′ ∷ 𝛽 → 𝑴𝒂𝒚𝒃𝒆 (𝛼, 𝛽) → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 𝑓𝑜𝑙𝑑′ ∷ (𝑴𝒂𝒚𝒃𝒆 (𝛼, 𝛽) → 𝛽) → 𝑳𝒊𝒔𝒕 𝛼 → 𝛽 unfoldr unfold Based on slightly modified versions of two sentences from the paper Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire Available here https://maartenfokkinga.github.io/utwente/mmf91m.pdf foldr foldRight