Folding Cheat Sheet #7

The three duality theorems of fold.

Transcript

1. CHEAT-SHEET Folding #7 ∶ / \ 𝒂𝟎 ∶ / \ 𝒂𝟏 ∶ / \ 𝒂𝟐 ∶ / \ 𝒂𝟑 𝒇 / \ 𝒂𝟎 𝒇 / \ 𝒂𝟏 𝒇 / \ 𝒂𝟐 𝒇 / \ 𝒂𝟑 𝒆 @philip_schwarz slides by https://fpilluminated.com/
2. The Three Duality Theorems of Fold (for all finite lists ) 𝑓𝑜𝑙𝑑𝑟 ⊕ 𝑒 𝑥𝑠 = 𝑓𝑜𝑙𝑑𝑙 ⊕ 𝑒 𝑥𝑠 𝑓𝑜𝑙𝑑𝑟 ⊕ 𝑒 𝑥𝑠 = 𝑓𝑜𝑙𝑑𝑙 ⊗ 𝑒 𝑥𝑠 𝑓𝑜𝑙𝑑𝑟 𝑓 𝑒 𝑥𝑠 = 𝑓𝑜𝑙𝑑𝑙 𝑓𝑙𝑖𝑝 𝑓 𝑒 (𝑟𝑒𝑣𝑒𝑟𝑠𝑒 𝑥𝑠) where ⊕ and 𝒆 are such that for all 𝑥, 𝑦, and 𝑧 we have 𝑥 ⊕ 𝑦 ⊕ 𝑧 = 𝑥 ⊕ 𝑦 ⊕ 𝑧 𝒆 ⊕ 𝑥 = 𝑥 and 𝑥 ⊕ 𝒆 = 𝑥 In other words, ⊕ is associative with unit 𝒆. where ⊕, ⊗, and 𝒆 are such that for all 𝑥, 𝑦, and 𝑧 we have 𝑥 ⊕ 𝑦 ⊗ 𝑧 = 𝑥 ⊕ 𝑦 ⊗ 𝑧 𝑥 ⊕ 𝒆 = 𝒆 ⊗ 𝑥 In other words, ⊕ and ⊗ associate with each other, and 𝒆 on the right of ⊕ is equivalent to 𝒆 on the left of ⊗. where 𝑓𝑙𝑖𝑝 𝑓 𝑥 𝑦 = 𝑓 𝑦 𝑥 1 2 3 𝑓𝑜𝑙𝑑𝑙 ∷ 𝛽 → 𝛼 → 𝛽 → 𝛽 → 𝛼 → 𝛽 𝑓𝑜𝑙𝑑𝑙 𝑓 𝑒 = 𝑒 𝑓𝑜𝑙𝑑𝑙 𝑓 𝑒 𝑥: 𝑥𝑠 = 𝑓𝑜𝑙𝑑𝑙 𝑓 𝑓 𝑒 𝑥 𝑥𝑠 𝑓𝑜𝑙𝑑𝑟 ∷ 𝛼 → 𝛽 → 𝛽 → 𝛽 → 𝛼 → 𝛽 𝑓𝑜𝑙𝑑𝑟 𝑓 𝑒 = 𝑒 𝑓𝑜𝑙𝑑𝑟 𝑓 𝑒 𝑥: 𝑥𝑠 = 𝑓 𝑥 𝑓𝑜𝑙𝑑𝑟 𝑓 𝑒 𝑥𝑠 † ‡ Theorem is a special case of with ⊕ = ⊗ 1 2 † Theorem is a generalisation of 2 1 ‡ ✠ For example, + and × are associative operators with respective units 0 and 1. ✠ ☩ ☩ Except lists sufficiently large to cause a right fold to encounter a stack overflow
3. :{ foldRight :: (α -> β -> β) -> β -> [α] -> β foldRight f e [] = e foldRight f e (x:xs) = f x (foldRight f e xs) foldLeft :: (β -> α -> β) -> β -> [α] -> β foldLeft f e [] = e foldLeft f e (x:xs) = foldLeft f (f e x) xs :} > sumLeft = foldLeft (+) 0 > sumRight = foldRight (+) 0 > subLeft = foldLeft (-) 0 > subRight = foldRight (-) 0 > prdLeft = foldLeft (*) 1 > prdRight = foldRight (*) 1 > andLeft = foldLeft (&&) True > andRight = foldRight (&&) True > orLeft = foldLeft (||) False > orRight = foldRight (||) False > concatLeft = foldLeft (++) [] > concatRight = foldRight (++) [] > integers = [1,2,3,4] > flags = [True, False, True] > lists = [[1], [2,3,4],[5,6]] > subLeft(integers) -10 > subRight(integers) -2 > assert (sumLeft(integers) == sumRight(integers)) "OK” "OK" > assert (subLeft(integers) /= subRight(integers)) "OK” "OK" > assert (prdLeft(integers) == prdRight(integers)) "OK” "OK" > assert (andLeft(flags) == andRight(flags)) "OK” "OK" > assert (orLeft(flags) == orRight(flags)) "OK” "OK" > assert (concatLeft(lists) == concatRight(lists)) "OK” "OK” 𝑓𝑜𝑙𝑑𝑟 ⊕ 𝑒 𝑥𝑠 = 𝑓𝑜𝑙𝑑𝑙 ⊕ 𝑒 𝑥𝑠 1 associative operator unit + 0 * 1 && True || False ++ [] subtraction is not associative, and 0 is not its unit, so the following are not equivalent: foldLeft (-) 0 foldRight (-) 0 where ⊕ and 𝒆 are such that for all 𝑥, 𝑦, and 𝑧 we have 𝑥 ⊕ 𝑦 ⊕ 𝑧 = 𝑥 ⊕ 𝑦 ⊕ 𝑧 𝒆 ⊕ 𝑥 = 𝑥 and 𝑥 ⊕ 𝒆 = 𝑥 In other words, ⊕ is associative with unit 𝒆.
4. > sumLeft = foldl (+) 0 > sumRight = foldr (+) 0 > subLeft = foldl (-) 0 > subRight = foldr (-) 0 > prdLeft = foldl (*) 1 > prdRight = foldr (*) 1 > andLeft = foldl (&&) True > andRight = foldr (&&) True > orLeft = foldl (||) False > orRight = foldr (||) False > concatLeft = foldl (++) [] > concatRight = foldr (++) [] > integers = [1,2,3,4] > flags = [True, False, True] > lists = [[1], [2,3,4],[5,6]] > subLeft(integers) -10 > subRight(integers) -2 > assert (sumLeft(integers) == sumRight(integers)) "OK” "OK" > assert (subLeft(integers) /= subRight(integers)) "OK” "OK" > assert (prdLeft(integers) == prdRight(integers)) "OK” "OK" > assert (andLeft(flags) == andRight(flags)) "OK” "OK" > assert (orLeft(flags) == orRight(flags)) "OK” "OK" > assert (concatLeft(lists) == concatRight(lists)) "OK” "OK” Same as previous slide but using built-in foldl and foldr subtraction is not associative, and 0 is not its unit, so the following are not equivalent: foldl (-) 0 foldr (-) 0
5. def foldr[A, B](f: A => B => B)(e: B)(s: List[A]): B = s match case Nil => e case x :: xs => f(x)(foldr(f)(e)(xs)) def foldl[A, B](f: B => A => B)(e: B)(s: List[A]): B = s match case Nil => e case x :: xs => foldl(f)(f(e)(x))(xs) val `(+)`: Int => Int => Int = m => n => m + n val `(-)`: Int => Int => Int = m => n => m - n val `(*)`: Int => Int => Int = m => n => m * n val `(&&)`: Boolean => Boolean => Boolean = m => n => m && n val `(||)`: Boolean => Boolean => Boolean = m => n => m || n def `(++)`[A](m: Seq[A]): Seq[A] => Seq[A] = n => m ++ n val sumLeft = foldl(`(+)`)(0) val sumRight = foldr(`(+)`)(0) val subLeft = foldl(`(-)`)(0) val subRight = foldr(`(-)`)(0) val prodLeft = foldl(`(*)`)(1) val prodRight = foldr(`(*)`)(1) val andLeft = foldl(`(&&)`)(true) val andRight = foldr(`(&&)`)(true) val orLeft = foldl(`(||)`)(true) val orRight = foldr(`(||)`)(true) val concatLeft = foldl(`(++)`)(Nil) val concatRight = foldr(`(++)`)(Nil) val integers = List(1, 2, 3, 4) val flags = List(true, false, true) val lists = List(List(1), List(2, 3, 4), List(5, 6)) scala> subLeft(integers) val res0: Int = -10 scala> subRight(integers) val res1: Int = -2 scala> assert( sumLeft(integers) == sumRight(integers) ) | assert( subLeft(integers) != subRight(integers) ) | assert( prodLeft(integers) == prodRight(integers) ) | assert( andLeft(flags) == andRight(flags) ) | assert( orLeft(flags) == orRight(flags) ) | assert( concatLeft(lists) == concatRight(lists) ) scala> subtraction is not associative, and 0 is not its unit, so the following are not equivalent: foldl(`(-)`)(0) foldr(`(-)`)(0) 𝑓𝑜𝑙𝑑𝑟 ⊕ 𝑒 𝑥𝑠 = 𝑓𝑜𝑙𝑑𝑙 ⊕ 𝑒 𝑥𝑠 1 associative operator unit + 0 * 1 && True || False ++ [] where ⊕ and 𝒆 are such that for all 𝑥, 𝑦, and 𝑧 we have 𝑥 ⊕ 𝑦 ⊕ 𝑧 = 𝑥 ⊕ 𝑦 ⊕ 𝑧 𝒆 ⊕ 𝑥 = 𝑥 and 𝑥 ⊕ 𝒆 = 𝑥 In other words, ⊕ is associative with unit 𝒆.
6. val sumLeft: List[Int] => Int = _.foldLeft(0)(_+_) val sumRight: List[Int] => Int = _.foldRight(0)(_+_) val subLeft: List[Int] => Int = _.foldLeft(0)(_-_) val subRight: List[Int] => Int = _.foldRight(0)(_-_) val prodLeft: List[Int] => Int = _.foldLeft(1)(_*_) val prodRight: List[Int] => Int = _.foldRight(1)(_*_) val andLeft: List[Boolean] => Boolean = _.foldLeft(true)(_&&_) val andRight: List[Boolean] => Boolean = _.foldRight(true)(_&&_) val orLeft: List[Boolean] => Boolean = _.foldLeft(false)(_||_) val orRight: List[Boolean] => Boolean = _.foldRight(false)(_||_) def concatLeft[A]: List[List[A]] => List[A] = _.foldLeft(List.empty[A])(_++_) def concatRight[A]: List[List[A]] => List[A] = _.foldRight(List.empty[A])(_++_) val integers = List(1, 2, 3, 4) val flags = List(true, false, true) val lists = List(List(1), List(2, 3, 4), List(5, 6)) scala> subLeft(integers) val res0: Int = -10 scala> subRight(integers) val res1: Int = -2 scala> assert( sumLeft(integers) == sumRight(integers) ) | assert( subLeft(integers) != subRight(integers) ) | assert( prodLeft(integers) == prodRight(integers) ) | assert( andLeft(flags) == andRight(flags) ) | assert( orLeft(flags) == orRight(flags) ) | assert( concatLeft(lists) == concatRight(lists) ) scala> Same as previous slide but using built-in foldLeft and foldRight subtraction is not associative, and 0 is not its unit, so the following are not equivalent: _.foldLeft(0)(_-_) _.foldRight(0)(_-_)
7. 𝑓𝑜𝑙𝑑𝑟 ⊕ 𝑒 𝑥𝑠 = 𝑓𝑜𝑙𝑑𝑙 ⊗ 𝑒 𝑥𝑠 2 :{ foldRight :: (α -> β -> β) -> β -> [α] -> β foldRight f e [] = e foldRight f e (x:xs) = f x (foldRight f e xs) foldLeft :: (β -> α -> β) -> β -> [α] -> β foldLeft f e [] = e foldLeft f e (x:xs) = foldLeft f (f e x) xs :} > lengthRight = foldr oneplus 0 where oneplus x n = 1 + n > lengthLeft = foldl plusone 0 where plusone n x = n + 1 > assert (lengthRight(list) == lengthLeft(list)) "OK" "OK” Same as on the left but using built-in foldl and foldr > lengthRight = foldRight oneplus 0 where oneplus x n = 1 + n > lengthLeft = foldLeft plusone 0 where plusone n x = n + 1 > assert (lengthRight(list) == lengthLeft(list)) "OK" "OK” > reverseRight = foldRight snoc [] where snoc x xs = xs ++ [x] > reverseLeft = foldLeft cons [] where cons xs x = x : xs > assert (reverseRight(list) == reverseLeft(list)) "OK" "OK" > reverseRight = foldr snoc [] where snoc x xs = xs ++ [x] > reverseLeft = foldl cons [] where cons xs x = x : xs > assert (reverseRight(list) == reverseLeft(list)) "OK" "OK" where ⊕, ⊗, and 𝒆 are such that for all 𝑥, 𝑦, and 𝑧 we have 𝑥 ⊕ 𝑦 ⊗ 𝑧 = 𝑥 ⊕ 𝑦 ⊗ 𝑧 𝑥 ⊕ 𝒆 = 𝒆 ⊗ 𝑥 In other words, ⊕ and ⊗ associate with each other, and 𝒆 on the right of ⊕ is equivalent to 𝒆 on the left of ⊗. list = [1,2,3]
8. 𝑓𝑜𝑙𝑑𝑟 ⊕ 𝑒 𝑥𝑠 = 𝑓𝑜𝑙𝑑𝑙 ⊗ 𝑒 𝑥𝑠 2 def foldr[A, B](f: A => B => B)(e: B)(s: List[A]): B = s match case Nil => e case x :: xs => f(x)(foldr(f)(e)(xs)) def foldl[A, B](f: B => A => B)(e: B)(s: List[A]): B = s match case Nil => e case x :: xs => foldl(f)(f(e)(x))(xs) def oneplus[A]: A => Int => Int = x => n => 1 + n def plusOne[A]: Int => A => Int = n => x => n + 1 val lengthRight = foldr(oneplus)(0) val lengthLeft = foldl(plusOne)(0) scala> assert( lengthRight(list) == lengthLeft(list) ) def snoc[A]: A => List[A] => List[A] = x => xs => xs ++ List(x) def cons[A]: List[A] => A => List[A] = xs => x => x::xs val reverseRight = foldr(snoc[Int])(Nil) val reverseLeft = foldl(cons[Int])(Nil) scala> assert( reverseRight(list) == reverseLeft(list) ) def oneplus[A]: (A, Int) => Int = (x, n) => 1 + n def plusOne[A]: (Int, A) => Int = (n, x) => n + 1 def lengthRight[A]: List[A] => Int = _.foldRight(0)(oneplus) def lengthLeft[A]: List[A] => Int = _.foldLeft(0)(plusOne) scala> assert( lengthRight(list) == lengthLeft(list) ) def snoc[A]:(A, List[A]) => List[A] = (x, xs) => xs ++ List(x) def cons[A]:(List[A], A) => List[A] = (xs, x) => x::xs def reverseRight[A]: List[A]=>List[A] = _.foldRight(Nil)(snoc) def reverseLeft[A] : List[A]=>List[A] = _.foldLeft(Nil)(cons) scala> assert( reverseRight(list) == reverseLeft(list) ) Same as on the left but using built-in foldLeft and foldRight where ⊕, ⊗, and 𝒆 are such that for all 𝑥, 𝑦, and 𝑧 we have 𝑥 ⊕ 𝑦 ⊗ 𝑧 = 𝑥 ⊕ 𝑦 ⊗ 𝑧 𝑥 ⊕ 𝒆 = 𝒆 ⊗ 𝑥 In other words, ⊕ and ⊗ associate with each other, and 𝒆 on the right of ⊕ is equivalent to 𝒆 on the left of ⊗. val list: List[Int] = List(1, 2, 3)
9. > sumRight = foldRight (+) 0 > sumLeft = foldLeft (flip (+)) 0 . reverse > assert (sumRight(list) == sumLeft(list)) "OK" "OK" 𝑓𝑜𝑙𝑑𝑟 𝑓 𝑒 𝑥𝑠 = 𝑓𝑜𝑙𝑑𝑙 𝑓𝑙𝑖𝑝 𝑓 𝑒 (𝑟𝑒𝑣𝑒𝑟𝑠𝑒 𝑥𝑠) 3 :{ foldRight :: (α -> β -> β) -> β -> [α] -> β foldRight f e [] = e foldRight f e (x:xs) = f x (foldRight f e xs) foldLeft :: (β -> α -> β) -> β -> [α] -> β foldLeft f e [] = e foldLeft f e (x:xs) = foldLeft f (f e x) xs :} > sumRight = foldr (+) 0 > sumLeft = foldl (flip (+)) 0 . reverse > assert (sumRight(list) == sumLeft(list)) "OK" "OK" Same as on the left but using built-in foldl and foldr > oneplus x n = 1 + n > lengthRight = foldRight oneplus 0 > lengthLeft = foldLeft (flip oneplus) 0 . reverse > assert (lengthRight(list) == lengthLeft(list)) "OK" "OK" > oneplus x n = 1 + n > lengthRight = foldr oneplus 0 > lengthLeft = foldl (flip oneplus) 0 . reverse > assert (lengthRight(list) == lengthLeft(list)) "OK" "OK" > n ⊕ d = 10 * n + d > decimalLeft = foldLeft (⊕) 0 > decimalRight = foldRight (flip (⊕)) 0 . reverse > assert (decimalLeft(list) == decimalRight(list)) "OK" > n ⊕ d = 10 * n + d > decimalLeft = foldl (⊕) 0 > decimalRight = foldr (flip (⊕)) 0 . reverse > assert (decimalLeft(list) == decimalRight(list)) "OK" "OK" (Also holds true when 𝑓𝑜𝑙𝑑𝑟 and 𝑓𝑜𝑙𝑑𝑙 are swapped) † † † see next slide
10. At the bottom of the previous slide and the next one, instead of exploiting this equation 𝑓𝑜𝑙𝑑𝑟 𝑓 𝑒 𝑥𝑠 = 𝑓𝑜𝑙𝑑𝑙 𝑓𝑙𝑖𝑝 𝑓 𝑒 (𝑟𝑒𝑣𝑒𝑟𝑠𝑒 𝑥𝑠) we are exploiting the following derived equation in which 𝑓𝑜𝑙𝑑𝑟 is renamed to 𝑓𝑜𝑙𝑑𝑙 and vice versa: 𝑓𝑜𝑙𝑑𝑙 𝑓 𝑒 𝑥𝑠 = 𝑓𝑜𝑙𝑑𝑟 𝑓𝑙𝑖𝑝 𝑓 𝑒 (𝑟𝑒𝑣𝑒𝑟𝑠𝑒 𝑥𝑠) The equation can be derived as shown below. Define 𝑔 = 𝑓𝑙𝑖𝑝 𝑓 and 𝑦𝑠 = 𝑟𝑒𝑣𝑒𝑟𝑠𝑒 𝑥𝑠, from which it follows that 𝑓 = 𝑓𝑙𝑖𝑝 𝑔 and 𝑥𝑠 = 𝑟𝑒𝑣𝑒𝑟𝑠𝑒 𝑦𝑠. In the original equation, replace 𝑓 with (𝑓𝑙𝑖𝑝 𝑔) and replace 𝑥𝑠 with (𝑟𝑒𝑣𝑒𝑟𝑠𝑒 𝑦𝑠) 𝑓𝑜𝑙𝑑𝑟 𝑓𝑙𝑖𝑝 𝑔 𝑒 (𝑟𝑒𝑣𝑒𝑟𝑠𝑒 𝑦𝑠) = 𝑓𝑜𝑙𝑑𝑙 𝑓𝑙𝑖𝑝 𝑓𝑙𝑖𝑝 𝑔 𝑒 (𝑟𝑒𝑣𝑒𝑟𝑠𝑒 (𝑟𝑒𝑣𝑒𝑟𝑠𝑒 𝑦𝑠)) Simplify by replacing 𝑓𝑙𝑖𝑝 𝑓𝑙𝑖𝑝 𝑔 with 𝑔 and (𝑟𝑒𝑣𝑒𝑟𝑠𝑒 (𝑟𝑒𝑣𝑒𝑟𝑠𝑒 𝑦𝑠)) with 𝑦𝑠 𝑓𝑜𝑙𝑑𝑟 𝑓𝑙𝑖𝑝 𝑔 𝑒 𝑟𝑒𝑣𝑒𝑟𝑠𝑒 𝑦𝑠 = 𝑓𝑜𝑙𝑑𝑙 𝑔 𝑒 𝑦𝑠 Swap the right hand side with left hand side 𝑓𝑜𝑙𝑑𝑙 𝑔 𝑒 𝑦𝑠 = 𝑓𝑜𝑙𝑑𝑟 𝑓𝑙𝑖𝑝 𝑔 𝑒 𝑟𝑒𝑣𝑒𝑟𝑠𝑒 𝑦𝑠 Rename 𝑔 to 𝑓 and rename 𝑦𝑠 to 𝑥𝑠 𝑓𝑜𝑙𝑑𝑙 𝑓 𝑒 𝑥𝑠 = 𝑓𝑜𝑙𝑑𝑟 𝑓𝑙𝑖𝑝 𝑓 𝑒 𝑟𝑒𝑣𝑒𝑟𝑠𝑒 𝑥𝑠 @philip_schwarz
11. 𝑓𝑜𝑙𝑑𝑟 𝑓 𝑒 𝑥𝑠 = 𝑓𝑜𝑙𝑑𝑙 𝑓𝑙𝑖𝑝 𝑓 𝑒 (𝑟𝑒𝑣𝑒𝑟𝑠𝑒 𝑥𝑠) 3 def flip[A, B, C]: (A => B => C) => (B => A => C) = f => b => a => f(a)(b) val list: List[Int] = List(1, 2, 3) def plus: Int => Int => Int = m => n => m + n val sumRight = foldr(plus)(0) val sumLeft = (xs: List[Int]) => foldl(flip(plus))(0)(xs.reverse) assert( sumRight(list) == sumLeft(list) ) def foldr[A, B](f: A => B => B)(e: B)(s: List[A]): B = s match case Nil => e case x :: xs => f(x)(foldr(f)(e)(xs)) def foldl[A, B](f: B => A => B)(e: B)(s: List[A]): B = s match case Nil => e case x :: xs => foldl(f)(f(e)(x))(xs) def oneplus[A]: A => Int => Int = x => n => 1 + n val lengthRight = foldr(oneplus)(0) def lengthLeft[A] = (xs: List[A]) => foldl(flip(oneplus))(0)(xs.reverse) assert( lengthRight(list) == lengthLeft(list) ) def `(⊕)`: Int => Int => Int = n => d => 10 * n + d val decimalLeft = foldl(`(⊕)`)(0) val decimalRight = (xs: List[Int]) => foldr(flip(`(⊕)`))(0)(xs.reverse) assert( decimalLeft(list) == decimalRight(list) ) † see previous slide †
12. def flip[A, B, C]: ((A,B) => C) => ((B,A) => C) = f => (b,a) => f(a,b) val list: List[Int] = List(1, 2, 3) def plus: (Int,Int) => Int = (m,n) => m + n val sumRight: List[Int] => Int = _.foldRight(0)(plus) val sumLeft: List[Int] => Int = _.reverse.foldLeft(0)(flip(plus)) assert( sumRight(list) == sumLeft(list) ) def oneplus[A]: (A,Int) => Int = (x,n) => 1 + n def lengthRight[A]: List[A] => Int = _.foldRight(0)(oneplus) def lengthLeft[A]: List[A] => Int = _.reverse.foldLeft(0)(flip(oneplus)) assert( lengthRight(list) == lengthLeft(list) ) val `(⊕)`: ((Int,Int) => Int) = (n,d) => 10 * n + d val decimalLeft: List[Int] => Int = _.foldLeft(0)(`(⊕)`) val decimalRight: List[Int] => Int = _.reverse.foldRight(0)(flip(`(⊕)`)) assert( decimalLeft(list) == decimalRight(list) ) Same as previous slide but using built-in foldLeft and foldRight
13. In previous slides we saw a decimal function that is implemented with a right fold. It is derived, using the third duality theorem, from a decimal function implemented with a left fold. 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) > n ⊕ d = 10 * n + d > decimalLeft = foldl (⊕) 0 > decimalRight = foldr (flip (⊕)) 0 . reverse val `(⊕)`: ((Int,Int) => Int) = (n,d) => 10 * n + d val decimalLeft: List[Int] => Int = _.foldLeft(0)(`(⊕)`) val decimalRight: List[Int] => Int = _.reverse.foldRight(0)(flip(`(⊕)`)) 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) Note how much simpler it is than the decimal function that we came up with in Cheat Sheet #4. That function was produced by the right hand side of the universal property of 𝑓𝑜𝑙𝑑, after plugging into the left hand side a function that we contrived purely to match that left hand side.
14. Cheat Sheet #6 claimed (see bottom of next slide) that when using Scala’s built in foldRight function, the reason why doing a right fold over a large collection did not result in a stack overflow error, is that foldRight is defined in terms of foldLeft.
15. scala> def foldr[A,B](f: A=>B=>B)(e:B)(s:List[A]):B = | s match { case Nil => e | case x::xs => f(x)(foldr(f)(e)(xs)) } scala> def `(+)`: Long => Long => Long = | m => n => m + n scala> foldr(`(+)`)(0)(List(1,2,3,4)) val res1: Long = 10 scala> foldr(`(+)`)(0)(List.range(1,10_001)) val res2: Long = 50005000 scala> foldr(`(+)`)(0)(List.range(1,100_001)) java.lang.StackOverflowError scala> // same again but using built-in function scala> List.range(1,10_001).foldRight(0)(_+_) val res3: Int = 50005000 scala> List.range(1,100_001).foldRight(0L)(_+_) val res4: Long = 500000500000 scala> import scala.annotation.tailrec scala> @tailrec | def foldl[A,B](f: B=>A=>B)(e:B)(s:List[A]):B = | s match { case Nil => e | case x::xs => foldl(f)(f(e)(x))(xs) } scala> def `(+)`: Long => Long => Long = | m => n => m + n scala> foldl(`(+)`)(0)(List.range(1,10_001)) val res1: Long = 50005000 scala> foldl(`(+)`)(0)(List.range(1,100_001)) val res2: Long = 5000050000 scala> // same again but using built-in function scala> List.range(1,10_001).foldLeft(0)(_+_) val res3: Int = 50005000 scala> List.range(1,100_001).foldLeft(0L)(_+_) val res4: Long = 5000050000 The reason a stack overflow is not happening here is because built-in foldRight is defined in terms of foldLeft! (see cheat-sheet #7) 𝑓𝑜𝑙𝑑𝑟 ∷ 𝛼 → 𝛽 → 𝛽 → 𝛽 → 𝛼 → 𝛽 𝑓𝑜𝑙𝑑𝑟 𝑓 𝑏 = 𝑏 𝑓𝑜𝑙𝑑𝑟 𝑓 𝑏 𝑥: 𝑥𝑠 = 𝑓 𝑥 𝑓𝑜𝑙𝑑𝑟 𝑓 𝑏 𝑥𝑠 𝑓𝑜𝑙𝑑𝑙 ∷ 𝛽 → 𝛼 → 𝛽 → 𝛽 → 𝛼 → 𝛽 𝑓𝑜𝑙𝑑𝑙 𝑓 𝑏 = 𝑏 𝑓𝑜𝑙𝑑𝑙 𝑓 𝑏 𝑥: 𝑥𝑠 = 𝑓𝑜𝑙𝑑𝑙 𝑓 𝑓 𝑏 𝑥 𝑥𝑠
16. The remaining slides provide a justification for that claim, and are taken from the following deck, which is what this cheat sheet is based on.
17. def foldRight[B](z: B)(op: (A, B) => B): B = reversed.foldLeft(z)((b, a) => op(a, b)) final override def foldRight[B](z: B)(op: (A, B) => B): B = { var acc = z var these: List[A] = reverse while (!these.isEmpty) { acc = op(these.head, acc) these = these.tail } acc } override def foldLeft[B](z: B)(op: (B, A) => B): B = { var acc = z var these: LinearSeq[A] = coll while (!these.isEmpty) { acc = op(acc, these.head) these = these.tail } acc } The reason why doing a right fold over a large collection did not result in a stack overflow error, is that the foldRight function is implemented by code that reverses the sequence, flips the function that it is passed, and then calls foldLeft! While this is not so obvious when we look at the code for foldRight in List, because it effectively inlines the call to foldLeft… …it is plain to see in the foldRight function for Seq Third duality theorem. For all finite lists 𝑥𝑠, 𝑓𝑜𝑙𝑑𝑟 𝑓 𝑒 𝑥𝑠 = 𝑓𝑜𝑙𝑑𝑙 𝑓𝑙𝑖𝑝 𝑓 𝑒 (𝑟𝑒𝑣𝑒𝑟𝑠𝑒 𝑥𝑠) 𝒘𝒉𝒆𝒓𝒆 𝑓𝑙𝑖𝑝 𝑓 𝑥 𝑦 = 𝑓 𝑦 𝑥 This is the third duality theorem in action
18. def foldRight[A,B](as: List[A], z: B)(f: (A, B) => B): B = as match { case Nil => z case Cons(x, xs) => f(x, foldRight(xs, z)(f)) } Functional Programming in Scala (by Paul Chiusano and Runar Bjarnason) @pchiusano @runarorama sealed trait List[+A] case object Nil extends List[Nothing] case class Cons[+A](head: A, tail: List[A]) extends List[A] def foldRightViaFoldLeft[A,B](l: List[A], z: B)(f: (A,B) => B): B = foldLeft(reverse(l), z)((b,a) => f(a,b)) @annotation.tailrec def foldLeft[A,B](l: List[A], z: B)(f: (B, A) => B): B = l match{ case Nil => z case Cons(h,t) => foldLeft(t, f(z,h))(f) } Implementing foldRight via foldLeft is useful because it lets us implement foldRight tail-recursively, which means it works even for large lists without overflowing the stack. Our implementation of foldRight is not tail-recursive and will result in a StackOverflowError for large lists (we say it’s not stack-safe). Convince yourself that this is the case, and then write another general list- recursion function, foldLeft, that is tail-recursive foldRight(Cons(1, Cons(2, Cons(3, Nil))), 0)((x,y) => x + y) 1 + foldRight(Cons(2, Cons(3, Nil)), 0)((x,y) => x + y) 1 + (2 + foldRight(Cons(3, Nil), 0)((x,y) => x + y)) 1 + (2 + (3 + (foldRight(Nil, 0)((x,y) => x + y)))) 1 + (2 + (3 + (0))) 6 At the bottom of this slide is where Functional Programming in Scala shows that foldRight can be defined in terms of foldLeft. The third duality theorem in action.
19. It looks like it was none other than Paul Chiusano (co-author of FP in Scala), back in 2010, who suggested that List’s foldRight(z)(f) be implemented as reverse.foldLeft(z)(flip(f))! It also looks like the change was made in 2013 (see next slide) and that it was in 2018 that foldRight was reimplemented as a while loop (see slide after that).