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

List Unfolding - 'unfold' as the Computational ...

List Unfolding - 'unfold' as the Computational Dual of 'fold', and how 'unfold' relates toย 'iterate'"

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", "unfoldL", "unfoldL'", "unfoldr", "iterate", "anamorphism", "catamorphism", "infinite list", "lazy list", "functional programming", "scala"," haskell"

Avatar for Philip Schwarz

Philip Schwarz

May 31, 2025
Tweet

More Decks by Philip Schwarz

Other Decks in Programming

Transcript

  1. List Unfolding ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ as the Computational Dual of ๐‘“๐‘œ๐‘™๐‘‘ and

    how ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ relates to ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ @philip_schwarz slides by https://fpilluminated.org/ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ ๐‘“๐‘œ๐‘™๐‘‘
  2. @philip_schwarz https://fpilluminated.org/ In this deck weโ€™ll be looking at โ€ข

    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
  3. The next two slides are based on extracts from the

    third chapter of The Fun of Programming, which is called Origami programming, and is available at the following URL: https://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/origami.pdf Oege de Moor @oegerikus Jeremy Gibbons @jer_gib
  4. 3.1 Introduction โ€ฆ In a precise technical sense, folds and

    unfolds are the natural patterns of computation over recursive datatypes; unfolds generate data structures and folds consume them. Functional programmers are very familiar with the foldr function on lists, and its directional dual foldl; they are gradually coming to terms with the generalisation to folds on other datatypes. The computational duals, unfolds, are still rather unfamiliar [45]; we hope to show here that they are no more complicated than, and just as useful as, folds, and to promote a style of programming based on these and similar recursion patterns ( IFPH ยง3.3, ยง6.1.3, ยง6.4). 3.2 Origami with lists: sorting โ€ฆ Recall ( IFPH ยง4.1.1) that lists may be defined explicitly via the following datatype declaration: ๐๐š๐ญ๐š ๐‘ณ๐’Š๐’”๐’• ๐›ผ = ๐‘ต๐’Š๐’ | ๐‘ช๐’๐’๐’” ๐›ผ (๐‘ณ๐’Š๐’”๐’• ๐›ผ) As a concession to Haskellโ€™s special syntax, we will define a function ๐‘ค๐‘Ÿ๐‘Ž๐‘ for constructing singleton lists: ๐‘ค๐‘Ÿ๐‘Ž๐‘ โˆท ๐›ผ โ†’ ๐‘ณ๐’Š๐’”๐’• ๐›ผ ๐‘ค๐‘Ÿ๐‘Ž๐‘ ๐‘ฅ = ๐‘ช๐’๐’๐’” ๐‘ฅ ๐‘ต๐’Š๐’ We also define a function ๐‘›๐‘–๐‘™ for detecting empty lists: ๐‘›๐‘–๐‘™ โˆท ๐‘ณ๐’Š๐’”๐’• ๐›ผ โ†’ ๐‘ฉ๐’๐’๐’ ๐‘›๐‘–๐‘™ ๐‘ต๐’Š๐’ = ๐‘ป๐’“๐’–๐’† ๐‘›๐‘–๐‘™ (๐‘ช๐’๐’๐’” ๐‘ฅ ๐‘ฅ๐‘ ) = ๐‘ญ๐’‚๐’๐’”๐’† IFPH IFPH
  5. Folds for lists The natural fold for lists may be

    defined as follows: ๐‘“๐‘œ๐‘™๐‘‘๐ฟ โˆท ๐›ผ โ†’ ๐›ฝ โ†’ ๐›ฝ โ†’ ๐›ฝ โ†’ ๐‘ณ๐’Š๐’”๐’• ๐›ผ โ†’ ๐›ฝ ๐‘“๐‘œ๐‘™๐‘‘๐ฟ ๐‘“ ๐‘’ ๐‘ต๐’Š๐’ = ๐‘’ ๐‘“๐‘œ๐‘™๐‘‘๐ฟ ๐‘“ ๐‘’ ๐‘ช๐’๐’๐’” ๐‘ฅ ๐‘ฅ๐‘  = ๐‘“ ๐‘ฅ ๐‘“๐‘œ๐‘™๐‘‘๐ฟ ๐‘“ ๐‘’ ๐‘ฅ๐‘  This is equivalent to Haskellโ€™s foldr function; the โ€˜๐ฟโ€™ here is for โ€˜listโ€™, not for โ€˜leftโ€™. โ€ฆ Unfolds for lists The dual of folding is unfolding. The Haskell standard List library defines the function ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐‘Ÿ for generating lists: ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐‘Ÿ โˆท ๐›ฝ โ†’ ๐‘ด๐’‚๐’š๐’ƒ๐’† (๐›ผ, ๐›ฝ) โ†’ ๐›ฝ โ†’ ๐›ผ Here, an instance of the type ๐‘ด๐’‚๐’š๐’ƒ๐’† ๐›ผ may or may not have an instance of the type ๐›ผ: ๐๐š๐ญ๐š ๐‘ด๐’‚๐’š๐’ƒ๐’† ๐›ผ = ๐‘ฑ๐’–๐’”๐’• ๐›ผ | ๐‘ต๐’๐’•๐’‰๐’Š๐’๐’ˆ We define an equivalent of ๐’–๐’๐’‡๐’๐’๐’…๐’“ for our list datatype: ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! โˆท ๐›ฝ โ†’ ๐‘ด๐’‚๐’š๐’ƒ๐’† (๐›ผ, ๐›ฝ) โ†’ ๐›ฝ โ†’ ๐‘ณ๐’Š๐’”๐’• ๐›ผ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! ๐‘“ ๐‘ข = ๐œ๐š๐ฌ๐ž ๐‘“ ๐‘ข ๐จ๐Ÿ ๐‘ต๐’๐’•๐’‰๐’Š๐’๐’ˆ โ†’ ๐‘ต๐’Š๐’ ๐‘ฑ๐’–๐’”๐’• (๐‘ฅ, ๐‘ฃ) โ†’ ๐‘ช๐’๐’๐’” ๐‘ฅ (๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! ๐‘“ ๐‘ฃ)
  6. Why is the name of the unfold function on the

    previous slide primed? ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! In other words, why does the name end in โ€ฒ ? Weโ€™ll come back to that question soon. The next two slides show Haskell and Scala documentation for their equivalent of ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ!.
  7. ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! โˆท ๐›ฝ โ†’ ๐‘ด๐’‚๐’š๐’ƒ๐’† (๐›ผ, ๐›ฝ) โ†’ ๐›ฝ โ†’

    ๐‘ณ๐’Š๐’”๐’• ๐›ผ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! ๐‘“ ๐‘ข = ๐œ๐š๐ฌ๐ž ๐‘“ ๐‘ข ๐จ๐Ÿ ๐‘ต๐’๐’•๐’‰๐’Š๐’๐’ˆ โ†’ ๐‘ต๐’Š๐’ ๐‘ฑ๐’–๐’”๐’• (๐‘ฅ, ๐‘ฃ) โ†’ ๐‘ช๐’๐’๐’” ๐‘ฅ (๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! ๐‘“ ๐‘ฃ) 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
  8. ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! โˆท ๐›ฝ โ†’ ๐‘ด๐’‚๐’š๐’ƒ๐’† (๐›ผ, ๐›ฝ) โ†’ ๐›ฝ โ†’

    ๐‘ณ๐’Š๐’”๐’• ๐›ผ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! ๐‘“ ๐‘ข = ๐œ๐š๐ฌ๐ž ๐‘“ ๐‘ข ๐จ๐Ÿ ๐‘ต๐’๐’•๐’‰๐’Š๐’๐’ˆ โ†’ ๐‘ต๐’Š๐’ ๐‘ฑ๐’–๐’”๐’• (๐‘ฅ, ๐‘ฃ) โ†’ ๐‘ช๐’๐’๐’” ๐‘ฅ (๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! ๐‘“ ๐‘ฃ) 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
  9. val multiply: List[Int] => Int = _.foldRight(1)(_ * _) val

    fact = multiply compose range(1) scala> fact(10) 3628800 Letโ€™s build on the above example to provide an example of the dual processes of folding and unfolding being used together. Letโ€™s compute the factorial of N by first unfolding and then folding. Our first example of using ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! is a range function which, given an integer lower bound and an integer upper bound, generates the sequence of integers going from the lower bound to the upper bound, inclusive of both bounds. In this example, the items in the generated list are the initial seed value, and the subsequent seed values generated by ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ!. val range: Int => Int => List[Int] = lwb => upb => List.unfold(lwb): n => if n > upb then None else Some(n, n + 1) scala> range(20)(30) val res0: List[Int] = List(20,21,22,23,24,25,26,27,28,29,30) range :: Int -> Int -> [Int] range lwb upb = unfoldr gen lwb where gen n = if n > upb then Nothing else Just (n, n + 1) > range 20 30 [20,21,22,23,24,25,26,27,28,29,30] multiply :: [Int] -> Int multiply = foldr (*) 1 fact = multiply . range 1 > fact 10 3628800
  10. squares :: Int -> [Int] squares = unfoldr gen where

    gen 0 = Nothing gen n = Just (n * n, n - 1) summation :: [Int] -> Int summation = foldr (+) 0 sumOfSquares :: Int -> Int sumOfSquares = summation . squares > sumOfSquares 5 55 val squares: Int => List[Int] = List.unfold(_): case 0 => None case n => Some(n * n, n - 1) val summation: List[Int] => Int = _.foldRight(0)(_+_) val sumOfSquares: Int => Int = summation compose squares scala> sumOfSquares(5) 55 sumOfSquares = foldr (+) 0 . unfoldr gen where gen 0 = Nothing gen n = Just(n * n, n - 1) > sumOfSquares 5 55 val sumOfSquares: Int => Int = val gen: Int => Option[(Int, Int)] = case 0 => None case n => Some(n * n, n - 1) ((n:Int) => List.unfold(n)(gen)) andThen (_.foldRight(0)(_+_)) scala> sumOfSquares(5) 55 Our second example of using ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! is a sumOfSquares function which, given an integer N, first generates the squares of the integers in the range 1..N, and then sums the squares. In this example, the items in the generated list are the squares of the initial seed (or state) value and of the subsequent seed values generated by ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ!. Same example, but refactored to highlight the fact that we are composing a fold with an unfold.
  11. val range: Int => Int => List[Int] = lwb =>

    upb => List.unfold(lwb): n => if n > upb then None else Some(n, n + 1) val range: Int => Int => List[Int] = lwb => upb => List.unfold(lwb): n => Option.unless(n > upb)(n, n + 1) val squares: Int => List[Int] = List.unfold(_): case 0 => None case n => Some(n * n, n - 1) val squares: Int => List[Int] = List.unfold(_): n => Option.unless(n == 0)(n * n, n - 1) As an aside, Scala functions range and squares may alternatively be written as follows
  12. In the example that we have just seen, the function

    f passed to the unfold function keeps returning a Just (Some) until a condition is met, at which point it returns a Nothing (None). But what stops function f from never returning a Nothing (None)? What happens if we unfold with such a function? In Haskell, it can make sense for function f never to return Nothing (None), because Haskell lists are lazy, so f can be used to generate an infinite list. In the following Haskell example, we first use foldr to generate an infinite list of Fibonacci numbers, and then take the first 10 such numbers. > take 10 (unfoldr (\(a,b) -> Just (a,(b,a+b))) (0,1)) [0,1,1,2,3,5,8,13,21,34] In Scala however, lists are not lazy, so it does not make sense to attempt to generate an infinite list, because doing so would take forever, if it werenโ€™t for the fact that the list keeps growing, and so eventually uses up all the available heap space. > List.unfold((0,1)){ case (a,b) => Some((a,(b,a+b))) }.take(10) java.lang.OutOfMemoryError: Java heap space The way we avoid the above problem is by unfolding a lazy version of a list: > LazyList.unfold((0,1)){ case (a,b) => Some((a,(b,a+b))) }.take(10).toList val res0: List[Int] = List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)
  13. Now that we have seen some examples of using the

    ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! function, letโ€™s go back to the following question: Why is the name of the function primed: why does the name end in โ€ฒ ? See the next slide for the answer.
  14. ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! โˆท ๐›ฝ โ†’ ๐‘ด๐’‚๐’š๐’ƒ๐’† (๐›ผ, ๐›ฝ) โ†’ ๐›ฝ โ†’

    ๐‘ณ๐’Š๐’”๐’• ๐›ผ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! ๐‘“ ๐‘ข = ๐œ๐š๐ฌ๐ž ๐‘“ ๐‘ข ๐จ๐Ÿ ๐‘ต๐’๐’•๐’‰๐’Š๐’๐’ˆ โ†’ ๐‘ต๐’Š๐’ ๐‘ฑ๐’–๐’”๐’• (๐‘ฅ, ๐‘ฃ) โ†’ ๐‘ช๐’๐’๐’” ๐‘ฅ (๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! ๐‘“ ๐‘ฃ) Sometimes it is convenient to provide the single argument of ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟโ€ฒ as three components: a predicate indicating when that argument should return ๐‘ต๐’๐’•๐’‰๐’Š๐’๐’ˆ, and two functions yielding the two components of the pair when it does not. The resulting function ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ takes a predicate ๐‘ indicating when the seed should unfold to the empty list, and for when this fails to hold, functions ๐‘“ giving the head of the list and ๐‘” giving the seed from which to unfold the tail: ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ โˆท ๐›ฝ โ†’ ๐‘ฉ๐’๐’๐’ โ†’ (๐›ฝ โ†’ ๐›ผ) โ†’ (๐›ฝ โ†’ ๐›ฝ) โ†’ ๐›ฝ โ†’ ๐‘ณ๐’Š๐’”๐’• ๐›ผ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ ๐‘ ๐‘“ ๐‘” ๐‘ = ๐ข๐Ÿ ๐‘ ๐‘ ๐ญ๐ก๐ž๐ง ๐‘ต๐’Š๐’ ๐ž๐ฅ๐ฌ๐ž ๐‘ช๐’๐’๐’” (๐‘“ ๐‘) (๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ ๐‘ ๐‘“ ๐‘” (๐‘” ๐‘)) Conversely, one could define a function ๐‘“๐‘œ๐‘™๐‘‘๐ฟ! taking a single argument of type ๐‘ด๐’‚๐’š๐’ƒ๐’† (๐›ผ, ๐›ฝ) โ†’ ๐›ฝ in place of ๐‘“๐‘œ๐‘™๐‘‘๐ฟโ€™s two arguments : ๐‘“๐‘œ๐‘™๐‘‘๐ฟ! โˆท (๐‘ด๐’‚๐’š๐’ƒ๐’† (๐›ผ, ๐›ฝ) โ†’ ๐›ฝ) โ†’ ๐‘ณ๐’Š๐’”๐’• ๐›ผ โ†’ ๐›ฝ ๐‘“๐‘œ๐‘™๐‘‘๐ฟ! ๐‘“ ๐‘ต๐’Š๐’ = ๐‘“ ๐‘ต๐’๐’•๐’‰๐’Š๐’๐’ˆ ๐‘“๐‘œ๐‘™๐‘‘๐ฟโ€ฒ ๐‘“ ๐‘ช๐’๐’๐’” ๐‘ฅ ๐‘ฅ๐‘  = ๐‘“ (๐‘ฑ๐’–๐’”๐’• ๐‘ฅ, ๐‘“๐‘œ๐‘™๐‘‘๐ฟโ€ฒ ๐‘“ ๐‘ฅ๐‘ ) These primed versions make the duality between the fold and the unfold very clear, although they may sometimes be less convenient for programming with. ๐‘“๐‘œ๐‘™๐‘‘๐ฟ โˆท ๐›ผ โ†’ ๐›ฝ โ†’ ๐›ฝ โ†’ ๐›ฝ โ†’ ๐‘ณ๐’Š๐’”๐’• ๐›ผ โ†’ ๐›ฝ ๐‘“๐‘œ๐‘™๐‘‘๐ฟ ๐‘“ ๐‘’ ๐‘ต๐’Š๐’ = ๐‘’ ๐‘“๐‘œ๐‘™๐‘‘๐ฟ ๐‘“ ๐‘’ ๐‘ช๐’๐’๐’” ๐‘ฅ ๐‘ฅ๐‘  = ๐‘“ ๐‘ฅ ๐‘“๐‘œ๐‘™๐‘‘๐ฟ ๐‘“ ๐‘’ ๐‘ฅ๐‘  foldr foldRight unfoldr unfold
  15. ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! โˆท ๐›ฝ โ†’ ๐‘ด๐’‚๐’š๐’ƒ๐’† (๐›ผ, ๐›ฝ) โ†’ ๐›ฝ โ†’

    ๐‘ณ๐’Š๐’”๐’• ๐›ผ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! ๐‘“ ๐‘ข = ๐œ๐š๐ฌ๐ž ๐‘“ ๐‘ข ๐จ๐Ÿ ๐‘ต๐’๐’•๐’‰๐’Š๐’๐’ˆ โ†’ ๐‘ต๐’Š๐’ ๐‘ฑ๐’–๐’”๐’• (๐‘ฅ, ๐‘ฃ) โ†’ ๐‘ช๐’๐’๐’” ๐‘ฅ (๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! ๐‘“ ๐‘ฃ) ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ โˆท ๐›ฝ โ†’ ๐‘ฉ๐’๐’๐’ โ†’ (๐›ฝ โ†’ ๐›ผ) โ†’ (๐›ฝ โ†’ ๐›ฝ) โ†’ ๐›ฝ โ†’ ๐‘ณ๐’Š๐’”๐’• ๐›ผ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ ๐‘ ๐‘“ ๐‘” ๐‘ = ๐ข๐Ÿ ๐‘ ๐‘ ๐ญ๐ก๐ž๐ง ๐‘ต๐’Š๐’ ๐ž๐ฅ๐ฌ๐ž ๐‘ช๐’๐’๐’” (๐‘“ ๐‘) (๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ ๐‘ ๐‘“ ๐‘” (๐‘” ๐‘)) ๐‘“๐‘œ๐‘™๐‘‘๐ฟ โˆท ๐›ผ โ†’ ๐›ฝ โ†’ ๐›ฝ โ†’ ๐›ฝ โ†’ ๐‘ณ๐’Š๐’”๐’• ๐›ผ โ†’ ๐›ฝ ๐‘“๐‘œ๐‘™๐‘‘๐ฟ ๐‘“ ๐‘’ ๐‘ต๐’Š๐’ = ๐‘’ ๐‘“๐‘œ๐‘™๐‘‘๐ฟ ๐‘“ ๐‘’ ๐‘ช๐’๐’๐’” ๐‘ฅ ๐‘ฅ๐‘  = ๐‘“ ๐‘ฅ ๐‘“๐‘œ๐‘™๐‘‘๐ฟ ๐‘“ ๐‘’ ๐‘ฅ๐‘  ๐‘“๐‘œ๐‘™๐‘‘๐ฟ! โˆท (๐‘ด๐’‚๐’š๐’ƒ๐’† (๐›ผ, ๐›ฝ) โ†’ ๐›ฝ) โ†’ ๐‘ณ๐’Š๐’”๐’• ๐›ผ โ†’ ๐›ฝ ๐‘“๐‘œ๐‘™๐‘‘๐ฟ! ๐‘“ ๐‘ต๐’Š๐’ = ๐‘“ ๐‘ต๐’๐’•๐’‰๐’Š๐’๐’ˆ ๐‘“๐‘œ๐‘™๐‘‘๐ฟโ€ฒ ๐‘“ ๐‘ช๐’๐’๐’” ๐‘ฅ ๐‘ฅ๐‘  = ๐‘“ (๐‘ฑ๐’–๐’”๐’• ๐‘ฅ, ๐‘“๐‘œ๐‘™๐‘‘๐ฟโ€ฒ ๐‘“ ๐‘ฅ๐‘ ) ๐‘ด๐’‚๐’š๐’ƒ๐’† (๐›ผ, ๐›ฝ) ๐›ฝ ๐‘ณ๐’Š๐’”๐’• ๐›ผ ๐‘“ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! ๐‘“ ๐‘ณ๐’Š๐’”๐’• ๐›ผ ๐‘“๐‘œ๐‘™๐‘‘๐ฟโ€ฒ ๐‘“ ๐›ฝ ๐‘ด๐’‚๐’š๐’ƒ๐’† (๐›ผ, ๐›ฝ) ๐‘“ 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
  16. The next slide is based on slightly modified versions of

    two sentences from the paper Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire, which is available here https://maartenfokkinga.github.io/utwente/mmf91m.pdf
  17. ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ โˆท ๐›ฝ โ†’ ๐‘ฉ๐’๐’๐’ โ†’ (๐›ฝ โ†’ ๐›ผ) โ†’

    (๐›ฝ โ†’ ๐›ฝ) โ†’ ๐›ฝ โ†’ ๐‘ณ๐’Š๐’”๐’• ๐›ผ ๐‘“๐‘œ๐‘™๐‘‘๐ฟ โˆท ๐›ผ โ†’ ๐›ฝ โ†’ ๐›ฝ โ†’ ๐›ฝ โ†’ ๐‘ณ๐’Š๐’”๐’• ๐›ผ โ†’ ๐›ฝ 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 foldr foldRight
  18. ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ and ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! are not the only functions that can

    be used to unfold lists. There is also ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’. The next slide shows how Introduction to Functional Programming introduces the ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ function. The subsequent slide shows how ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ is implemented, and the slide after that shows how the Haskell API documentation describes the function. Richard Bird http://www.cs.ox.ac.uk/people/richard.bird/ Philip Wadler https://github.com/wadler
  19. 7.2 Iterate Recall that in mathematics, the notation ๐‘“๐‘› denotes

    a function composed with itself ๐‘› times; thus ๐‘“0 = ๐‘–๐‘‘, ๐‘“1 = ๐‘“, ๐‘“2 = ๐‘“ โˆ˜ ๐‘“ , ๐‘“3 = ๐‘“ โˆ˜ ๐‘“ โˆ˜ ๐‘“ and so on, where ๐‘–๐‘‘ is the identity function. In our notation we will write ๐‘“๐‘› as (๐‘๐‘œ๐‘ค๐‘’๐‘Ÿ ๐‘“ ๐‘›). One way to define ๐‘๐‘œ๐‘ค๐‘’๐‘Ÿ is by the equations: ๐‘๐‘œ๐‘ค๐‘’๐‘Ÿ ๐‘“ 0 = ๐‘–๐‘‘ ๐‘๐‘œ๐‘ค๐‘’๐‘Ÿ ๐‘“ ๐‘› + 1 = ๐‘“ โˆ˜ ๐‘๐‘œ๐‘ค๐‘’๐‘Ÿ ๐‘“ ๐‘› Observe that ๐‘“๐‘› is similar in form to ๐‘ฅ๐‘›, which denotes a number multiplied by itself ๐‘› times, but one should be careful not to confuse the two. The function ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ is defined informally as follows: ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ ๐‘“ ๐‘ฅ = [๐‘ฅ, ๐‘“ ๐‘ฅ, ๐‘“2๐‘ฅ, ๐‘“3๐‘ฅ, โ€ฆ ] Thus ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ takes a function and a starting value and returns an infinite list. For example: ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ +1 1 = 1, 2, 3, 4, 5, โ€ฆ ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ ร—2 1 = 1, 2, 4, 8, 16, 32, โ€ฆ ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ ๐๐ข๐ฏ 10 2718 = 2718, 271, 27, 2, 0, 0, โ€ฆ We also have: ๐‘š. . = ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ +1 ๐‘š ๐‘š. . ๐‘› = ๐‘ก๐‘Ž๐‘˜๐‘’๐‘Šโ„Ž๐‘–๐‘™๐‘’ โ‰ค ๐‘› (๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ +1 ๐‘š) These equations provide one way of defining the notations ๐‘š. . and ๐‘š. . ๐‘› . In the second equation, ๐‘ก๐‘Ž๐‘˜๐‘’๐‘Šโ„Ž๐‘–๐‘™๐‘’ is used to truncate the infinite list to a finite list.
  20. Produces an infinite list of iterated applications of a function

    to a value. ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ โˆท ๐›ผ โ†’ ๐›ผ โ†’ ๐›ผ โ†’ ๐›ผ ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ ๐‘“ ๐‘ฅ = ๐‘ฅ โˆถ ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ ๐‘“ (๐‘“ ๐‘ฅ) The definition of the ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ function on the previous slide was informal. Here is a formal definition (there are also alternative ones).
  21. ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ โˆท ๐›ผ โ†’ ๐›ผ โ†’ ๐›ผ โ†’ ๐›ผ ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’

    ๐‘“ ๐‘ฅ = ๐‘ฅ โˆถ ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ ๐‘“ (๐‘“ ๐‘ฅ)
  22. It turns out that iterate is just a special case

    of ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ and ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ!. The way we are going to illustrate this is by looking at a digits function which given a positive integer number, returns a list of the numberโ€™s digits. In the next three slides, we are going to see how, in The Science of Functional Programming, Sergei Winitzki introduces iterate and uses it to implement digits (which he calls digitsOf). Sergei Winitzki sergei-winitzki-11a6431
  23. 2.3 Generating a sequence from a single value An aggregation

    converts (โ€œfoldsโ€) a sequence into a single value; the opposite operation (โ€œunfoldingโ€) builds a new sequence from a single value and other needed information. An example is computing the decimal digits of a given integer: def digitsOf(x: Int): Seq[Int] = ??? scala> digitsOf(2405) res0: Seq[Int] = List(2, 4, 0, 5) We cannot implement digitsOf using map, zip, or foldLeft, because these methods work only if we already have a sequence; but the function digitsOf needs to create a new sequence. We could create a sequence via the expression (1 to n) if the required length of the sequence were known in advance. However, the function digitsOf must produce a sequence whose length is determined by a condition that we cannot easily evaluate in advance. A general โ€œunfoldingโ€ operation needs to build a sequence whose length is not determined in advance. This kind of sequence is called a stream. The elements of a stream are computed only when necessary (unlike the elements of List or Array, which are all computed in advance). The unfolding operation will compute next elements on demand; this creates a stream. We can then apply takeWhile to the stream, in order to stop it when a certain condition holds. Finally, if required, the truncated stream may be converted to a list or another type of sequence. In this way, we can generate a sequence of initially unknown length according to any given requirements. The Scala library has a general stream-producing function Stream.iterate2. This function has two arguments, the initial value and a function that computes the next value from the previous one: scala> Stream.iterate(2) { x => x + 10 } res0: Stream[Int] = Stream(2, ?) The stream is ready to start computing the next elements of the sequence (so far, only the first element, 2, has been computed). 2 In a future version of Scala 3, the Stream class will be replaced by LazyList.
  24. In order to see the next elements, we need to

    stop the stream at a finite size and then convert the result to a list: scala> Stream.iterate(2) { x => x + 10 }.take(6).toList res1: List[Int] = List(2, 12, 22, 32, 42, 52) If we try to evaluate toList on a stream without first limiting its size via take or takeWhile, the program will keep producing more elements until it runs out of memory and crashes. Streams are similar to sequences, and methods such as map, filter, and flatMap are also defined for streams. For instance, the method drop skips a given number of initial elements: scala> Seq(10, 20, 30, 40, 50).drop(3) res2: Seq[Int] = List(40, 50) scala> Stream.iterate(2) { x => x + 10 }.drop(3) res3: Stream[Int] = Stream(32, ?) To figure out the code for digitsOf, we first write this function as a mathematical formula. To compute the digits for, say, n = 2405, we need to divide n repeatedly by 10, getting a sequence nk of intermediate numbers (n0 = 2405, n1 = 240, ...) and the corresponding sequence of last digits, nk mod 10 (in this example: 5, 0, ...). The sequence nk is defined using mathematical induction: โ€ข Base case: n0 = n, where n is the given initial integer. โ€ข Inductive step: nk+1 = nk 10 for k = 1, 2, ... Here nk 10 is the mathematical notation for the integer division by 10. Let us tabulate the evaluation of the sequence nk for n = 2405: The numbers nk will remain all zeros after k = 4. It is clear that the useful part of the sequence is before it becomes all zeros. In this example, the sequence nk needs to be stopped at k = 4. The sequence of digits then becomes [5, 0, 4, 2], and we need to reverse it to obtain [2, 4, 0, 5]. For reversing a sequence, the Scala library has the standard method reverse.
  25. So, a complete implementation for digitsOf is: def digitsOf(n: Int):

    Seq[Int] = if (n == 0) Seq(0) else { // n == 0 is a special case. Stream.iterate(n) { nk => nk / 10 } .takeWhile { nk => nk != 0 } .map { nk => nk % 10 } .toList.reverse } We can shorten the code by using the syntax such as (_ % 10) instead of { nk => nk % 10 }, def digitsOf(n: Int): Seq[Int] = if (n == 0) Seq(0) else { // n == 0 is a special case. Stream.iterate(n) (_ / 10 ) .takeWhile ( _ != 0 ) .map ( _ % 10 ) .toList.reverse } The type signature of the method Stream.iterate can be written as def iterate[A](init: A)(next: A => A): Stream[A] and shows a close correspondence to a definition by mathematical induction. The base case is the first value, init, and the inductive step is a function, next, that computes the next element from the previous one. It is a general way of creating sequences whose length is not determined in advance.
  26. Earlier we saw that when Introduction to Functional Programming introduces

    the iterate function, it provides some simple examples of its usage. As shown on the next slide, the next thing the book does is introduce two more interesting examples, the first of which is the digits function.
  27. Here are some more examples of the use of iterate.

    First, the digits of a positive integer can be extracted by a function digits defined as follows: digits = reverse โˆ˜ map (mod 10) โˆ˜ takewhile (/= 0) โˆ˜ iterate (div 10) For example, digits 2718 = (reverse โˆ˜ map (mod 10) โˆ˜ takewhile (/= 0)) [2718, 271, 27, 2, 0, 0, โ€ฆ] = (reverse โˆ˜ map (mod 10)) [2718, 271, 27, 2] = reverse [8, 1, 7, 2] = [2, 7, 1, 8] Next, consider the function (group n) which breaks a list into segments of length n. group n = map (take n) โˆ˜ takewhile (/= []) โˆ˜ iterate (drop n) If the original list does not have a length that is evenly divisible by n, then the last segment will have length strictly less than n.
  28. def digits(n: Int): List[Int] = LazyList.iterate(n)(_ / 10).takeWhile(_ != 0).map(_

    % 10).toList.reverse digits :: Int -> [Int] digits = reverse . map (`mod` 10) . takeWhile (/= 0) . iterate (`div` 10) Here are the Haskell and Scala versions of the digits function next to each other > digits 2718 [2,7,1,8] scala> digits(2718) val res0: List[Int] = List(2,7,1,8) group :: Eq a => Int -> [a] -> [[a]] group n = map (take n) . takeWhile (/= []) . iterate (drop n) > group 3 [1,2,3,4,5,6,7,8,9,10,11] [[1,2,3],[4,5,6],[7,8,9],[10,11]] def group[A](n: Int, as: List[A]): List[List[A]] = LazyList.iterate(as)(_.drop(n)).takeWhile(_.nonEmpty).map(_.take(n)).toList scala> group(3, List(1,2,3,4,5,6,7,8,9,10,11)) val res16: List[List[Int]] = List(List(1,2,3),List(4,5,6),List(7,8,9),List(10,11)) Similarly for the group function. ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ โˆท ๐›ผ โ†’ ๐›ผ โ†’ ๐›ผ โ†’ ๐›ผ ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ ๐‘“ ๐‘ฅ = ๐‘ฅ โˆถ ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ ๐‘“ (๐‘“ ๐‘ฅ)
  29. On the next slide, we see Introduction to Functional Programming

    introducing the unfold function, which is spoken of speculatively, and not mentioned again in the book.
  30. As the last two examples suggest, one often finds map,

    takewhile and iterate composed together in sequence. Suppose we capture this pattern of computation as a generic function, ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ say, defined as follows: ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ โ„Ž ๐‘ ๐‘ก = ๐‘š๐‘Ž๐‘ โ„Ž โˆ˜ ๐‘ก๐‘Ž๐‘˜๐‘’๐‘คโ„Ž๐‘–๐‘™๐‘’ ๐‘ โˆ˜ ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ ๐‘ก The key feature about ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ is that it is a general function for producing lists. Moreover, the functions โ„Ž, ๐‘ก and ๐‘ correspond to simple operations on lists. We have โ„Ž๐‘‘ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ โ„Ž ๐‘ ๐‘ก ๐‘ฅ = โ„Ž ๐‘ฅ ๐‘ก๐‘™ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ โ„Ž ๐‘ ๐‘ก ๐‘ฅ = ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ โ„Ž ๐‘ ๐‘ก (๐‘ก ๐‘ฅ) ๐‘›๐‘œ๐‘›๐‘›๐‘ข๐‘™๐‘™ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ โ„Ž ๐‘ ๐‘ก ๐‘ฅ = ๐‘ ๐‘ฅ Thus, the first argument โ„Ž of ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ is a function that corresponds to โ„Ž๐‘‘, the third function, ๐‘ก, corresponds to ๐‘ก๐‘™, and the second function, ๐‘, to a predicate which tests whether the list is empty or not. Letโ€™s implement the unfold function. Weโ€™ll use it in the next two slides. 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) ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ โˆท (๐›ฝ โ†’ ๐›ผ) โ†’ ๐›ฝ โ†’ ๐‘ฉ๐’๐’๐’ โ†’ (๐›ฝ โ†’ ๐›ฝ) โ†’ ๐›ฝ โ†’ ๐‘ณ๐’Š๐’”๐’• ๐›ผ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ โ„Ž ๐‘ ๐‘ก = ๐‘š๐‘Ž๐‘ โ„Ž โˆ˜ ๐‘ก๐‘Ž๐‘˜๐‘’๐‘คโ„Ž๐‘–๐‘™๐‘’ ๐‘ โˆ˜ ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ ๐‘ก
  31. Remember the digits function implemented a few slides ago using

    the iterate function? Letโ€™s reimplement it using ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘. The result is much simpler thanks to ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ capturing the pattern of computation involving map, takewhile and iterate . > digits = reverse . unfold (`mod` 10) (/= 0) (`div` 10) > digits 2718 [2,7,1,8] def digits(n: Int): List[Int] = LazyList.iterate(n)(_ / 10).takeWhile(_ != 0).map(_ % 10).toList.reverse digits :: Int -> [Int] digits = reverse . map (`mod` 10) . takeWhile (/= 0) . iterate (`div` 10) scala> def digits(n: Int): List[Int] = | unfold[Int,Int](_ % 10, _ != 0, _ / 10, n).toList.reverse | def digits(n: Int): List[Int] scala> digits(2718) val res0: List[Int] = List(2, 7, 1, 8) ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ โˆท (๐›ฝ โ†’ ๐›ผ) โ†’ ๐›ฝ โ†’ ๐‘ฉ๐’๐’๐’ โ†’ (๐›ฝ โ†’ ๐›ฝ) โ†’ ๐›ฝ โ†’ ๐‘ณ๐’Š๐’”๐’• ๐›ผ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ โ„Ž ๐‘ ๐‘ก = ๐‘š๐‘Ž๐‘ โ„Ž โˆ˜ ๐‘ก๐‘Ž๐‘˜๐‘’๐‘คโ„Ž๐‘–๐‘™๐‘’ ๐‘ โˆ˜ ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ ๐‘ก
  32. def group[A](n: Int, as: List[A]): List[List[A]] = unfold[List[A],List[A]](_.take(n), _.nonEmpty, _.drop(n),

    as).toList scala> group(3, List(1,2,3,4,5,6,7,8,9,10,11)) val res0: List[List[Int]] = List(List(1, 2, 3), List(4, 5, 6), List(7, 8, 9), List(10, 11)) > group n = unfold (take n) (/= []) (drop n) > group 3 [1,2,3,4,5,6,7,8,9,10,11] [[1,2,3],[4,5,6],[7,8,9],[10,11]] Remember the group function implemented a few of slides ago using the iterate function? Letโ€™s also reimplement it using ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘. Again, the result is much simpler thanks to ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ capturing the pattern of computation involving map, takewhile and iterate . def group[A](n: Int, as: List[A]): List[List[A]] = LazyList.iterate(as)(_.drop(n)).takeWhile(_.nonEmpty).map(_.take(n)).toList group :: Eq a => Int -> [a] -> [[a]] group n = map (take n) . takeWhile (/= []) . iterate (drop n) ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ โˆท (๐›ฝ โ†’ ๐›ผ) โ†’ ๐›ฝ โ†’ ๐‘ฉ๐’๐’๐’ โ†’ (๐›ฝ โ†’ ๐›ฝ) โ†’ ๐›ฝ โ†’ ๐‘ณ๐’Š๐’”๐’• ๐›ผ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ โ„Ž ๐‘ ๐‘ก = ๐‘š๐‘Ž๐‘ โ„Ž โˆ˜ ๐‘ก๐‘Ž๐‘˜๐‘’๐‘คโ„Ž๐‘–๐‘™๐‘’ ๐‘ โˆ˜ ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ ๐‘ก
  33. We have seen thar ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ is defined in terms of

    map, takewhile and iterate. What about defining iterate in terms of ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ ? It looks like this should work, right? ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ โˆท ๐›ผ โ†’ ๐›ผ โ†’ ๐›ผ โ†’ ๐›ผ ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ = ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ ๐‘–๐‘‘ ๐‘๐‘œ๐‘›๐‘ ๐‘ก ๐‘‡๐‘Ÿ๐‘ข๐‘’ Yes, it does: iterate' :: (a -> a) -> a -> [a] iterate' = unfold id (const True) > take 10 (iterate' (+1) 1) [1,2,3,4,5,6,7,8,9,10] ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ โˆท (๐›ฝ โ†’ ๐›ผ) โ†’ ๐›ฝ โ†’ ๐‘ฉ๐’๐’๐’ โ†’ (๐›ฝ โ†’ ๐›ฝ) โ†’ ๐›ฝ โ†’ ๐‘ณ๐’Š๐’”๐’• ๐›ผ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ โ„Ž ๐‘ ๐‘ก = ๐‘š๐‘Ž๐‘ โ„Ž โˆ˜ ๐‘ก๐‘Ž๐‘˜๐‘’๐‘คโ„Ž๐‘–๐‘™๐‘’ ๐‘ โˆ˜ ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ ๐‘ก
  34. ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ โˆท ๐›ฝ โ†’ ๐‘ฉ๐’๐’๐’ โ†’ (๐›ฝ โ†’ ๐›ผ) โ†’

    (๐›ฝ โ†’ ๐›ฝ) โ†’ ๐›ฝ โ†’ ๐‘ณ๐’Š๐’”๐’• ๐›ผ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ ๐‘ ๐‘“ ๐‘” ๐‘ = ๐ข๐Ÿ ๐‘ ๐‘ ๐ญ๐ก๐ž๐ง ๐‘ต๐’Š๐’ ๐ž๐ฅ๐ฌ๐ž ๐‘ช๐’๐’๐’” (๐‘“ ๐‘) (๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ ๐‘ ๐‘“ ๐‘” (๐‘” ๐‘)) It looks like apart from some renaming and reordering of parameters, and the inversion of the condition tested by predicate function ๐‘, the ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ function is equivalent to the ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ function. ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ โˆท (๐›ฝ โ†’ ๐›ผ) โ†’ ๐›ฝ โ†’ ๐‘ฉ๐’๐’๐’ โ†’ (๐›ฝ โ†’ ๐›ฝ) โ†’ ๐›ฝ โ†’ ๐‘ณ๐’Š๐’”๐’• ๐›ผ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ โ„Ž ๐‘ ๐‘ก = ๐‘š๐‘Ž๐‘ โ„Ž โˆ˜ ๐‘ก๐‘Ž๐‘˜๐‘’๐‘คโ„Ž๐‘–๐‘™๐‘’ ๐‘ โˆ˜ ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ ๐‘ก And we already know that ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ is equivalent to ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟโ€™. So on the next slide, letโ€™s reimplement digits and group using ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟโ€™. ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! โˆท ๐›ฝ โ†’ ๐‘ด๐’‚๐’š๐’ƒ๐’† (๐›ผ, ๐›ฝ) โ†’ ๐›ฝ โ†’ ๐‘ณ๐’Š๐’”๐’• ๐›ผ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! ๐‘“ ๐‘ข = ๐œ๐š๐ฌ๐ž ๐‘“ ๐‘ข ๐จ๐Ÿ ๐‘ต๐’๐’•๐’‰๐’Š๐’๐’ˆ โ†’ ๐‘ต๐’Š๐’ ๐‘ฑ๐’–๐’”๐’• (๐‘ฅ, ๐‘ฃ) โ†’ ๐‘ช๐’๐’๐’” ๐‘ฅ (๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! ๐‘“ ๐‘ฃ) unfoldr unfold
  35. > digits = reverse . unfoldr gen where gen 0

    = Nothing gen d = Just (d `mod` 10, d `div` 10) > digits 2718 [2,7,1,8] > group n = unfoldr gen where gen [] = Nothing gen xs = Just (take n xs, drop n xs) > group 3 [1,2,3,4,5,6,7,8,9,10,11] [[1,2,3],[4,5,6],[7,8,9],[10,11]] ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! โˆท ๐›ฝ โ†’ ๐‘ด๐’‚๐’š๐’ƒ๐’† (๐›ผ, ๐›ฝ) โ†’ ๐›ฝ โ†’ ๐‘ณ๐’Š๐’”๐’• ๐›ผ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! ๐‘“ ๐‘ข = ๐œ๐š๐ฌ๐ž ๐‘“ ๐‘ข ๐จ๐Ÿ ๐‘ต๐’๐’•๐’‰๐’Š๐’๐’ˆ โ†’ ๐‘ต๐’Š๐’ ๐‘ฑ๐’–๐’”๐’• (๐‘ฅ, ๐‘ฃ) โ†’ ๐‘ช๐’๐’๐’” ๐‘ฅ (๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! ๐‘“ ๐‘ฃ) scala> def digits(n: Int): List[Int] = | LazyList.unfold(n): | case 0 => None | case x => Some(x % 10, x / 10) | .toList.reverse | def digits(n: Int): List[Int] scala> digits(2718) val res0: List[Int] = List(2, 7, 1, 8) scala> def group[A](n: Int, as: List[A]): List[List[A]] = | LazyList.unfold(as): | case Nil => None | case xs => Some(xs.take(n), xs.drop(n)) | .toList | def group[A](n: Int, as: List[A]): List[List[A]] scala> group(3, List(1,2,3,4,5,6,7,8,9,10,11)) val res0: List[List[Int]]=List(List(1,2,3),List(4,5,6),List(7,8,9),List(10,11)) unfoldr unfold
  36. def digits(n: Int): List[Int] = LazyList.unfold(n): case 0 => None

    case x => Some(x % 10, x / 10) .toList.reverse def digits(n: Int): List[Int] = LazyList.unfold(n): x => Option.unless(x==0)(x % 10, x / 10) .toList.reverse def group[A](n: Int, as: List[A]): List[List[A]] = LazyList.unfold(as): case Nil => None case xs => Some(xs.take(n), xs.drop(n)) .toList def group[A](n: Int, as: List[A]): List[List[A]] = LazyList.unfold(as): xs => Option.unless(xs.isEmpty)(xs.take(n), xs.drop(n)) .toList As an aside, Scala functions digits and group, may alternatively be written as follows
  37. Earlier we looked at how to define iterate in terms

    of ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘. Implementing iterate in terms of unfoldL is very similar, because ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ and ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ are very similar: ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ โˆท ๐›ผ โ†’ ๐›ผ โ†’ ๐›ผ โ†’ ๐›ผ ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ = ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ ๐‘๐‘œ๐‘›๐‘ ๐‘ก ๐น๐‘Ž๐‘™๐‘ ๐‘’ ๐‘–๐‘‘ What about defining iterate in terms of ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ!? The answer below can be found on the next slide, in the documentation of Haskellโ€™s equivalent of unfoldLโ€™ ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ โˆท ๐›ผ โ†’ ๐›ผ โ†’ ๐›ผ โ†’ ๐›ผ ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ ๐‘“ = ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟโ€ฒ ๐œ†๐‘ฅ. ๐ฝ๐‘ข๐‘ ๐‘ก (๐‘ฅ, ๐‘“ ๐‘ฅ) ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! โˆท ๐›ฝ โ†’ ๐‘ด๐’‚๐’š๐’ƒ๐’† (๐›ผ, ๐›ฝ) โ†’ ๐›ฝ โ†’ ๐‘ณ๐’Š๐’”๐’• ๐›ผ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! ๐‘“ ๐‘ข = ๐œ๐š๐ฌ๐ž ๐‘“ ๐‘ข ๐จ๐Ÿ ๐‘ต๐’๐’•๐’‰๐’Š๐’๐’ˆ โ†’ ๐‘ต๐’Š๐’ ๐‘ฑ๐’–๐’”๐’• (๐‘ฅ, ๐‘ฃ) โ†’ ๐‘ช๐’๐’๐’” ๐‘ฅ (๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! ๐‘“ ๐‘ฃ) unfoldr unfold ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ โˆท ๐›ฝ โ†’ ๐‘ฉ๐’๐’๐’ โ†’ (๐›ฝ โ†’ ๐›ผ) โ†’ (๐›ฝ โ†’ ๐›ฝ) โ†’ ๐›ฝ โ†’ ๐‘ณ๐’Š๐’”๐’• ๐›ผ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ ๐‘ ๐‘“ ๐‘” ๐‘ = ๐ข๐Ÿ ๐‘ ๐‘ ๐ญ๐ก๐ž๐ง ๐‘ต๐’Š๐’ ๐ž๐ฅ๐ฌ๐ž ๐‘ช๐’๐’๐’” (๐‘“ ๐‘) (๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ ๐‘ ๐‘“ ๐‘” (๐‘” ๐‘))
  38. ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! โˆท ๐›ฝ โ†’ ๐‘ด๐’‚๐’š๐’ƒ๐’† (๐›ผ, ๐›ฝ) โ†’ ๐›ฝ โ†’

    ๐‘ณ๐’Š๐’”๐’• ๐›ผ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! ๐‘“ ๐‘ข = ๐œ๐š๐ฌ๐ž ๐‘“ ๐‘ข ๐จ๐Ÿ ๐‘ต๐’๐’•๐’‰๐’Š๐’๐’ˆ โ†’ ๐‘ต๐’Š๐’ ๐‘ฑ๐’–๐’”๐’• (๐‘ฅ, ๐‘ฃ) โ†’ ๐‘ช๐’๐’๐’” ๐‘ฅ (๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! ๐‘“ ๐‘ฃ) ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ โˆท ๐›ผ โ†’ ๐›ผ โ†’ ๐›ผ โ†’ ๐›ผ ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ ๐‘“ ๐‘ฅ = ๐‘ฅ โˆถ ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ ๐‘“ (๐‘“ ๐‘ฅ) unfoldr unfold
  39. Earlier we saw that ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ is defined in terms of

    map, takewhile and iterate. ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ โˆท (๐›ฝ โ†’ ๐›ผ) โ†’ ๐›ฝ โ†’ ๐ต๐‘œ๐‘œ๐‘™ โ†’ (๐›ฝ โ†’ ๐›ฝ) โ†’ ๐›ฝ โ†’ ๐‘ณ๐’Š๐’”๐’• ๐›ผ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ โ„Ž ๐‘ ๐‘ก = ๐‘š๐‘Ž๐‘ โ„Ž โˆ˜ ๐‘ก๐‘Ž๐‘˜๐‘’๐‘คโ„Ž๐‘–๐‘™๐‘’ ๐‘ โˆ˜ ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ ๐‘ก What about ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ? It looks like this should work, right? ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ ๐‘ ๐‘“ ๐‘” = ๐‘š๐‘Ž๐‘ ๐‘“ โˆ˜ ๐‘ก๐‘Ž๐‘˜๐‘’๐‘Šโ„Ž๐‘–๐‘™๐‘’ (๐‘›๐‘œ๐‘ก โˆ˜ ๐‘) โˆ˜ ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ ๐‘” Yes, it does. Just like with ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘, implementing digits and group using ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ is much simpler thanks to ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ capturing the pattern of computation involving map, takewhile and iterate . > unfoldL p f g = map f . takeWhile (not . p) . iterate g > digits = reverse . unfoldL (==0) (`mod` 10) (`div` 10) > digits 2718 [2,7,1,8] > group n = unfoldL (==[]) (take n) (drop n) > group 3 [1,2,3,4,5,6,7,8,9,10,11] [[1,2,3],[4,5,6],[7,8,9],[10,11]] ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ โˆท ๐›ฝ โ†’ ๐‘ฉ๐’๐’๐’ โ†’ (๐›ฝ โ†’ ๐›ผ) โ†’ (๐›ฝ โ†’ ๐›ฝ) โ†’ ๐›ฝ โ†’ ๐‘ณ๐’Š๐’”๐’• ๐›ผ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ ๐‘ ๐‘“ ๐‘” ๐‘ = ๐ข๐Ÿ ๐‘ ๐‘ ๐ญ๐ก๐ž๐ง ๐‘ต๐’Š๐’ ๐ž๐ฅ๐ฌ๐ž ๐‘ช๐’๐’๐’” (๐‘“ ๐‘) (๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ ๐‘ ๐‘“ ๐‘” (๐‘” ๐‘))
  40. The next slide recaps the different ways of writing a

    function to unfold a list by using ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’, ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘, ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ and ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟโ€ฒ. The slide after that recaps how ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ and ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟโ€ฒ relate to ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’.
  41. digits = reverse . map (`mod` 10) . takeWhile (/=

    0) . iterate (`div` 10) digits = reverse . unfold (`mod` 10) (/= 0) (`div` 10) digits = reverse . unfoldL (== 0) (`mod` 10) (`div` 10) digits = reverse . unfoldr gen where gen 0 = Nothing gen d = Just (d `mod` 10, d `div` 10) Here are the four different implementations of digits that we have considered (we have not actually bothered with the third Scala one, due to it being very similar to the second one). In the two succinct middle ones, we are relying on our own implementation of ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ and ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ, since as far as I can tell, they are not provided by Haskell and Scala. 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] = unfoldL[Int,Int](_ == 0, _ % 10, _ / 10, n).toList.reverse def digits(n: Int): List[Int] = LazyList.unfold(n): x => Option.unless(x==0)(x % 10, x / 10) .toList.reverse ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟโ€ฒ ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟโ€ฒ
  42. ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ โˆท ๐›ผ โ†’ ๐›ผ โ†’ ๐›ผ โ†’ ๐›ผ ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’

    ๐‘“ ๐‘ฅ = ๐‘ฅ โˆถ ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ ๐‘“ (๐‘“ ๐‘ฅ) ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ ๐‘“ = ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ ๐‘๐‘œ๐‘›๐‘ ๐‘ก ๐น๐‘Ž๐‘™๐‘ ๐‘’ ๐‘–๐‘‘ ๐‘“ ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ ๐‘“ = ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟโ€ฒ ๐œ†๐‘ฅ. ๐ฝ๐‘ข๐‘ ๐‘ก (๐‘ฅ, ๐‘“ ๐‘ฅ) ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ ๐‘ ๐‘“ ๐‘” = ๐‘š๐‘Ž๐‘ ๐‘“ โˆ˜ ๐‘ก๐‘Ž๐‘˜๐‘’๐‘Šโ„Ž๐‘–๐‘™๐‘’ (๐‘›๐‘œ๐‘ก โˆ˜ ๐‘) โˆ˜ ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ ๐‘” ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! โˆท ๐›ฝ โ†’ ๐‘ด๐’‚๐’š๐’ƒ๐’† (๐›ผ, ๐›ฝ) โ†’ ๐›ฝ โ†’ ๐‘ณ๐’Š๐’”๐’• ๐›ผ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! ๐‘“ ๐‘ข = ๐œ๐š๐ฌ๐ž ๐‘“ ๐‘ข ๐จ๐Ÿ ๐‘ต๐’๐’•๐’‰๐’Š๐’๐’ˆ โ†’ ๐‘ต๐’Š๐’ ๐‘ฑ๐’–๐’”๐’• (๐‘ฅ, ๐‘ฃ) โ†’ ๐‘ช๐’๐’๐’” ๐‘ฅ (๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ! ๐‘“ ๐‘ฃ) ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ โˆท ๐›ฝ โ†’ ๐‘ฉ๐’๐’๐’ โ†’ (๐›ฝ โ†’ ๐›ผ) โ†’ (๐›ฝ โ†’ ๐›ฝ) โ†’ ๐›ฝ โ†’ ๐‘ณ๐’Š๐’”๐’• ๐›ผ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ ๐‘ ๐‘“ ๐‘” ๐‘ = ๐ข๐Ÿ ๐‘ ๐‘ ๐ญ๐ก๐ž๐ง ๐‘ต๐’Š๐’ ๐ž๐ฅ๐ฌ๐ž ๐‘ช๐’๐’๐’” (๐‘“ ๐‘) (๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ ๐‘ ๐‘“ ๐‘” (๐‘” ๐‘)) unfoldr unfold ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ โˆท (๐›ฝ โ†’ ๐›ผ) โ†’ ๐›ฝ โ†’ ๐‘ฉ๐’๐’๐’ โ†’ (๐›ฝ โ†’ ๐›ฝ) โ†’ ๐›ฝ โ†’ ๐‘ณ๐’Š๐’”๐’• ๐›ผ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘ โ„Ž ๐‘ ๐‘ก = ๐‘š๐‘Ž๐‘ โ„Ž โˆ˜ ๐‘ก๐‘Ž๐‘˜๐‘’๐‘คโ„Ž๐‘–๐‘™๐‘’ ๐‘ โˆ˜ ๐‘–๐‘ก๐‘’๐‘Ÿ๐‘Ž๐‘ก๐‘’ ๐‘ก
  43. The ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ function also makes an appearance in one of

    the exercises in Graham Huttonโ€™s book, Programming in Haskell. His example of unfolding a number into binary digits only differs from our example of unfolding a number in to decimal digits in that he doesnโ€™t need to reverse the result of the unfolding because he doesnโ€™t require the binary digits to be ordered from most significant to least significant. A higher-order function unfold that encapsulates a simple pattern of recursion for producing a list can be defined as follows: unfold p h t x | p x = [] | otherwise = h x : unfold p h t (t x) That is, the function unfold p h t produces the empty list if the predicate p is true of the argument value, and otherwise produces a non-empty list by applying the function h to this value to give the head, and the function t to generate another argument that is recursively processed in the same way to produce the tail of the list. For example, the function int2bin can be rewritten more compactly using unfold as follows: int2bin = unfold (== 0) (โ€˜modโ€˜ 2) (โ€˜divโ€˜ 2) Redefine the functions chop8, map f and iterate f using unfold. ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ โˆท ๐›ฝ โ†’ ๐‘ฉ๐’๐’๐’ โ†’ (๐›ฝ โ†’ ๐›ผ) โ†’ (๐›ฝ โ†’ ๐›ฝ) โ†’ ๐›ฝ โ†’ ๐‘ณ๐’Š๐’”๐’• ๐›ผ ๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ ๐‘ ๐‘“ ๐‘” ๐‘ = ๐ข๐Ÿ ๐‘ ๐‘ ๐ญ๐ก๐ž๐ง ๐‘ต๐’Š๐’ ๐ž๐ฅ๐ฌ๐ž ๐‘ช๐’๐’๐’” (๐‘“ ๐‘) (๐‘ข๐‘›๐‘“๐‘œ๐‘™๐‘‘๐ฟ ๐‘ ๐‘“ ๐‘” (๐‘” ๐‘)) > unfoldL p f g = map f . takeWhile (not . p) . iterate g > digits = reverse . unfoldL (==0) (`mod` 10) (`div` 10) > digits 2718 [2,7,1,8] Graham Hutton @haskellhutt
  44. While in part 1 of the The Science of Functional

    Programming, Sergei Winitzki doesnโ€™t mention the unfold function provided by Scala, this may be because the function was introduced in Scala 2.13 (in June 2019), i.e. about 1.5 years after the first code commit for the book (in Oct 2017). Sergei does discuss the unfold function in the bookโ€™s exercises (see below). Also, in upcoming part 2 of the book I see there is a section called 12.2.8 Using recursion schemes. II. Unfolding operations. Example 2.5.1.7 Implement a function unfold with the type signature def unfold[A](init: A)(next: A => Option[A]): Stream[A] The function should create a stream of values of type A with the initial value init. Next elements are computed from previous ones via the function next until it returns None. โ€ฆ Exercise 2.5.2.13 Implement a function unfold2 with the type signature def unfold2[A,B](init: A)(next: A => Option[(A,B)]): Stream[B] The function should create a stream of values of type B by repeatedly applying the given function next until it returns None. At each iteration, next should be applied to the value of type A returned by the previous call to next. An example test: scala> unfold2(0) { x => if (x > 5) None else Some((x + 2, s"had $x")) } res0: Stream[String] = Stream(had 0, ?) scala> res0.toList res1: List[String] = List(had 0, had 2, had 4)