Combinatorial Interview Problems with Backtracking Solutions - From Imperative Procedural Programming to Declarative Functional Programming - Part 1

In this deck series we are going to do the following for each of three combinatorial problems covered in chapter fourteen of a book called Coding Interview Patterns – Nail Your Next Coding Interview :
* see how the book describes the problem
* view the book’s solution to the problem, which exploits backtracking
* view the book’s imperative Python code for the solution
* translate the imperative code from Python to Scala
* explore Haskell and Scala functional programming solutions.

Transcript

1. Combinatorial Interview Problems with Backtracking Solutions From Imperative Procedural Programming to Declarative Functional Programming Programming Paradigms Imperative Declarative Procedural Object Oriented Functional Logic @philip_schwarz slides by https://fpilluminated.org/ 𝐼𝑚𝑚𝑢𝑡𝑎𝑏𝑖𝑙𝑖𝑡𝑦 𝐿𝑖𝑠𝑡 𝑀𝑜𝑛𝑎𝑑 𝑀𝑢𝑡𝑎𝑏𝑖𝑙𝑖𝑡𝑦 𝑅𝑒𝑐𝑢𝑟𝑠𝑖𝑜𝑛 𝑑𝑎𝑡𝑎 𝐿𝑖𝑠𝑡 𝑎 = | 𝑎 ∶ [𝑎] 𝑝𝑢𝑟𝑒 𝑥 = 𝑥 𝑥𝑠 ≫= 𝑓 = [𝑦 | 𝑥 ⟵ 𝑥𝑠, 𝑦 ⟵ 𝑓 𝑥] 🔎🧑💻💡
2. In this deck series we are going to do the following for each of three combinatorial problems covered in chapter fourteen of a book called Coding Interview Patterns – Nail Your Next Coding Interview : • see how the book describes the problem • view the book’s solution to the problem, which exploits backtracking • view the book’s imperative Python code for the solution • translate the imperative code from Python to Scala • explore Haskell and Scala functional programming solutions. See next slide for the first combinatorial problem that we are going to tackle. @philip_schwarz
3. Find All Subsets Return all possible subsets of a given set of unique integers. Each subset can be ordered in any way, and the subsets can be returned in any order. Example: Input: nums = [4,5,6] Output: [[], [4], [4,5], [4,5,6], [4,6], [5], [5,6], [6]] Intuition The key intuition for solving this problem lies in understanding that each subset is formed by making a specific decision for every number in the input array: to include the number or exclude it. For example, from the array [4,5,6], the subset [4,6] is created by including 4, excluding 5, and including 6. From Chapter 14: Backtracking @alexxubyte Alex Xu @shaungunaw Shaun Gunawardane [] [4] [] [4,5] [4] [5] [] [4,5,6] [4,5] [4,6] [4] [5,6] [5] [6] [] include 4 exclude 4 include 5 exclude 5 include 5 exclude 5 include 6 exclude 6 include 6 exclude 6 include 6 exclude 6 include 6 exclude 6 • The authors solve the problem using a recursive function called which considers each number in turn, recursively calling itself, once after deciding to add the number to a copy of a subset grown so far, and once after deciding not to add it, with the base case adding the subset grown so far to an accumulator that is a growing result list of subsets. • The reader is walked through a series of diagrams visualising the individual steps of the recursive backtracking process. • See the diagram below for a compressed representation of all the steps.
4. def find_all_subsets(nums: List[Int]) -> List[List[Int]]: res = [] backtrack(0, [], nums, res) res def backtrack( i: Int, current_subset: List[Int], nums: List[Int], res: List[List[Int]] ) -> None: // Base case: if all elements have been considered, add the // current subset to the output. if i == len(nums): res.append(current_subset[:]) return // Include the current element and recursively explore all paths // that branch from this subset. current_subset.append(nums(i)) backtrack(i + 1, current_subset, nums, res) // Exclude the current element and recursively explore all paths // that branch from this subset. current_subset.pop() backtrack(i + 1, current_subset, nums, res) [] [4] [] [4,5] [4] [5] [] [4,5,6] [4,5] [4,6] [4] [5,6] [5] [6] [] include nums[i] exclude nums[i] include nums[i] exclude nums[i] include nums[i] exclude nums[i] include nums[i] exclude nums[i] include nums[i] exclude nums[i] include nums[i] exclude nums[i] include nums[i] exclude nums[i] nums=[4,5,6] nums=[4,5,6] nums=[4,5,6] nums=[4,5,6] i=0 i=1 i=2 i=3 Here is the Python code for computing subsets. It represents a set as a list. To compute the set of all subsets of a set of size N, method backtrack needs to make 2N-1 decisions, each with two choices available: including a number, or excluding it. Making a decision (choosing) is followed by a recursive call. The total number of calls required is 2N+1-1. @alexxubyte Alex Xu @shaungunaw Shaun Gunawardane This program is side-effecting, in that it adds and removes numbers to and from mutable lists current_subset and res. The diagram below shows the computation of the subsets of a set of size three. E.g for a set with three elements, the number of decisions is 23-1 = 8-1 = 7 and the number of calls is 23+1-1 = 16-1 = 15. index of number we need to consider next subset grown so far numbers to generate subsets with subsets generated so far
5. Here is a high-level diagram capturing the shape of the search process used to compute the powerset of a set. Each circle represents the decision of whether or not to add an item to a subset that is being generated, and each square represents the identification of a subset to be included in the powerset. In part two of this series, in which look at two more combinatorial problems, we’ll compare their corresponding diagrams with this one.
6. Next, let’s turn to the translation of the Python program into Scala. The program uses Python’s mutable list. Is there a corresponding collection in Scala? The answer depends on what we want to accomplish. In a real-world scenario, armed with our functional and non-functional requirements, it could make sense to answer the question only after studying several relevant slides contained in the deck shown below.
7. For our modest purposes however, we are just going to pick a collection based on some of the following facts, some of them from that deck: 1. .Python provides both an array type and a list type, both being mutable 2. The book decided to solve the problem using mutable lists, and in particular, using their following functions: selecting the Nth item, appending an item, and removing the last item. 3. The recommended general-purpose go-to sequential collections for the combinations of mutable/immutable and indexed/linear are shown in the first table below (from the deck shown on the previous slide) 4. If we consider that the Python program uses a mutable list, which is a linear collection, then according to the table, it seems to make sense to pick a Scala ListBuffer. 5. If we consider the following extract from book Programming in Scala, it doesn’t make perfect sense to pick a Scala ListBuffer in that a ListBuffer is not actually a list: “As the name implies, a ListBuffer is backed by a List and supports efficient conversion of its elements to a List” 6. If we consider this other extract from Programming in Scala, it also doesn’t make sense to pick a Scala ArrayBuffer because it also is not a list: “an ArrayBuffer is backed by an array, and can be quickly converted into one.” 7. If we are going to pick a buffer type, it can make sense to pick a Scala ArrayBuffer because according to the operation complexity table below (also from the deck shown on the previous slide) the time complexity of selecting the Nth item is lower in an ArrayBuffer (interestingly though, the time complexity of removing an item, an operation used by the program, is not shown!). Neither ListBuffer nor ArrayBuffer seem to be a perfect match for Python’s mutable list, but we have to pick one, so based on (3) and (4), let’s pick ListBuffer. Immutable Mutable Indexed Vector ArrayBuffer Linear (Linked lists) List ListBuffer head tail apply update prepend append insert ListBuffer Linear Mutable O(1) O(n) O(n) O(n) O(1) O(1) O(n) ArrayBuffer Indexed Mutable O(1) O(n) O(1) O(1) O(n) amort O(1) O(n)
8. On the next slide we can see the translation of the program from Python to Scala. Note that when we import the ListBuffer type, we rename it to List. We do this purely to reduce the number of non-essential visible differences between the two programs. Also, if you are coding along as you go through the deck, you can change the collection used by the Scala program from ListBuffer to ArrayBuffer simply by replacing ListBuffer with ArrayBuffer in the import statement.
9. def find_all_subsets(nums: List[Int]): List[List[Int]] = val res = List.empty[List[Int]] backtrack(0, List(), nums, res) res def backtrack( i: Int, current_subset: List[Int], nums: List[Int], res: List[List[Int]] ): Unit = // Base case: if all elements have been considered, add the // current subset to the output. if i == nums.length then return res.append(current_subset.clone) // Include the current element and recursively explore all paths // that branch from this subset. current_subset.append(nums(i)) backtrack(i + 1, current_subset, nums, res) // Exclude the current element and recursively explore all paths // that branch from this subset. current_subset.dropRightInPlace(1) backtrack(i + 1, current_subset, nums, res) def find_all_subsets(nums: List[Int]) -> List[List[Int]]: res = [] backtrack(0, [], nums, res) res def backtrack( i: Int, current_subset: List[Int], nums: List[Int], res: List[List[Int]] ) -> None: // Base case: if all elements have been considered, add the // current subset to the output. if i == len(nums): res.append(current_subset[:]) return // Include the current element and recursively explore all paths // that branch from this subset. current_subset.append(nums(i)) backtrack(i + 1, current_subset, nums, res) // Exclude the current element and recursively explore all paths // that branch from this subset. current_subset.pop() backtrack(i + 1, current_subset, nums, res) import scala.collection.mutable.ListBuffer as List
10. @main def main: Unit: assert(find_all_subsets(List()) == List(List())) assert( find_all_subsets(List(1, 2, 3)).toSet.map(_.toSet) == Set( Set(1, 2, 3), Set(1, 2), Set(1, 3), Set(2, 3), Set(1), Set(2), Set(3), Set.empty) ) assert( find_all_subsets(List(1, 2, 3)).sorted.mkString("\n") == """|ListBuffer() |ListBuffer(1) |ListBuffer(1, 2) |ListBuffer(1, 2, 3) |ListBuffer(1, 3) |ListBuffer(2) |ListBuffer(2, 3) |ListBuffer(3)""” .stripMargin ) Let’s test a bit the Scala version of the program
11. On the Rosetta Code site we are reminded that the set of all subsets of a set is called its powerset, so in what follows, when we write a function that computes subsets, we are going to call it powerset. Also, as seen in the definition of powerset on the site (see next slide), the type of items in a set need not be a digit or an integer, so the powerset functions that we are going to write are going to be generic.
12. Rosetta Code https://rosettacode.org/wiki/Rosetta_Code
13. In Introduction to Functional Programming (IFP), there is a Combinatorial functions section which defines 𝑠𝑢𝑏𝑠, a powerset function which is recursive, and in which a set is implemented as an immutable list. Richard Bird http://www.cs.ox.ac.uk/people/richard.bird/ Philip Wadler https://github.com/wadler
14. 5.6 Combinatorial functions Many interesting problems are combinatorial in nature, that is, they involve selecting or permuting elements of a list in some desired manner. This section describes several combinatorial functions of widespread utility. Initial segments. The function 𝑖𝑛𝑖𝑡𝑠 returns the list of all initial segments of a list, in order of increasing length. For example: … Subsequences. The function 𝑠𝑢𝑏𝑠 returns a list of all subsequences of a list. For example: ? 𝑠𝑢𝑏𝑠 ”𝑒𝑟𝑎” [“”, ”“𝑎”, ”“𝑟”, “𝑟𝑎”, “𝑒”, ”“𝑒𝑎”, “𝑒𝑟”, ”“𝑒𝑟𝑎”] The ordering of this list is a consequence of the particular definition of 𝑠𝑢𝑏𝑠 given below. If 𝑥𝑠 has length 𝑛, then 𝑠𝑢𝑏𝑠 𝑥𝑠 has length 2𝑛. This can be seen by noting that each of the 𝑛 elements in 𝑥𝑠 might be either present or absent in a subsequence, so there are 2 × ⋯ × 2 (𝑛 times) possibilities. A recursive definition of 𝑠𝑢𝑏𝑠 is: 𝑠𝑢𝑏𝑠 [ ] = [[ ]] 𝑠𝑢𝑏𝑠 𝑥: 𝑥𝑠 = 𝑠𝑢𝑏𝑠 𝑥𝑠 ++ 𝑚𝑎𝑝 𝑥: 𝑠𝑢𝑏𝑠 𝑥𝑠 That is, the empty list has one subsequence, namely itself. A non-empty list 𝑥: 𝑥𝑠 has as subsequences all the subsequences of 𝑥𝑠, together with those subsequences formed by following 𝑥 with each possible subsequence of 𝑥𝑠. Notice that this definition differs from that of inits in only one place, but has a considerably different meaning. Interleave. … … –- Appends two lists (++) :: [a] -> [a] -> [a] In Haskell a string is a list of characters.
15. Let’s code the function in Haskell and Scala and try it out. def powerset[A](as: List[A]): List[List[A]] = as match case Nil => List(Nil) case a::rest => powerset(rest) ++ powerset(rest).map(a::_) powerset :: [a] -> [[a]] powerset [] = [[]] powerset (a:as) = powerset as ++ map (a:) powerset as haskell> powerset [4,5,6] [[],[6],[5],[5,6],[4],[4,6],[4,5],[4,5,6]] scala> powerset(List(4,5,6)) List(List(), List(6), List(5), List(5, 6), List(4), List(4, 6), List(4, 5), List(4, 5, 6)) def powerset[A](as: List[A]): List[List[A]] = as match case Nil => List(Nil) case a::rest => val subsets = powerset(rest) subsets ++ subsets.map(a::_) powerset :: [a] -> [[a]] powerset [] = [[]] powerset (a:as) = subsets ++ map (a:) subsets where subsets = powerset as Same as above but making a single recursive call.
16. Exercise 2.32: We can represent a set as a list of distinct elements, and we can represent the set of all subsets of the set as a list of lists. For example, if the set is (1 2 3), then the set of all subsets is (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3)). Complete the following definition of a procedure that generates the set of subsets of a set and give a clear explanation of why it works: (define (subsets s) (if (null? s) (list `()) (let ((rest (subsets (cdr s)))) (append rest (map <??> rest))))) (define (subsets s) (if (null? s) (list `()) (let ((rest (subsets (cdr s)))) (append rest (map (lambda (ss) (cons (car s) ss)) rest))))) By the way, if we take our powerset function and do some minor renaming and switch from using where to using the equivalent let, we see that the function is the same as the following subsets function that is the solution of an exercise in Structure and interpretation of Computer Programs (SICP). powerset :: [a] -> [[a]] powerset [] = [[]] powerset (a:as) = subsets ++ map (a:) subsets where subsets = powerset as subsets :: [a] -> [[a]] subsets [] = [[]] subsets (a:as) = let rest = subsets as in rest ++ map (a:) rest SICP Scheme Scheme Haskell
17. While this first definition of the powerset function is nice, it is possible to come up with simpler definitions by exploiting the link that exists between non-determinism and the list monad. One of the places where the link is explained is in a 2001 paper called Functional Quantum Programming. The paper takes a function that computes all the segments of a list, and shows how to simplify the function by using the expressive power of the list monad. Let’s go over the relevant section of the paper (in the next three slides). After that, we are going to look at a few Haskell and Scala implementations of the segments function. We are then going to come up with simpler definitions of the powerset function by using an approach based on the one seen in the paper. 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 ∷ 𝑎 → [ 𝑎 ] 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 = [[ ]] 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 𝑎: 𝑎𝑠 = 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 𝑎𝑠 ++ 𝑚𝑎𝑝 𝑎: 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 𝑎𝑠 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 ∷ 𝑎 → [ 𝑎 ] 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 = [[ ]] 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 𝑎: 𝑎𝑠 = 𝑠𝑢𝑏𝑠𝑒𝑡𝑠 𝑎𝑠 ++ 𝑚𝑎𝑝 𝑎: 𝑠𝑢𝑏𝑠𝑒𝑡𝑠 𝑤ℎ𝑒𝑟𝑒 𝑠𝑢𝑏𝑠𝑒𝑡𝑠 = 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 𝑎𝑠
18. Functional Quantum Programming Shin-Cheng Mu Richard Bird DRAFT Abstract It has been shown that non-determinism, both angelic and demonic, can be encoded in a functional language in different representation of sets. … … 1 Introduction … 2 Non-determinism and the list monad Before going into quantum computing, we will first review some known facts about lists, list monads, and their use for modelling non-determinism. As an example, consider the problem of computing an arbitrary (consecutive) segment of a given list. An elegant way to formulate the problem is to use two relations, or two non-deterministic functions 𝑝𝑟𝑒𝑓𝑖𝑥 and 𝑠𝑢𝑓𝑓𝑖𝑥 . The relation 𝑝𝑟𝑒𝑓𝑖𝑥 ∷ 𝑎 → [𝑎] non-deterministically returns an arbitrary prefix of the given list, while 𝑠𝑢𝑓𝑓𝑖𝑥 ∷ 𝑎 → [𝑎] returns an arbitrary suffix. The problem is thus formulated as 𝑠𝑒𝑔𝑚𝑒𝑛𝑡 = 𝑠𝑢𝑓𝑓𝑖𝑥 ∘ 𝑝𝑟𝑒𝑓𝑖𝑥. Working in a functional language, however, we do not have non-deterministic functions, as they violate the basic requirement for being a function – to yield the same value for the same input. Nevertheless, non-deterministic functions can be simulated by functions returning the set of all possible solutions [7]. A function 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 returning the set of all prefixes of the input list can be defined by: 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 ∷ 𝑎 → 𝑺𝒆𝒕 [𝑎] 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 = 𝑠𝑖𝑛𝑔𝑙𝑒𝑡𝑜𝑛 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 𝑎: 𝑥 = 𝑠𝑖𝑛𝑔𝑙𝑒𝑡𝑜𝑛 `𝑢𝑛𝑖𝑜𝑛` 𝑚𝑎𝑝 𝑎: (𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 𝑥) where 𝑠𝑖𝑛𝑔𝑙𝑒𝑡𝑜𝑛 returns a singleton set, 𝑢𝑛𝑖𝑜𝑛 performs set union, and 𝑚𝑎𝑝 is overloaded for sets.
19. One possible representation of sets in Haskell is via lists, i.e, 𝐭𝐲𝐩𝐞 𝑺𝒆𝒕 𝑎 = 𝑎 In this case, the two set constructing functions above can simply be defined by 𝑠𝑖𝑛𝑔𝑙𝑒𝑡𝑜𝑛 𝑥 = [𝑥] and union = ++ . Similarly, 𝑠𝑢𝑓𝑓𝑖𝑥𝑒𝑠 can be defined by: 𝑠𝑢𝑓𝑓𝑖𝑥𝑒𝑠 ∷ 𝑎 → 𝑺𝒆𝒕 [𝑎] 𝑠𝑢𝑓𝑓𝑖𝑥𝑒𝑠 = 𝑠𝑖𝑛𝑔𝑙𝑒𝑡𝑜𝑛 𝑠𝑢𝑓𝑓𝑖𝑥𝑒𝑠 𝑎: 𝑥 = 𝑎: 𝑥 `𝑢𝑛𝑖𝑜𝑛` (𝑠𝑢𝑓𝑓𝑖𝑥𝑒𝑠 𝑥) The function 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠, which returns the set of all consecutive segments of a given list, can thus be composed as below with the help of primitive list operators 𝑚𝑎𝑝 and 𝑐𝑜𝑛𝑐𝑎𝑡. 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠 ∷ 𝑎 → 𝑺𝒆𝒕 [𝑎] 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠 = 𝑐𝑜𝑛𝑐𝑎𝑡 ∘ 𝑚𝑎𝑝 𝑠𝑢𝑓𝑓𝑖𝑥𝑒𝑠 ∘ 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 The use of a 𝑐𝑜𝑛𝑐𝑎𝑡 after a 𝑚𝑎𝑝 to compose two list-returning functions is a general pattern captured by the list monad. This is how the ≫= operator for the list monad is defined. 𝑥 ≫= 𝑓 = 𝑐𝑜𝑛𝑐𝑎𝑡 (𝑚𝑎𝑝 𝑓 𝑥) The instance of ≫= above has type 𝑎 → 𝑎 → 𝑏 → [𝑏]. We can think of it as an apply function for lists, applying a list-returning function to a list of values. –- Appends two lists (++) :: [a] -> [a] -> [a] Scala’s equivalent of ≫= is flatMap. –- Concatenate a list of lists concat :: [[a]] -> [a] -- Sequentially compose two actions, passing any value -- produced by the first as an argument to the second. (>>=) :: Monad m => m a -> (a -> m b) -> m b If for example 𝑥 = 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 𝑦 and 𝑓 = 𝑠𝑢𝑓𝑓𝑖𝑥𝑒𝑠 then (𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 𝑦) ≫= 𝑠𝑢𝑓𝑓𝑖𝑥𝑒𝑠 = 𝑐𝑜𝑛𝑐𝑎𝑡 (𝑚𝑎𝑝 𝑠𝑢𝑓𝑓𝑖𝑥𝑒𝑠 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 𝑦 )
20. Furthermore, Haskell programmers are equipped with a convenient do-notation for monads. The functions 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 and 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠 can be re-written in do-notation as below. 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 ∷ 𝑎 → 𝑺𝒆𝒕 [𝑎] 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 = 𝑟𝑒𝑡𝑢𝑟𝑛 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 𝑎: 𝑥 = 𝑟𝑒𝑡𝑢𝑟𝑛 `𝑢𝑛𝑖𝑜𝑛` (do 𝑦 ← 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 𝑥 𝑟𝑒𝑡𝑢𝑟𝑛 (𝑎: 𝑦)) 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠 ∷ 𝑎 → 𝑺𝒆𝒕 [𝑎] 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠 𝑥 = do 𝑦 ← 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 𝑥 𝑧 ← 𝑠𝑢𝑓𝑓𝑖𝑥𝑒𝑠 𝑦 𝑟𝑒𝑡𝑢𝑟𝑛 𝑧 The do-notation gives programmers a feeling that they are dealing with a single value rather than a set of them. In the definition for 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠, for instance, identifiers 𝑦 and 𝑧 have type 𝑎 . It looks like we take one arbitrary prefix of 𝑥 , calling it 𝑦, take one arbitrary suffix of 𝑦, calling it 𝑧 , and return it. The fact that there is a whole set of values to be processed is taken care of by the underlying ≫= operator. Simulating non-determinism with sets represented by lists is similar to angelic non-determinism in logic programming. All the answers are enumerated in a list and are ready to be taken one by one. In fact, the list monad has close relationship with backtracking and has been used to model the semantics of logic programming [10]. 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 ∷ 𝑎 → 𝑺𝒆𝒕 [𝑎] 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 = 𝑠𝑖𝑛𝑔𝑙𝑒𝑡𝑜𝑛 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 𝑎: 𝑥 = 𝑠𝑖𝑛𝑔𝑙𝑒𝑡𝑜𝑛 `𝑢𝑛𝑖𝑜𝑛` 𝑚𝑎𝑝 𝑎: (𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 𝑥) 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠 ∷ 𝑎 → 𝑺𝒆𝒕 [𝑎] 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠 = 𝑐𝑜𝑛𝑐𝑎𝑡 ∘ 𝑚𝑎𝑝 𝑠𝑢𝑓𝑓𝑖𝑥𝑒𝑠 ∘ 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠
21. The next three slides show Haskell and Scala code for 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠, 𝑠𝑢𝑓𝑓𝑖𝑥𝑒𝑠 and 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠, together with an example of using each function.
22. type Set a = [a] singleton :: a -> Set a singleton a = [a] union :: Set [a] -> Set [a] -> Set [a] union = (++) prefixes :: [a] -> Set [a] prefixes [] = singleton [] prefixes (a:x) = (singleton []) `union` (map (a:) (prefixes x)) ghci> prefixes [1,2,3,4] [[],[1],[1,2],[1,2,3],[1,2,3,4]] type Set[A] = List[A] def singleton[A](a:A): Set[A] = List(a) // Commented this out because there is no need to provide it, as it is a // Scala built-in function. Note however that it is deprecated in favour // of built-in function concat. // def union[A](x: Set[A], y: Set[A]): Set[A] = x ++ y def prefixes[A](as: List[A]): Set[List[A]] = as match case Nil => singleton(Nil) case a::x => singleton(Nil) union prefixes(x).map(a::_) scala> prefixes(List(1,2,3,4)) val res0: List[List[Int]] = List(List(), List(1), List(1, 2), List(1, 2, 3), List(1, 2, 3, 4)) 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 ∷ 𝑎 → 𝑺𝒆𝒕 [𝑎] 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 = 𝑠𝑖𝑛𝑔𝑙𝑒𝑡𝑜𝑛 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 𝑎: 𝑥 = 𝑠𝑖𝑛𝑔𝑙𝑒𝑡𝑜𝑛 `𝑢𝑛𝑖𝑜𝑛` 𝑚𝑎𝑝 𝑎: (𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 𝑥)
23. suffixes :: [a] -> Set [a] suffixes [] = singleton [] suffixes (a:x) = (a:x) `union` (suffixes x) suffixes :: [a] -> Set [a] suffixes [] = singleton [] suffixes (a:x) = (singleton (a:x)) `union` (suffixes x) Couldn't match expected type: Set [a] with actual type: [a] ghci> suffixes [1,2,3,4] [[1,2,3,4],[2,3,4],[3,4],[4],[]] def suffixes[A](as: List[A]): Set[List[A]] = as match case Nil => singleton(Nil) case a::x => singleton(a::x) union suffixes(x) def suffixes[A](as: List[A]): Set[List[A]] = as match case Nil => singleton(Nil) case a::x => (a::x) union suffixes(x) scala> suffixes(List(1,2,3,4)) val res1: List[List[Int]] = List(List(1, 2, 3, 4), List(2, 3, 4), List(3, 4), List(4), List()) Found: List[A | List[A]] Required: List[List[A]] Fix compilation error Fix compilation error 𝑠𝑢𝑓𝑓𝑖𝑥𝑒𝑠 ∷ 𝑎 → 𝑺𝒆𝒕 [𝑎] 𝑠𝑢𝑓𝑓𝑖𝑥𝑒𝑠 = 𝑠𝑖𝑛𝑔𝑙𝑒𝑡𝑜𝑛 𝑠𝑢𝑓𝑓𝑖𝑥𝑒𝑠 𝑎: 𝑥 = 𝑎: 𝑥 `𝑢𝑛𝑖𝑜𝑛` (𝑠𝑢𝑓𝑓𝑖𝑥𝑒𝑠 𝑥) The Functional Quantum Programming paper was a draft after all
24. 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠 ∷ 𝑎 → 𝑺𝒆𝒕 [𝑎] 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠 = 𝑐𝑜𝑛𝑐𝑎𝑡 ∘ 𝑚𝑎𝑝 𝑠𝑢𝑓𝑓𝑖𝑥𝑒𝑠 ∘ 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 segments :: [a] -> Set [a] segments = concat . map suffixes . prefixes def segments[A](as: List[A]): Set[List[A]] = concat(prefixes(as).map(suffixes(_))) ghci> segments [1,2,3,4] [[],[1],[],[1,2],[2],[],[1,2,3],[2,3],[3],[],[1,2,3,4],[2,3,4],[3,4],[4],[]] scala> segments(List(1,2,3,4)) val res0: List[List[Int]] = List(List(), List(1), List(), List(1,2), List(2), List(), List(1,2,3), List(2,3), List(3), List(), List(1,2,3,4), List(2,3,4), List(3,4), List(4), List()) // NOTE – the concat provided by Scala appends a list to // another, and is the replacement for deprecated union def concat[A](as: List[List[A]]): List[A] = as.flatten Duplicate empty lists! Well, the Functional Quantum Programming paper was a draft after all. See next slide for a fix.
25. segments :: Eq a => [a] -> Set [a] segments = nub . concat . map suffixes . prefixes def segments[A](as: List[A]): Set[List[A]] = concat(prefixes(as).map(suffixes(_))).distinct If we want to remove the duplicate empty lists seen in the results on the previous slide we can do that by adding a call to Haskell’s nub function (nub means ‘essence’ ) and to Scala’s distinct function. The Eq a => in the signature of the segments function is needed because the nub function needs to compare list elements for equality. import Data.List (nub) -- removes duplicate elements nub :: Eq a => [a] -> [a] Eq a => also needs to be added to the signatures of the suffixes and prefixes functions.
26. The next two slides show how the Haskell and Scala code for 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 and 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠 changes when we use the syntactic sugar of Haskell’s do notation and Scala’s for notation. Where the Haskell code uses the 𝑟𝑒𝑡𝑢𝑟𝑛 function, the Scala code uses the 𝑝𝑢𝑟𝑒 function. haskell> :type pure pure :: Applicative f => a -> f a haskell> :type return return :: Monad m => a -> m a scala> :type cats.Applicative[List].pure Any => List[Any] scala> :type cats.Monad[List].pure Any => List[Any] Cats
27. 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 ∷ 𝑎 → 𝑺𝒆𝒕 [𝑎] 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 = 𝑟𝑒𝑡𝑢𝑟𝑛 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 𝑎: 𝑥 = 𝑟𝑒𝑡𝑢𝑟𝑛 `𝑢𝑛𝑖𝑜𝑛` (do 𝑦 ← 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 𝑥 𝑟𝑒𝑡𝑢𝑟𝑛 (𝑎: 𝑦)) 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠 ∷ 𝑎 → 𝑺𝒆𝒕 [𝑎] 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠 𝑥 = do 𝑦 ← 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 𝑥 𝑧 ← 𝑠𝑢𝑓𝑓𝑖𝑥𝑒𝑠 𝑦 𝑟𝑒𝑡𝑢𝑟𝑛 𝑧 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 ∷ 𝑎 → 𝑺𝒆𝒕 [𝑎] 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 = 𝑠𝑖𝑛𝑔𝑙𝑒𝑡𝑜𝑛 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 𝑎: 𝑥 = 𝑠𝑖𝑛𝑔𝑙𝑒𝑡𝑜𝑛 `𝑢𝑛𝑖𝑜𝑛` 𝑚𝑎𝑝 𝑎: (𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 𝑥) 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠 ∷ 𝑎 → 𝑺𝒆𝒕 [𝑎] 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠 = 𝑐𝑜𝑛𝑐𝑎𝑡 ∘ 𝑚𝑎𝑝 𝑠𝑢𝑓𝑓𝑖𝑥𝑒𝑠 ∘ 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 prefixes :: [a] -> Set [a] prefixes [] = singleton [] prefixes (a:x) = (singleton []) `union` (map (a:) (prefixes x)) prefixes :: [a] -> Set [a] prefixes [] = return [] prefixes (a:x) = return [] `union` (do y <- prefixes x return (a:y)) segments :: [a] -> Set [a] segments = concat . map suffixes . prefixes segments :: [a] -> Set [a] segments x = do y <- prefixes x z <- suffixes y return z Switching to do notation
28. 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 ∷ 𝑎 → 𝑺𝒆𝒕 [𝑎] 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 = 𝑟𝑒𝑡𝑢𝑟𝑛 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 𝑎: 𝑥 = 𝑟𝑒𝑡𝑢𝑟𝑛 `𝑢𝑛𝑖𝑜𝑛` (do 𝑦 ← 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 𝑥 𝑟𝑒𝑡𝑢𝑟𝑛 (𝑎: 𝑦)) 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠 ∷ 𝑎 → 𝑺𝒆𝒕 [𝑎] 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠 𝑥 = do 𝑦 ← 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 𝑥 𝑧 ← 𝑠𝑢𝑓𝑓𝑖𝑥𝑒𝑠 𝑦 𝑟𝑒𝑡𝑢𝑟𝑛 𝑧 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 ∷ 𝑎 → 𝑺𝒆𝒕 [𝑎] 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 = 𝑠𝑖𝑛𝑔𝑙𝑒𝑡𝑜𝑛 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 𝑎: 𝑥 = 𝑠𝑖𝑛𝑔𝑙𝑒𝑡𝑜𝑛 `𝑢𝑛𝑖𝑜𝑛` 𝑚𝑎𝑝 𝑎: (𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 𝑥) 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠 ∷ 𝑎 → 𝑺𝒆𝒕 [𝑎] 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠 = 𝑐𝑜𝑛𝑐𝑎𝑡 ∘ 𝑚𝑎𝑝 𝑠𝑢𝑓𝑓𝑖𝑥𝑒𝑠 ∘ 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 def prefixes[A](as: List[A]): Set[List[A]] = as match case Nil => singleton(Nil) case a::x => singleton(Nil) union prefixes(x).map(a::_) def prefixes[A](as: List[A]): Set[List[A]] = as match case Nil => Nil.pure case a::x => Nil.pure union (for y <- prefixes(x) yield a::y) def segments[A](as: List[A]): Set[List[A]] = concat(prefixes(as).map(suffixes(_))) def segments[A](as: List[A]): Set[List[A]] = for y <- prefixes(x) z <- suffixes(y) yield z Switching to for notation Cats
29. As seen in the previous two slides, using the do notation in 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠 ∷ 𝑎 → 𝑺𝒆𝒕 [𝑎] 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠 = 𝑐𝑜𝑛𝑐𝑎𝑡 ∘ 𝑚𝑎𝑝 𝑠𝑢𝑓𝑓𝑖𝑥𝑒𝑠 ∘ 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 is worth considering 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠 ∷ 𝑎 → 𝑺𝒆𝒕 [𝑎] 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠 𝑥 = do 𝑦 ← 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 𝑥 𝑧 ← 𝑠𝑢𝑓𝑓𝑖𝑥𝑒𝑠 𝑦 𝑟𝑒𝑡𝑢𝑟𝑛 𝑧 but I think that exploiting this equivalence 𝑥 ≫= 𝑓 = 𝑐𝑜𝑛𝑐𝑎𝑡 𝑚𝑎𝑝 𝑓 𝑥 is also worthwhile: 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠 ∷ 𝑎 → 𝑺𝒆𝒕 [𝑎] 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠 𝑥 = 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 𝑥 ≫= 𝑠𝑢𝑓𝑓𝑖𝑥𝑒𝑠
30. Having just seen how the definition of 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠 can be simplified using this equivalence 𝑥 ≫= 𝑓 = 𝑐𝑜𝑛𝑐𝑎𝑡 𝑚𝑎𝑝 𝑓 𝑥 Let’s now go back to our 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 function and see if we are able to do something similar 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 ∷ 𝑎 → [ 𝑎 ] 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 = [[ ]] 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 𝑎: 𝑎𝑠 = 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 𝑎𝑠 ++ 𝑚𝑎𝑝 𝑎: 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 𝑎𝑠 How about using this equivalence? 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 𝑥𝑠 ≫= 𝜆𝑥𝑠. [𝑥𝑠, 𝑥: 𝑥𝑠] = 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 𝑎𝑠 ++ 𝑚𝑎𝑝 𝑎: (𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 𝑎𝑠) Here is how using the equivalence improves the definition of 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 ∷ 𝑎 → [ 𝑎 ] 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 = [[ ]] 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 𝑎: 𝑎𝑠 = 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 𝑎𝑠 ≫= 𝜆𝑎𝑠. [𝑎𝑠, 𝑎: 𝑎𝑠] We can improve this further by extracting an 𝑎𝑑𝑑 function: 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 ∷ 𝑎 → [ 𝑎 ] 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 = [[ ]] 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 𝑎: 𝑎𝑠 = 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 𝑎𝑠 ≫= 𝑎𝑑𝑑 𝑎 𝑤ℎ𝑒𝑟𝑒 𝑎𝑑𝑑 𝑎 𝑎𝑠 = [𝑎𝑠, 𝑎: 𝑎𝑠] I find both versions an improvement on the original.
31. Now let’s take our first improved version of 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 ∷ 𝑎 → [ 𝑎 ] 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 = [[ ]] 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 𝑎: 𝑎𝑠 = 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 𝑎𝑠 ≫= 𝜆𝑎𝑠. [𝑎𝑠, 𝑎: 𝑎𝑠] and see how it looks if we replace ≫= with the syntactic sugar of do notation: 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 ∷ 𝑎 → [ 𝑎 ] 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 = [[ ]] 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 𝑎: 𝑎𝑠 = do 𝑠𝑢𝑏𝑠𝑒𝑡 ← 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 𝑎𝑠 𝑟𝑒𝑠𝑢𝑙𝑡 ← [𝑠𝑢𝑏𝑠𝑒𝑡, 𝑎: 𝑠𝑢𝑏𝑠𝑒𝑡] 𝑟𝑒𝑡𝑢𝑟𝑛 𝑟𝑒𝑠𝑢𝑙𝑡 We can arguably improve this by extracting an 𝑔𝑟𝑜𝑤 function, which is just like the 𝑎𝑑𝑑 function that we introduced earlier, but with its parameters swapped round: 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 ∷ 𝑎 → [ 𝑎 ] 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 = [[ ]] 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 𝑎: 𝑎𝑠 = do 𝑠𝑢𝑏𝑠𝑒𝑡 ← 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 𝑎𝑠 𝑟𝑒𝑠𝑢𝑙𝑡 ← 𝑔𝑟𝑜𝑤 𝑠𝑢𝑏𝑠𝑒𝑡 𝑎 𝑟𝑒𝑡𝑢𝑟𝑛 𝑟𝑒𝑠𝑢𝑙𝑡 where 𝑔𝑟𝑜𝑤 𝑎s 𝑎 = [𝑎𝑠, 𝑎: 𝑎𝑠]
32. def powerset[A](as: List[A]): List[List[A]] = as match case Nil => List(Nil) case a::rest => val subsets = powerset(rest) subsets ++ subsets.map(a::_) powerset :: [a] -> [[a]] powerset [] = [[]] powerset (a:as) = subsets ++ map (a:) subsets where subsets = powerset as powerset :: [a] -> [[a]] powerset [] = [[]] powerset (a:as) = powerset as >>= add a powerset :: [a] -> [[a]] powerset [] = [[]] powerset (a:as) = do subset <- powerset as result <- grow subset a return result def powerset[A](as: List[A]): List[List[A]] = as match case Nil => List(Nil) case a::rest => for subset <- powerset(rest) result <- grow(subset,a) yield result grow :: [a] -> a -> [[a]] grow subset element = [subset, element:subset] add :: a -> [a] -> [[a]] add = flip grow def grow[A](subset: List[A], element: A) = List(subset, element::subset) def add[A](element: A)(subset: List[A]): List[List[A]] = grow(subset,element) def powerset[A](as: List[A]): List[List[A]] = as match case Nil => List(Nil) case a::rest => powerset(rest).flatMap(add(a)) As a recap, here is the code for the three different versions of 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 that we have covered so far, with some very minor renaming and changes. Of course we would also have the option, if preferable, to inline subordinate functions add and grow.
33. (define (concat xss) (fold-right append `() xss)) (define (flatmap proc seq) (concat (map proc seq))) > (concat (list (list 1 2) (list 3 4)) ) (1 2 3 4) > (flatmap (lambda (x) (list x x)) (list 1 2 3)) (1 1 2 2 3 3) By the way, equivalence 𝑥 ≫= 𝑓 = 𝑐𝑜𝑛𝑐𝑎𝑡 𝑚𝑎𝑝 𝑓 𝑥 also makes an appearance in SICP SICP The combination of mapping and accumulating with append is so common in this sort of program that we will isolate it as a separate procedure: (define (flatmap proc seq) (accumulate append `() (map proc seq))) It is the same equivalence because the accumulate function in SICP is a fold, and folding the append function over a list of lists is what the concat function does. Let’s define concat and flatmap using MIT/GNU Scheme and try it out –- Concatenate a list of lists concat :: [[a]] -> [a] concat = foldr (++) [] 𝑠𝑒𝑞 ≫= 𝑝𝑟𝑜𝑐 = 𝑐𝑜𝑛𝑐𝑎𝑡 𝑚𝑎𝑝 𝑝𝑟𝑜𝑐 𝑠𝑒𝑞 𝑥 ≫= 𝑓 = 𝑐𝑜𝑛𝑐𝑎𝑡 𝑚𝑎𝑝 𝑓 𝑥 Scheme Haskell Scheme
34. The three recursive definitions of the 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 function that we have considered so far are good, but can we can come up with an even simpler definition, one that doesn’t even use recursion? The way we are going to do that is by further exploiting the link between the list monad and non-determinism / backtracking. We are going to have a go at writing a definition of the 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 function using just the do notation (syntactic sugar for ≫=). As a first step, armed purely with the do notation, let’s do the following: 1. write function powerset0, which returns the powerset of [ ] 2. rename the function powerset1 and get it to return the powerset of [1] 3. rename the function powerset2 and get it to return the powerset of [1,2] 4. rename the function powerset3 and get it to return the powerset of [1,2,3] 5. rename the function powerset3b and get it to return the powerset of [x0,x1,x2] where x0 is 1, x1 is 2, and x2 is 3
35. -- powerset of [] powerset0 = do let ss0 = [] [ss0] > powerset0 [[]] Computes the powerset of an empty set by returning a set containing the only subset of the empty set, i.e the empty set itself. Step 1 - write function powerset0, which returns the powerset of [ ] ss0 stands for a subset with 0 elements
36. -- powerset of [] powerset0 = do let ss0 = [] [ss0] > powerset0 [[]] Computes the powerset of an empty set by returning a set containing the only subset of the empty set, i.e the empty set itself. -- powerset of [1] powerset1 = do let ss0 = [] [ss0, 1:ss0] > powerset1 [[],[1]] Computes the powerset of a singleton set by returning a set containing both the single subset of the empty set and the result of adding the set’s item to the subset. Step 2 - rename the function powerset1 and get it to return the powerset of [1]
37. Computes the powerset of a singleton set by returning a set containing both the single subset of the empty set and the result of adding the set’s item to the subset. Computes the powerset of a two-item set by computing the subsets of a set containing one item and returning a set containing both the subsets, and the result of adding one more item to each of the subsets. -- powerset of [1,2] powerset2 = do let ss0 = [] ss1 <- [ss0, 1:ss0] [ss1, 2:ss1] > powerset2 [[],[2],[1],[2,1]] -- powerset of [1] powerset1 = do let ss0 = [] [ss0, 1:ss0] > powerset1 [[],[1]] Step 3 - rename the function powerset2 and get it to return the powerset of [1,2]
38. Computes the powerset of a two-item set by computing the subsets of a set containing one item and returning a set containing both the subsets, and the result of adding one more item to each of the subsets. Computes the powerset of a three-item set by computing the subsets of a set containing two items and returning a set containing both the subsets, and the result of adding one more item to each of the subsets. -- powerset of [1,2,3] powerset3 = do let ss0 = [] ss1 <- [ss0, 1:ss0] ss2 <- [ss1, 2:ss1] [ss2, 3:ss2] > powerset3 [[],[3],[2],[3,2],[1],[3,1],[2,1],[3,2,1]] -- powerset of [1,2] powerset2 = do let ss0 = [] ss1 <- [ss0, 1:ss0] [ss1, 2:ss1] > powerset2 [[],[2],[1],[2,1]] Step 4 - rename the function powerset3 and get it to return the powerset of [1,2,3]
39. Name the items of the set x0, x1 and x2 -- powerset of [x0,x1,x2] powerset3b = do let ss0 = [] [x0,x1,x2] = [1,2,3] ss1 <- [ss0, x0:ss0] ss2 <- [ss1, x1:ss1] [ss2, x2:ss2] -- powerset of [1,2,3] powerset3 = do let ss0 = [] ss1 <- [ss0, 1:ss0] ss2 <- [ss1, 2:ss1] [ss2, 3:ss2] Step 5 - rename the function powerset3b and get it to return the powerset of [x0,x1,x2] where x0 is 1, x1 is 2, and x2 is 3 grow :: [a] -> a -> [[a]] grow subset element = [subset, element:subset] Remember the grow function? On the next slide we replace the following with invocations of grow: [ss0, x0:ss0] ,[ss1, x1:ss1] ,[ss2, x2:ss2]
40. Extract into a function called grow the logic which given one of the subsets computed so far, and the next item, returns a list containing both the subset and the result of adding the item to the subset -- powerset of [x0,x1,x2] powerset3b = do let ss0 = [] [x0,x1,x2] = [1,2,3] ss1 <- [ss0, x0:ss0] ss2 <- [ss1, x1:ss1] [ss2, x2:ss2] -- powerset of [x0,x1,x2] powerset3c = do let grow xs x = [xs, x:xs] ss0 = [] [x0,x1,x2] = [1,2,3] ss1 <- grow ss0 x0 ss2 <- grow ss1 x1 grow ss2 x2 On the next slide we simply bump up the index numbers in ss0, ss1, ss2, x0, x1, x2.
41. -- powerset of [x0,x1,x2] powerset3c = do let grow xs x = [xs, x:xs] ss0 = [] [x0,x1,x2] = [1,2,3] ss1 <- grow ss0 x0 ss2 <- grow ss1 x1 grow ss2 x2 -- powerset of [x1,x2,x3] powerset3d = do let grow xs x = [xs, x:xs] ss1 = [] [x1,x2,x3] = [1,2,3] ss2 <- grow ss1 x1 ss3 <- grow ss2 x2 grow ss3 x3 Bump up index numers On the next slide we just rename ss1, ss2, ss3 and the grow function.
42. -- powerset of [x1,x2,x3] powerset3d = do let grow xs x = [xs, x:xs] ss1 = [] [x1,x2,x3] = [1,2,3] ss2 <- grow ss1 x1 ss3 <- grow ss2 x2 grow ss3 x3 -- powerset of [x1,x2,x3] powerset3e = do let f xs x = [xs, x:xs] a1 = [] [x1,x2,x3] = [1,2,3] a2 <- f a1 x1 a3 <- f a2 x2 f a2 x2 Renaming: grow à f ss<n> à a<n>
43. While this function’s logic does show how the powerset of a set of items can be computed purely using do notation, the logic is not generic with respect to the size of the set: every time the size changes, we have to change the logic to reflect that. How can we make the logic generic? Let’s start by renaming the function powersetn and making it generic on paper: here is how we can express the fact that the logic depends on the size of the set -- powerset of [x1,x2,x3] powerset3e = do let f xs x = [xs, x:xs] a1 = [] [x1,x2,x3] = [1,2,3] a2 <- f a1 x1 a3 <- f a2 x2 f a2 x2 -- powerset of [x1,x2,…,xn-1 ,xn ] powersetn = do let f xs x = [xs, x:xs] a1 = [] [x1,x2,…,xn]=[1,2,…,n-1,n] a2 <- f a1 x1 a3 <- f a2 x2 … an <- f an-1 xn-1 f an xn -- powerset of [x1,x2,x3] powerset3e = do let f xs x = [xs, x:xs] a1 = [] [x1,x2,x3] = [1,2,3] a2 <- f a1 x1 a3 <- f a2 x2 f a2 x2 picture comparison
44. -- powerset of [x1,x2,…,xm] powersetm = do let f xs x = [xs, x:xs] a1 = [] [x1,x2,…,xm]=[1,2,…,m] a2 <- f a1 x1 a3 <- f a2 x2 … f am xm -- powerset of [x1,x2,…,xn-1,xn] powersetn = do let f xs x = [xs, x:xs] a1 = [] [x1,x2,…,xn]=[1,2,…,n-1,n] a2 <- f a1 x1 a3 <- f a2 x2 … an <- f an-1 xn-1 f an xn picture comparison In preparation for the next step, let’s rename n to m and drop the function’s penultimate line, which is superfluous in that its presence can be inferred from the rest of the logic.
45. The reason why we have gone to the trouble of working out the definition of powersetm is that the logic of this function is a special case of the logic of a function that is called foldM and is provided by both Haskell and Scala’s Cats library. -- powerset of [x1,x2,…,xm] powersetm = do let f xs x = [xs, x:xs] a1 = [] [x1,x2,…,xm ]=[1,2,…,m] a2 <- f a1 x1 a3 <- f a2 x2 … f am xm foldM f a1 [x1, x2, …, xm] == do a2 <- f a1 x1 a3 <- f a2 x2 … f am xm extract from the Haskell documentation for foldM the function we have written See the next two slides for the Haskell and Scala Cats documentation for foldM.
46. https://hackage.haskell.org/package/base-4.15.0.0/docs/Control-Monad.html
47. https://typelevel.org/cats/api/cats/Foldable$.html Cats
48. powersetm = do let f xs x = [xs, x:xs] a1 = [] [x1,x2,…,xm]=[1,2,…,m] a2 <- f a1 x1 a3 <- f a2 x2 … f am xm powersetm = let f xs x = [xs, x:xs] in foldM f [] [1,2,…,m] Function foldM does a monadic fold, a monadic version of an ordinary fold. While our powersetm function operates on the list monad, foldM operates on any monad. When we get foldM to operate on the list monad, its behaviour is the same as that captured by the logic in our powersetm function. For that reason, we are able to reimplement powersetm as follows: def powersetm = val f = (xs:List[Int],x:Int) => List(xs, x::xs) val a1 = Nil val List(x1, x2, x3) = List(1,2,3) for a2 <- f(a1,x1) a3 <- f(a2,x2) subset <- f(a3,x3) yield subset def powersetm = val f = (xs:List[Int],x:Int) => List(xs, x::xs) List(1,2,…,m).foldM(Nil)(f)
49. import cats.implicits.* def powerset[A](as: List[A]): List[List[A]] = as.foldM(Nil)(grow) def grow[A](as: List[A], a: A) = List(as, a::as) import Control.Monad (foldM) powerset :: [a] -> [[a]] powerset = foldM grow [] grow :: [a] -> a -> [[a]] grow as a = [as, a:as] powersetm = let f xs x = [xs, x:xs] in foldM f [] [1,2,…,m] def powersetm = val f = (xs:List[Int],x:Int) => List(xs, x::xs) List(1,2,…,m).foldM(Nil)(f) From the two back-of-an-envelope functions (since they refer to m) on the left, we can finally derive executable Haskell and Scala powerset functions.
50. > powerset [] [[]] > powerset [4] [[],[4]] > powerset [4,5] [[],[5],[4],[5,4]] > powerset [4,5,6] [[],[6],[5],[6,5],[4],[6,4],[5,4],[6,5,4]] > powerset [4,5,6,7] [[],[7],[6],[7,6],[5],[7,5],[6,5],[7,6,5],[4],[7,4],[6,4],[7,6,4],[5,4],[7,5,4],[6,5,4],[7,6,5,4]] Let’s take the Haskell version of the foldM-based powerset function for a spin.
51. > powerset(Nil) val res0: List[List[Nothing]] = List(List()) > powerset(List(4)) val res1: List[List[Int]] = List(List(), List(4)) > powerset(List(4,5)) val res2: List[List[Int]] = List(List(), List(5), List(4), List(5, 4)) > powerset(List(4,5,6)) val res3: List[List[Int]] = List(List(), List(6), List(5), List(6, 5), List(4), List(6, 4), List(5, 4), List(6, 5, 4)) > powerset(List(4,5,6,7)) val res4: List[List[Int]] = List(List(), List(7), List(6), List(7, 6), List(5), List(7, 5), List(6, 5), List(7, 6, 5), List(4), List(7, 4), List(6, 4), List(7, 6, 4), List(5, 4), List(7, 5, 4), List(6, 5, 4), List(7, 6, 5, 4)) And now the Scala version.
52. The next slide shows the Haskell and Scala code for the final version of the powerset function, and compares it with the imperative Python code of the find_all_subsets function that we saw at the beginning of this deck. The slide after that is the same, except that it inlines the grow function.
53. def find_all_subsets(nums: List[Int]) -> List[List[Int]]: res = [] backtrack(0, [], nums, res) res def backtrack( i: Int, current_subset: List[Int], nums: List[Int], res: List[List[Int]] ) -> None: // Base case: if all elements have been considered, add the // current subset to the output. if i == len(nums): res.append(current_subset[:]) return // Include the current element and recursively explore all paths // that branch from this subset. current_subset.append(nums(i)) backtrack(i + 1, current_subset, nums, res) // Exclude the current element and recursively explore all paths // that branch from this subset. current_subset.pop() backtrack(i + 1, current_subset, nums, res) import cats.implicits.* def powerset[A](as: List[A]): List[List[A]] = as.foldM(Nil)(grow) def grow[A](as: List[A], a: A) = List(as, a::as) import Control.Monad (foldM) powerset :: [a] -> [[a]] powerset = foldM grow [] grow :: [a] -> a -> [[a]] grow as a = [as, a:as] Cats
54. def find_all_subsets(nums: List[Int]) -> List[List[Int]]: res = [] backtrack(0, [], nums, res) res def backtrack( i: Int, current_subset: List[Int], nums: List[Int], res: List[List[Int]] ) -> None: // Base case: if all elements have been considered, add the // current subset to the output. if i == len(nums): res.append(current_subset[:]) return // Include the current element and recursively explore all paths // that branch from this subset. current_subset.append(nums(i)) backtrack(i + 1, current_subset, nums, res) // Exclude the current element and recursively explore all paths // that branch from this subset. current_subset.pop() backtrack(i + 1, current_subset, nums, res) import cats.implicits.* def powerset[A](as: List[A]): List[List[A]] = as.foldM(Nil)((as, a) => List(as, a::as)) import Control.Monad (foldM) powerset :: [a] -> [[a]] powerset = foldM (\as a -> [as, a:as]) [] Cats
55. If you want to know more about the foldM function, which is very interesting because its behaviour depends on the particular Monad that it operates on, see the following deck, or the deck series on the next slide. https://fpilluminated.org/
57. That’s all for part one. I hope you enjoyed it. See you in part two.