Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Folding Cheat Sheet #7

Folding Cheat Sheetย #7

The three duality theorems of fold.

Avatar for Philip Schwarz

Philip Schwarz

July 07, 2024
Tweet

More Decks by Philip Schwarz

Other Decks in Programming

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).