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"

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. Let’s look at some examples of unfolding.
10. 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
11. 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, generates the sum of 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.
12. 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
13. 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)
14. 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 two slides for the answer.
15. 𝑢𝑛𝑓𝑜𝑙𝑑𝐿! ∷ 𝛽 → 𝑴𝒂𝒚𝒃𝒆 (𝛼, 𝛽) → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 𝑢𝑛𝑓𝑜𝑙𝑑𝐿! 𝑓 𝑢 = 𝐜𝐚𝐬𝐞 𝑓 𝑢 𝐨𝐟 𝑵𝒐𝒕𝒉𝒊𝒏𝒈 → 𝑵𝒊𝒍 𝑱𝒖𝒔𝒕 (𝑥, 𝑣) → 𝑪𝒐𝒏𝒔 𝑥 (𝑢𝑛𝑓𝑜𝑙𝑑𝐿! 𝑓 𝑣) 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
16. The next slide aims to reinforce the notion of duality seen on the previous slide.
17. 𝑢𝑛𝑓𝑜𝑙𝑑𝐿! ∷ 𝛽 → 𝑴𝒂𝒚𝒃𝒆 (𝛼, 𝛽) → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 𝑢𝑛𝑓𝑜𝑙𝑑𝐿! 𝑓 𝑢 = 𝐜𝐚𝐬𝐞 𝑓 𝑢 𝐨𝐟 𝑵𝒐𝒕𝒉𝒊𝒏𝒈 → 𝑵𝒊𝒍 𝑱𝒖𝒔𝒕 (𝑥, 𝑣) → 𝑪𝒐𝒏𝒔 𝑥 (𝑢𝑛𝑓𝑜𝑙𝑑𝐿! 𝑓 𝑣) 𝑢𝑛𝑓𝑜𝑙𝑑𝐿 ∷ 𝛽 → 𝑩𝒐𝒐𝒍 → (𝛽 → 𝛼) → (𝛽 → 𝛽) → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 𝑢𝑛𝑓𝑜𝑙𝑑𝐿 𝑝 𝑓 𝑔 𝑏 = 𝐢𝐟 𝑝 𝑏 𝐭𝐡𝐞𝐧 𝑵𝒊𝒍 𝐞𝐥𝐬𝐞 𝑪𝒐𝒏𝒔 (𝑓 𝑏) (𝑢𝑛𝑓𝑜𝑙𝑑𝐿 𝑝 𝑓 𝑔 (𝑔 𝑏)) 𝑓𝑜𝑙𝑑𝐿 ∷ 𝛼 → 𝛽 → 𝛽 → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 → 𝛽 𝑓𝑜𝑙𝑑𝐿 𝑓 𝑒 𝑵𝒊𝒍 = 𝑒 𝑓𝑜𝑙𝑑𝐿 𝑓 𝑒 𝑪𝒐𝒏𝒔 𝑥 𝑥𝑠 = 𝑓 𝑥 𝑓𝑜𝑙𝑑𝐿 𝑓 𝑒 𝑥𝑠 𝑓𝑜𝑙𝑑𝐿! ∷ (𝑴𝒂𝒚𝒃𝒆 (𝛼, 𝛽) → 𝛽) → 𝑳𝒊𝒔𝒕 𝛼 → 𝛽 𝑓𝑜𝑙𝑑𝐿! 𝑓 𝑵𝒊𝒍 = 𝑓 𝑵𝒐𝒕𝒉𝒊𝒏𝒈 𝑓𝑜𝑙𝑑𝐿′ 𝑓 𝑪𝒐𝒏𝒔 𝑥 𝑥𝑠 = 𝑓 (𝑱𝒖𝒔𝒕 𝑥, 𝑓𝑜𝑙𝑑𝐿′ 𝑓 𝑥𝑠) 𝑴𝒂𝒚𝒃𝒆 (𝛼, 𝛽) 𝛽 𝑳𝒊𝒔𝒕 𝛼 𝑓 𝑢𝑛𝑓𝑜𝑙𝑑𝐿! 𝑓 𝑳𝒊𝒔𝒕 𝛼 𝑓𝑜𝑙𝑑𝐿′ 𝑓 𝛽 𝑴𝒂𝒚𝒃𝒆 (𝛼, 𝛽) 𝑓 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
18. 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
19. 𝑢𝑛𝑓𝑜𝑙𝑑𝐿 ∷ 𝛽 → 𝑩𝒐𝒐𝒍 → (𝛽 → 𝛼) → (𝛽 → 𝛽) → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 𝑓𝑜𝑙𝑑𝐿 ∷ 𝛼 → 𝛽 → 𝛽 → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 → 𝛽 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
20. 𝑢𝑛𝑓𝑜𝑙𝑑𝐿 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
21. 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.
22. 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).
23. 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 ∷ 𝛼 → 𝛼 → 𝛼 → 𝛼 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑓 𝑥 = 𝑥 ∶ 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑓 (𝑓 𝑥)
24. 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
25. 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.
26. 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.
27. 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.
28. The next slide shows how the Scala API documentation describes the iterate function.
30. 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.
31. Here are some more example 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.
32. 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. 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 ∷ 𝛼 → 𝛼 → 𝛼 → 𝛼 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑓 𝑥 = 𝑥 ∶ 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑓 (𝑓 𝑥)
33. 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.
34. 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) 𝑢𝑛𝑓𝑜𝑙𝑑 ∷ (𝛽 → 𝛼) → 𝛽 → 𝑩𝒐𝒐𝒍 → (𝛽 → 𝛽) → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 𝑢𝑛𝑓𝑜𝑙𝑑 ℎ 𝑝 𝑡 = 𝑚𝑎𝑝 ℎ ∘ 𝑡𝑎𝑘𝑒𝑤ℎ𝑖𝑙𝑒 𝑝 ∘ 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑡
35. 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) 𝑢𝑛𝑓𝑜𝑙𝑑 ∷ (𝛽 → 𝛼) → 𝛽 → 𝑩𝒐𝒐𝒍 → (𝛽 → 𝛽) → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 𝑢𝑛𝑓𝑜𝑙𝑑 ℎ 𝑝 𝑡 = 𝑚𝑎𝑝 ℎ ∘ 𝑡𝑎𝑘𝑒𝑤ℎ𝑖𝑙𝑒 𝑝 ∘ 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑡
36. 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 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) 𝑢𝑛𝑓𝑜𝑙𝑑 ∷ (𝛽 → 𝛼) → 𝛽 → 𝑩𝒐𝒐𝒍 → (𝛽 → 𝛽) → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 𝑢𝑛𝑓𝑜𝑙𝑑 ℎ 𝑝 𝑡 = 𝑚𝑎𝑝 ℎ ∘ 𝑡𝑎𝑘𝑒𝑤ℎ𝑖𝑙𝑒 𝑝 ∘ 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑡
37. 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] 𝑢𝑛𝑓𝑜𝑙𝑑 ∷ (𝛽 → 𝛼) → 𝛽 → 𝑩𝒐𝒐𝒍 → (𝛽 → 𝛽) → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 𝑢𝑛𝑓𝑜𝑙𝑑 ℎ 𝑝 𝑡 = 𝑚𝑎𝑝 ℎ ∘ 𝑡𝑎𝑘𝑒𝑤ℎ𝑖𝑙𝑒 𝑝 ∘ 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑡
38. 𝑢𝑛𝑓𝑜𝑙𝑑𝐿 ∷ 𝛽 → 𝑩𝒐𝒐𝒍 → (𝛽 → 𝛼) → (𝛽 → 𝛽) → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 𝑢𝑛𝑓𝑜𝑙𝑑𝐿 𝑝 𝑓 𝑔 𝑏 = 𝐢𝐟 𝑝 𝑏 𝐭𝐡𝐞𝐧 𝑵𝒊𝒍 𝐞𝐥𝐬𝐞 𝑪𝒐𝒏𝒔 (𝑓 𝑏) (𝑢𝑛𝑓𝑜𝑙𝑑𝐿 𝑝 𝑓 𝑔 (𝑔 𝑏)) 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
39. > 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
40. 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
41. 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 𝑢𝑛𝑓𝑜𝑙𝑑𝐿 ∷ 𝛽 → 𝑩𝒐𝒐𝒍 → (𝛽 → 𝛼) → (𝛽 → 𝛽) → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 𝑢𝑛𝑓𝑜𝑙𝑑𝐿 𝑝 𝑓 𝑔 𝑏 = 𝐢𝐟 𝑝 𝑏 𝐭𝐡𝐞𝐧 𝑵𝒊𝒍 𝐞𝐥𝐬𝐞 𝑪𝒐𝒏𝒔 (𝑓 𝑏) (𝑢𝑛𝑓𝑜𝑙𝑑𝐿 𝑝 𝑓 𝑔 (𝑔 𝑏))
42. 𝑢𝑛𝑓𝑜𝑙𝑑𝐿! ∷ 𝛽 → 𝑴𝒂𝒚𝒃𝒆 (𝛼, 𝛽) → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 𝑢𝑛𝑓𝑜𝑙𝑑𝐿! 𝑓 𝑢 = 𝐜𝐚𝐬𝐞 𝑓 𝑢 𝐨𝐟 𝑵𝒐𝒕𝒉𝒊𝒏𝒈 → 𝑵𝒊𝒍 𝑱𝒖𝒔𝒕 (𝑥, 𝑣) → 𝑪𝒐𝒏𝒔 𝑥 (𝑢𝑛𝑓𝑜𝑙𝑑𝐿! 𝑓 𝑣) 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 ∷ 𝛼 → 𝛼 → 𝛼 → 𝛼 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑓 𝑥 = 𝑥 ∶ 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑓 (𝑓 𝑥) unfoldr unfold
43. 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]] 𝑢𝑛𝑓𝑜𝑙𝑑𝐿 ∷ 𝛽 → 𝑩𝒐𝒐𝒍 → (𝛽 → 𝛼) → (𝛽 → 𝛽) → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 𝑢𝑛𝑓𝑜𝑙𝑑𝐿 𝑝 𝑓 𝑔 𝑏 = 𝐢𝐟 𝑝 𝑏 𝐭𝐡𝐞𝐧 𝑵𝒊𝒍 𝐞𝐥𝐬𝐞 𝑪𝒐𝒏𝒔 (𝑓 𝑏) (𝑢𝑛𝑓𝑜𝑙𝑑𝐿 𝑝 𝑓 𝑔 (𝑔 𝑏))
44. The next slide recaps the different ways of writing a function to unfold a list by using 𝑖𝑡𝑒𝑟𝑎𝑡𝑒, 𝑢𝑛𝑓𝑜𝑙𝑑 𝑢𝑛𝑓𝑜𝑙𝑑𝐿, 𝑢𝑛𝑓𝑜𝑙𝑑𝐿′. The slide after that recaps how 𝑢𝑛𝑓𝑜𝑙𝑑𝐿 and 𝑢𝑛𝑓𝑜𝑙𝑑𝐿′ relate to 𝑖𝑡𝑒𝑟𝑎𝑡𝑒.
45. 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 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑢𝑛𝑓𝑜𝑙𝑑 𝑢𝑛𝑓𝑜𝑙𝑑𝐿 𝑢𝑛𝑓𝑜𝑙𝑑𝐿′ 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑢𝑛𝑓𝑜𝑙𝑑 𝑢𝑛𝑓𝑜𝑙𝑑𝐿 𝑢𝑛𝑓𝑜𝑙𝑑𝐿′
46. 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 ∷ 𝛼 → 𝛼 → 𝛼 → 𝛼 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑓 𝑥 = 𝑥 ∶ 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑓 (𝑓 𝑥) 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑓 = 𝑢𝑛𝑓𝑜𝑙𝑑𝐿 𝑐𝑜𝑛𝑠𝑡 𝐹𝑎𝑙𝑠𝑒 𝑖𝑑 𝑓 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑓 = 𝑢𝑛𝑓𝑜𝑙𝑑𝐿′ 𝜆𝑥. 𝐽𝑢𝑠𝑡 (𝑥, 𝑓 𝑥) 𝑢𝑛𝑓𝑜𝑙𝑑𝐿 𝑝 𝑓 𝑔 = 𝑚𝑎𝑝 𝑓 ∘ 𝑡𝑎𝑘𝑒𝑊ℎ𝑖𝑙𝑒 (𝑛𝑜𝑡 ∘ 𝑝) ∘ 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑔 𝑢𝑛𝑓𝑜𝑙𝑑𝐿! ∷ 𝛽 → 𝑴𝒂𝒚𝒃𝒆 (𝛼, 𝛽) → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 𝑢𝑛𝑓𝑜𝑙𝑑𝐿! 𝑓 𝑢 = 𝐜𝐚𝐬𝐞 𝑓 𝑢 𝐨𝐟 𝑵𝒐𝒕𝒉𝒊𝒏𝒈 → 𝑵𝒊𝒍 𝑱𝒖𝒔𝒕 (𝑥, 𝑣) → 𝑪𝒐𝒏𝒔 𝑥 (𝑢𝑛𝑓𝑜𝑙𝑑𝐿! 𝑓 𝑣) 𝑢𝑛𝑓𝑜𝑙𝑑𝐿 ∷ 𝛽 → 𝑩𝒐𝒐𝒍 → (𝛽 → 𝛼) → (𝛽 → 𝛽) → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 𝑢𝑛𝑓𝑜𝑙𝑑𝐿 𝑝 𝑓 𝑔 𝑏 = 𝐢𝐟 𝑝 𝑏 𝐭𝐡𝐞𝐧 𝑵𝒊𝒍 𝐞𝐥𝐬𝐞 𝑪𝒐𝒏𝒔 (𝑓 𝑏) (𝑢𝑛𝑓𝑜𝑙𝑑𝐿 𝑝 𝑓 𝑔 (𝑔 𝑏)) unfoldr unfold 𝑢𝑛𝑓𝑜𝑙𝑑 ∷ (𝛽 → 𝛼) → 𝛽 → 𝑩𝒐𝒐𝒍 → (𝛽 → 𝛽) → 𝛽 → 𝑳𝒊𝒔𝒕 𝛼 𝑢𝑛𝑓𝑜𝑙𝑑 ℎ 𝑝 𝑡 = 𝑚𝑎𝑝 ℎ ∘ 𝑡𝑎𝑘𝑒𝑤ℎ𝑖𝑙𝑒 𝑝 ∘ 𝑖𝑡𝑒𝑟𝑎𝑡𝑒 𝑡
47. The next two slides are the final ones and contain some afterthoughts.
48. 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
49. 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)
50. @philip_schwarz That’s all for this deck. I hope you found it useful.