Folding Cheat Sheet #4

For functions that can be defined both as an instance of a right fold and as an instance of a left fold, one may be more efficient than the other.

Let's look at the example of a function 'decimal' that converts a list of digits into the corresponding decimal number.

Keywords: folding, list, right fold, left fold, recursion, tail recursion, universal property of fold, Horner’s rule.

1. CHEAT-SHEET Folding #4 ∶ / \ 𝒂𝟎 ∶ / \ 𝒂𝟏 ∶ / \ 𝒂𝟐 ∶ / \ 𝒂𝟑 𝒇 / \ 𝒂𝟎 𝒇 / \ 𝒂𝟏 𝒇 / \ 𝒂𝟐 𝒇 / \ 𝒂𝟑 𝒆 @philip_schwarz slides by https://fpilluminated.com/
2. We want to write function 𝒅𝒆𝒄𝒊𝒎𝒂𝒍, which given the digits of an integer number [𝑑0 , 𝑑1 , … , 𝑑𝑛 ] computes the integer value of the number - &'( ) 𝑑𝑘 ∗ 10)*& Thanks to the universal property of fold, if we are able to define 𝒅𝒆𝒄𝒊𝒎𝒂𝒍 so that its equations match those on the left hand side of the following equivalence, then we are also able to implement 𝒅𝒆𝒄𝒊𝒎𝒂𝒍 using a right fold i.e. given 𝑓𝑜𝑙𝑑𝑟 𝑓𝑜𝑙𝑑𝑟 :: 𝛼 → 𝛽 → 𝛽 → 𝛽 → 𝛼 → 𝛽 𝑓𝑜𝑙𝑑𝑟 𝑓 𝑣 = 𝑣 𝑓𝑜𝑙𝑑𝑟 𝑓 𝑣 𝑥 ∶ 𝑥𝑠 = 𝑓 𝑥 𝑓𝑜𝑙𝑑𝑟 𝑓 𝑣 𝑥𝑠 we can reimplement 𝒅𝒆𝒄𝒊𝒎𝒂𝒍 like this: 𝒅𝒆𝒄𝒊𝒎𝒂𝒍 = 𝑓𝑜𝑙𝑑𝑟 𝑓 𝑣 The universal property of 𝒇𝒐𝒍𝒅 𝒈 = 𝒗 ⟺ 𝒈 = 𝒇𝒐𝒍𝒅 𝒇 𝒗 𝒈 :: 𝛼 → 𝛽 𝒈 𝑥 ∶ 𝑥𝑠 = 𝒇 𝑥 𝒈 𝑥𝑠 𝒗 :: 𝛽 𝒇 :: 𝛼 → 𝛽 → 𝛽 scala> decimal(List(1,2,3,4)) val res0: Int = 1234 haskell> decimal [1,2,3,4] 1234 𝑑0 ∗ 103 + 𝑑1 ∗ 102 + 𝑑2 ∗ 101 + 𝑑3 ∗ 100 = 1 ∗ 1000 + 2 ∗ 100 + 3 ∗ 10 + 4 ∗ 1 = 1234
3. Notice that 𝒇 has two parameters: the head of the list, and the result of recursively calling 𝒈 with the tail of the list 𝒈 𝑥 ∶ 𝑥𝑠 = 𝒇 𝑥 𝒈 𝑥𝑠 In order to define our 𝒅𝒆𝒄𝒊𝒎𝒂𝒍 function however, the two parameters of 𝒇 are not sufficient. When 𝒅𝒆𝒄𝒊𝒎𝒂𝒍 is passed [𝑑𝑘, … , 𝑑𝑛], 𝒇 is passed digit 𝑑𝑘 , so 𝒇 needs 𝑛 and 𝑘 in order to compute 10)*&, but 𝑛 − 𝑘 is the number of elements in [𝑑𝑘, … , 𝑑𝑛] minus one, so by nesting the definition of 𝒇 inside that of 𝒅𝒆𝒄𝒊𝒎𝒂𝒍, we can avoid explicitly adding a third parameter to 𝒇 : We nested 𝒇 inside 𝒅𝒆𝒄𝒊𝒎𝒂𝒍, so that the equations of 𝒅𝒆𝒄𝒊𝒎𝒂𝒍 match (almost) those of 𝒈. They don’t match perfectly, in that the 𝒇 nested inside 𝒅𝒆𝒄𝒊𝒎𝒂𝒍 depends on 𝒅𝒆𝒄𝒊𝒎𝒂𝒍’s list parameter, whereas the 𝒇 nested inside 𝒈 does not depend on 𝒈’s list parameter. Are we still able to redefine 𝒅𝒆𝒄𝒊𝒎𝒂𝒍 using 𝑓𝑜𝑙𝑑𝑟? If the match had been perfect, we would be able to define 𝒅𝒆𝒄𝒊𝒎𝒂𝒍 = 𝑓𝑜𝑙𝑑𝑟 𝑓 0 (with 𝒗 = 0), but because 𝒇 needs to know the value of 𝑛 − 𝑘, we can’t just pass 𝒇 to 𝑓𝑜𝑙𝑑𝑟, and use 0 as the initial accumulator. Instead, we need to use (0, 0) as the accumulator (the second 0 being the initial value of 𝑛 − 𝑘, when 𝑘 = 𝑛), and pass to 𝑓𝑜𝑙𝑑𝑟 a helper function ℎ that manages 𝑛 − 𝑘 and that wraps 𝒇, so that the latter has access to 𝑛 − 𝑘. def h(d: Int, acc: (Int,Int)): (Int,Int) = acc match { case (ds, e) => def f(d: Int, ds: Int): Int = d * Math.pow(10, e).toInt + ds (f(d, ds), e + 1) } def decimal(ds: List[Int]): Int = ds.foldRight((0,0))(h).head h :: Int -> (Int,Int) -> (Int,Int) h d (ds, e) = (f d ds, e + 1) where f :: Int -> Int -> Int f d ds = d * (10 ^ e) + ds decimal :: [Int] -> Int decimal ds = fst (foldr h (0,0) ds) def decimal(digits: List[Int]): Int = val e = digits.length-1 def f(d: Int, ds: Int): Int = d * Math.pow(10, e).toInt + ds digits match case Nil => 0 case d +: ds => f(d, decimal(ds)) decimal :: [Int] -> Int decimal [] = 0 decimal (d:ds) = f d (decimal ds) where e = length ds f :: Int -> Int -> Int f d ds = d * (10 ^ e) + ds The unnecessary complexity of the 𝒅𝒆𝒄𝒊𝒎𝒂𝒍 functions on this slide is purely due to them being defined in terms of 𝒇 . See next slide for simpler refactored versions in which 𝒇 is inlined.
4. def f(d: Int, acc: (Int,Int)): (Int,Int) = acc match case (ds, e) => (d * Math.pow(10, e).toInt + ds, e + 1) def decimal(ds: List[Int]): Int = ds.foldRight((0,0))(f).head f :: Int -> (Int,Int) -> (Int,Int) f d (ds, e) = (d * (10 ^ e) + ds, e + 1) decimal :: [Int] -> Int decimal ds = fst (foldr f (0,0) ds) def decimal(digits: List[Int]): Int = digits match case Nil => 0 case d +: ds => d * Math.pow(10, ds.length).toInt + decimal(ds) decimal :: [Int] -> Int decimal [] = 0 decimal (d:ds) = d*(10^(length ds))+(decimal ds) Same 𝒅𝒆𝒄𝒊𝒎𝒂𝒍 functions as on the previous slide, but refactored as follows: 1. inlined 𝒇 in all four functions 2. inlined e in the first two functions 3. renamed 𝒉 to 𝒇 in the last two functions
5. Not every function on lists can be defined as an instance of 𝑓𝑜𝑙𝑑𝑟. ... Even for those that can, an alternative definition may be more efficient. To illustrate, suppose we want a function decimal that takes a list of digits and returns the corresponding decimal number; thus 𝑑𝑒𝑐𝑖𝑚𝑎𝑙 [𝑥0 , 𝑥1 , … , 𝑥n ] = ∑!"# $ 𝑥𝑘 10($&!) It is assumed that the most significant digit comes first in the list. One way to compute decimal efficiently is by a process of multiplying each digit by ten and adding in the following digit. For example 𝑑𝑒𝑐𝑖𝑚𝑎𝑙 𝑥0 , 𝑥1 , 𝑥2 = 10 × 10 × 10 × 0 + 𝑥0 + 𝑥1 + 𝑥2 This decomposition of a sum of powers is known as Horner’s rule. Suppose we define ⊕ by 𝑛 ⊕ 𝑥 = 10 × 𝑛 + 𝑥. Then we can rephrase the above equation as 𝑑𝑒𝑐𝑖𝑚𝑎𝑙 𝑥0 , 𝑥1 , 𝑥2 = (0 ⊕ 𝑥0 ) ⊕ 𝑥1 ⊕ 𝑥2 This is almost like an instance of 𝑓𝑜𝑙𝑑𝑟, except that the grouping is the other way round, and the starting value appears on the left, not on the right. In fact the computation is dual: instead of processing from right to left, the computation processes from left to right. This example motivates the introduction of a second fold operator called 𝑓𝑜𝑙𝑑𝑙 (pronounced ‘fold left’). Informally: 𝑓𝑜𝑙𝑑𝑙 ⊕ 𝑒 𝑥0 , 𝑥1 , … , 𝑥𝑛 − 1 = … ((𝑒 ⊕ 𝑥0 ) ⊕ 𝑥1 ) … ⊕ 𝑥𝑛 − 1 The parentheses group from the left, which is the reason for the name. The full definition of 𝑓𝑜𝑙𝑑𝑙 is 𝑓𝑜𝑙𝑑𝑙 ∷ 𝛽 → 𝛼 → 𝛽 → 𝛽 → 𝛼 → 𝛽 𝑓𝑜𝑙𝑑𝑙 𝑓 𝑒 = 𝑒 𝑓𝑜𝑙𝑑𝑙 𝑓 𝑒 𝑥: 𝑥𝑠 = 𝑓𝑜𝑙𝑑𝑙 𝑓 𝑓 𝑒 𝑥 𝑥𝑠 Richard Bird The definition of 𝒅𝒆𝒄𝒊𝒎𝒂𝒍 using a right fold is inefficient because it computes ∑!"# $ 𝑑𝑘 ∗ 10$&! by computing 10$&! for each 𝑘.
6. If we look back at our initial recursive definition of 𝒅𝒆𝒄𝒊𝒎𝒂𝒍, we see that it splits its list parameter into a head and a tail. If we get 𝒅𝒆𝒄𝒊𝒎𝒂𝒍 to split the list into init and last, we can make it more efficient by using Horner’s rule: We can then improve on that by going back to splitting the list into a head and a tail, and making 𝒅𝒆𝒄𝒊𝒎𝒂𝒍 tail recursive: And finally, we can improve on that by defining 𝒅𝒆𝒄𝒊𝒎𝒂𝒍 using a left fold: (⊕) :: Int -> Int -> Int n ⊕ d = 10 * n + d decimal :: [Int] -> Int decimal [] = 0 decimal (d:ds) = d*(10^(length ds)) + (decimal ds) def decimal(digits: List[Int]): Int = digits match case Nil => 0 case d +: ds => d * Math.pow(10, ds.length).toInt + decimal(ds) extension (n: Int) def ⊕(d Int): Int = 10 * n + d decimal :: [Int] -> Int -> Int decimal [] acc = acc decimal (d:ds) acc = decimal ds (acc ⊕d) def decimal(ds: List[Int], acc: Int=0): Int = digits match case Nil => acc case d +: ds => decimal(ds, acc ⊕ d) decimal :: [Int] -> Int decimal = foldl (⊕) 0 decimal :: [Int] -> Int decimal [] = 0 decimal ds = (decimal (init ds)) ⊕ (last ds) def decimal(digits: List[Int]): Int = digits match case Nil => 0 case ds :+ d => decimal(ds) ⊕ d def decimal(ds: List[Int]): Int = ds.foldLeft(0)(_⊕_)
7. Recap In the case of the 𝒅𝒆𝒄𝒊𝒎𝒂𝒍 function, defining it using a left fold is simple and mathematically more efficient whereas defining it using a right fold is more complex and mathematically less efficient def decimal(ds: List[Int]): Int = ds.foldRight((0,0))(f).head def f(d: Int, acc: (Int,Int)): (Int,Int) = acc match case (ds, e) => (d * Math.pow(10, e).toInt + ds, e + 1) decimal :: [Int] -> Int decimal ds = fst (foldr f (0,0) ds) f :: Int -> (Int,Int) -> (Int,Int) f d (ds, e) = (d * (10 ^ e) + ds, e + 1) 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 𝒅𝒆𝒄𝒊𝒎𝒂𝒍 1,2,3,4 = 𝑑0 ∗ 103 + (𝑑1 ∗ 102 + (𝑑2 ∗ 101 + (𝑑3 ∗ 100 + 0))) = 1 ∗ 1000 + (2 ∗ 100 + (3 ∗ 10 + (4 ∗ 1 + 0))) = 1234 𝒅𝒆𝒄𝒊𝒎𝒂𝒍 1,2,3,4 = 10 ∗ 10 ∗ 10 ∗ 10 ∗ 0 + 𝑑0 + 𝑑1 + 𝑑2 + 𝑑3 = 10 ∗ (10 ∗ 10 ∗ 10 ∗ 0 + 1 + 2 + 3) + 4 = 1234
8. https://fpilluminated.com/ inspired by