Combinatorial Interview Problems with Backtracking Solutions - From Imperative Procedural Programming to Declarative Functional Programming - Part 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.

Keywords: backtracking, bind, combinatorial_problems, declarative_programming, flatMap, foldM, functional_programming, haskell, imperative_programming, interview_problems, monad, monadic_folding, non-determinism, procedural_programming, python, recursion, scala

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/ 𝐼𝑚𝑚𝑢𝑡𝑎𝑏𝑖𝑙𝑖𝑡𝑦 𝐿𝑖𝑠𝑡 𝑀𝑜𝑛𝑎𝑑 𝑀𝑢𝑡𝑎𝑏𝑖𝑙𝑖𝑡𝑦 𝑅𝑒𝑐𝑢𝑟𝑠𝑖𝑜𝑛 𝑑𝑎𝑡𝑎 𝐿𝑖𝑠𝑡 𝑎 = | 𝑎 ∶ [𝑎] 𝑝𝑢𝑟𝑒 𝑥 = 𝑥 𝑥𝑠 ≫= 𝑓 = [𝑦 | 𝑥 ⟵ 𝑥𝑠, 𝑦 ⟵ 𝑓 𝑥] 🔎🧑💻💡 Part 2 Part 1 Part 2 Part 3
2. Let’s begin part 2 with a quick recap, in the following six slides, of what we did in part 1. @philip_schwarz
3. 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 @alexxubyte Alex Xu @shaungunaw Shaun Gunawardane index of number we need to consider next subset grown so far numbers to generate subsets with subsets generated so far The combinatorial interview problem that we looked at in part 1 was that of computing the powerset of a set, i.e. the set of all the subsets of a set. Here on the left is the code for an imperative procedural Python solution to the problem.
4. 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 The first thing that we did was take that code and translate it into the Scala equivalent.
5. 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 We then switched to the functional programming paradigm and came across a recursively defined 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 function operating on sets represented as immutable lists.
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 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)) Next, we had a first stab at finding ways of writing alternative 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 functions which, while also being recursively defined and operating on immutable lists, exploit the link between the list monad and non-determinism/backtracking. Here is the first version again, followed by the two alternative versions that we came up with.
7. We then decided to further exploit the link between the list monad and non- determinism/backtracking. We first had a go at writing a back-of-the-napkin, mathematical definition of the powerset function that only used the do notation (syntactic sugar for ≫=). We went to that trouble because the logic of such a function would turn out to be a special case of the logic of the 𝑓𝑜𝑙𝑑𝑀 function. We were then able to write an extremely concise 𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡 function using 𝑓𝑜𝑙𝑑𝑀. The function is shown on the next slide, side by side with the Python function seen earlier.
8. 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
9. After that recap, let’s turn to the second† combinatorial problem covered in chapter fourteen of Coding Interview Patterns – Nail Your Next Coding Interview. † In the book, the first and second combinatorial problems are presented in the opposite order to the one adopted in this slide deck.
10. Find All Permutations Return all possible permutations of a given array of unique integers. They can be returned in any order. Example: Input: nums = [4,5,6] Output: [[4,5,6], [4,6,5], [5,4,6], [5,6,4], [6,4,5], [6,5,4]] Intuition Our task in this problem is quite straightforward: find all permutations of a given array. The key word here is “all”. To achieve this, we need an algorithm that generates each possible permutation one at a time. The technique that naturally fits this requirement is backtracking. … From Chapter 14: Backtracking @alexxubyte Alex Xu @shaungunaw Shaun Gunawardane
11. def find_all_permutations(nums: List[Int]) -> List[List[Int]]: res = [] backtrack(nums, [], set(), res) return res def backtrack( nums: List[Int], candidate: List[Int], used: Set[Int], res: List[List[Int]] ) -> None: # If the current candidate is a complete # permutation, add it to the result. if len(candidate) == len(nums): res.append(candidate[:]) return for num in nums: if num not in used: # Add 'num' to the current permutation and mark it as used. candidate.append(num) used.add(num) # Recursively explore all branches using # the updated permutation candidate. backtrack(nums, candidate, used, res) # Backtrack by reversing the changes made. candidate.pop() used.remove(num) @alexxubyte Alex Xu @shaungunaw Shaun Gunawardane numbers to generate permutations with permutation grown so far numbers used up so far permutations generated so far Here is the Python code for the imperative procedural solution to the combinatorial problem of computing the permutations of a list of numbers. The authors solve the problem using a recursive backtrack function which, for each number not yet added to a permutation that is currently being generated, adds the number to the permutation and then calls itself recursively. When the recursive call returns, the function backtracks by removing the number from the permutation being generated. The recursion base case is reached when the permutation being generated is complete, at which point it is added to a running result accumulator. The reader is walked through a series of diagrams visualising the individual steps of the recursive backtracking process. See the diagram below for a simplified, compressed representation of all the steps. [] [4] [6] [4,5] [4,6] [4,5,6][4,6,5] choose 4 choose 6 choose 5 choose 6 choose 6 choose 5 [5] [5,4] [5,6] [5,4,6][5,6,4] choose 4 choose 6 choose 6 choose 4 [6,4] [6,5] [6,4,5][6,5,4] choose 4 choose 5 choose 5 choose 4 choose 5 nums candidate used [4,5,6] [] {} [4,5,6] [4] {4} [4,5,6] [4,5] {4,5} [4,5,6] [4,5,6] {4,5,6} [4,5,6] [4,6] {4,6} [4,5,6] [4,6,5] {4,6,5} [4,5,6] [5] {5} … … … for num in [4,5,6]: if num not in {} for num in [4,5,6]: if num not in {4} for num in [4,5,6]: if num not in {4,5}
12. To compute the N! permutations of a list with N>1 elements, method backtrack faces 1 + (∑ !"# $%# ∏ &"!'# $ 𝑗) decision points, at each of which it repeatedly chooses a number that has not yet been used in the permutation currently being generated. Choosing a number is followed by a recursive call. The total number of calls is 1 + (∑!"# $ ∏&"! $ 𝑗). def find_all_permutations(nums: List[Int]) -> List[List[Int]]: res = [] backtrack(nums, [], set(), res) return res def backtrack( nums: List[Int], candidate: List[Int], used: Set[Int], res: List[List[Int]] ) -> None: # If the current candidate is a complete # permutation, add it to the result. if len(candidate) == len(nums): res.append(candidate[:]) return for num in nums: if num not in used: # Add 'num' to the current permutation and mark it as used. candidate.append(num) used.add(num) # Recursively explore all branches using # the updated permutation candidate. backtrack(nums, candidate, used, res) # Backtrack by reversing the changes made. candidate.pop() used.remove(num) @alexxubyte Alex Xu @shaungunaw Shaun Gunawardane numbers to generate permutations with permutation grown so far numbers used up so far permutations generated so far This program is side-effecting, in that it adds/removes numbers to/from two mutable lists and a mutable set. The diagram below illustrates the computation of the permutations of a three-element list. E.g for a list with three elements: • permutations = 3! = 3 x 2 x 1 = 6 • decision pts = 1 + ∑!"# (%# ∏&"!'# ( 𝑗 = 10 • calls = 1 + ∑!"# ( ∏&"! ( 𝑗 = 16 [] [4] [6] [4,5] [4,6] [4,5,6][4,6,5] choose 4 choose 6 choose 5 choose 6 choose 6 choose 5 [5] [5,4] [5,6] [5,4,6][5,6,4] choose 4 choose 6 choose 6 choose 4 [6,4] [6,5] [6,4,5][6,5,4] choose 4 choose 5 choose 5 choose 4 choose 5 nums candidate used [4,5,6] [] {} [4,5,6] [4] {4} [4,5,6] [4,5] {4,5} [4,5,6] [4,5,6] {4,5,6} [4,5,6] [4,6] {4,6} [4,5,6] [4,6,5] {4,6,5} [4,5,6] [5] {5} … … … for num in [4,5,6]: if num not in {} for num in [4,5,6]: if num not in {4} for num in [4,5,6]: if num not in {4,5}
13. On the next slide we can see the translation of the program from Python to Scala. As in part 1, 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.
14. def find_all_permutations(nums: List[Int]): List[List[Int]] = val res = List.empty[List[Int]] backtrack(nums, List(), Set(), res) res def backtrack( nums: List[Int], candidate: List[Int], used: Set[Int], res: List[List[Int]] ): Unit = // If the current candidate is a complete // permutation, add it to the result. if candidate.length == nums.length then return res.append(candidate.clone) for num <- nums do if !used.contains(num) then // Add 'num' to the current permutation and mark it as used. candidate.append(num) used.add(num) // Recursively explore all branches using // the updated permutation candidate. backtrack(nums, candidate, used, res) // Backtrack by reversing the changes made. candidate.dropRightInPlace(1) used.remove(num) def find_all_permutations(nums: List[Int]) -> List[List[Int]]: res = [] backtrack(nums, [], set(), res) return res def backtrack( nums: List[Int], candidate: List[Int], used: Set[Int], res: List[List[Int]] ) -> None: # If the current candidate is a complete # permutation, add it to the result. if len(candidate) == len(nums): res.append(candidate[:]) return for num in nums: if num not in used: # Add 'num' to the current permutation and mark it as used. candidate.append(num) used.add(num) # Recursively explore all branches using # the updated permutation candidate. backtrack(nums, candidate, used, res) # Backtrack by reversing the changes made. candidate.pop() used.remove(num) import scala.collection.mutable.ListBuffer as List import scala.collection.mutable.Set
15. @main def main: Unit: assert(find_all_permutations(List()) == List(List())) assert( find_all_permutations(List(1, 2, 3)).toSet == Set( List(1, 2, 3), List(1, 3, 2), List(2, 1, 3), List(2, 3, 1), List(3, 1, 2), List(3, 2, 1) ) ) assert( find_all_permutations(List(1, 2, 3)).sorted.map(_.toList).mkString("\n") == """|List(1, 2, 3) |List(1, 3, 2) |List(2, 1, 3) |List(2, 3, 1) |List(3, 1, 2) |List(3, 2, 1)""".stripMargin ) Let’s test a bit the Scala version of the program
16. Remember the 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. [] [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] computing the powerset of [4,5,6] the shape of the computation
17. Here is the equivalent diagram for the problem of computing the permutations of a list of items. Each circle represents the decision of which item to add to a subset that is being generated, and each square represents the identification of a permutation to be included in the result. computing the permutations of [4,5,6] the shape of the computation [] [4] [6] [4,5] [4,6] [4,5,6][4,6,5] choose 4 choose 6 choose 5 choose 6 choose 6 choose 5 [5] [5,4] [5,6] [5,4,6][5,6,4] choose 4 choose 6 choose 6 choose 4 [6,4] [6,5] [6,4,5][6,5,4] choose 4 choose 5 choose 5 choose 4 choose 5
18. Here is how the two shapes compare. computing the permutations of a list of three items computing the powerset of a set of three items # of permutations: N! = 6 # of decision points: 1 + ∑@AB CDB ∏EA@FB C 𝑗 = 10 # of calls: 1 + ∑@AB C ∏EA@ C 𝑗 = 16 # of subsets: 2N = 8 # of decision points: 2N − 1 = 7 # of calls: 2N+1 − 1 = 15
19. In part 1 we saw that in Introduction to Functional Programming, 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. It also defines 𝑝𝑒𝑟𝑚𝑠, a permutations function which is also recursive, and also operates on an immutable list. Let’s take a look at the definition of 𝑝𝑒𝑟𝑚𝑠, but not before seeing the definition of a function that it uses: 𝑖𝑛𝑡𝑒𝑟𝑙𝑒𝑎𝑣𝑒. Richard Bird http://www.cs.ox.ac.uk/people/richard.bird/ Philip Wadler https://github.com/wadler
20. 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. … Interleave. The term 𝑖𝑛𝑡𝑒𝑟𝑙𝑒𝑎𝑣𝑒 𝑥 𝑦𝑠 returns a list of all possible ways of inserting the element 𝑥 into the list 𝑦𝑠. For example: ? 𝑖𝑛𝑡𝑒𝑟𝑙𝑒𝑎𝑣𝑒 ′𝑒′ ”𝑎𝑟” [“𝑒𝑎𝑟”, “𝑎𝑒𝑟”, “𝑎𝑟𝑒”] If 𝑦𝑠 has length 𝑛, then 𝑖𝑛𝑡𝑒𝑟𝑙𝑒𝑎𝑣𝑒 𝑥 𝑦𝑠 has length 𝑛 + 1. A recursive definition of 𝑖𝑛𝑡𝑒𝑟𝑙𝑒𝑎𝑣𝑒 is: 𝑖𝑛𝑡𝑒𝑟𝑙𝑒𝑎𝑣𝑒 ∷ 𝛼 → 𝛼 → [𝛼] 𝑖𝑛𝑡𝑒𝑟𝑙𝑒𝑎𝑣𝑒 𝑥 = [ 𝑥 ] 𝑖𝑛𝑡𝑒𝑟𝑙𝑒𝑎𝑣𝑒 𝑥 𝑦 ∶ 𝑦𝑠 = 𝑥 ∶ 𝑦 ∶ 𝑦𝑠 ++ 𝑚𝑎𝑝 𝑦 ∶ (𝑖𝑛𝑡𝑒𝑟𝑙𝑒𝑎𝑣𝑒 𝑥 𝑦𝑠) That is, there is only one way of interleaving 𝑥 into an empty list, namely the list containing just 𝑥. The ways of interleaving 𝑥 into a non-empty list 𝑦 ∶ 𝑦𝑠 are either to begin the list with 𝑥 and follow it with 𝑦 ∶ 𝑦𝑠 , or to begin the list with 𝑦 and follow it with an interleaving of 𝑥 into 𝑦𝑠. … –- Appends two lists (++) :: [a] -> [a] -> [a] In Haskell a string is a list of characters.
21. Permutations. The function 𝑝𝑒𝑟𝑚𝑠 returns a list of all permutations of a list. For example: ? 𝑝𝑒𝑟𝑚𝑠 “𝑒𝑟𝑎” [“𝑒𝑟𝑎”, “𝑟𝑒𝑎”, “𝑟𝑎𝑒”, “𝑒𝑎𝑟”, “𝑎𝑒𝑟”, “𝑎𝑟𝑒”] If 𝑥𝑠 has length 𝑛, then 𝑝𝑒𝑟𝑚𝑠 𝑥𝑠 has length 𝑛! = 𝑛 × 𝑛 − 1 × ⋯× 1. This can be seen by noting that any of the 𝑛 elements of 𝑥𝑠 may appear in the first position, and then any of the remaining 𝑛 − 1 elements may appear in the second position, and so on, until finally there is only one element that may appear in the last position. A recursive definiton of 𝑝𝑒𝑟𝑚𝑠 can be made using the function 𝑖𝑛𝑡𝑒𝑟𝑙𝑒𝑎𝑣𝑒 defined in the previous section: 𝑝𝑒𝑟𝑚𝑠 ∷ 𝛼 → [𝛼] 𝑝𝑒𝑟𝑚𝑠 = [ ] 𝑝𝑒𝑟𝑚𝑠 𝑥 ∶ 𝑥𝑠 = 𝑐𝑜𝑛𝑐𝑎𝑡 𝑚𝑎𝑝 (𝑖𝑛𝑡𝑒𝑟𝑙𝑒𝑎𝑣𝑒 𝑥 (𝑝𝑒𝑟𝑚𝑠 𝑥𝑠)) That is, there is only one permutation of the empty list, namely itself. The permutations of the non-empty list 𝑥 ∶ 𝑥𝑠 are all the ways of interleaving 𝑥 into a permutation of 𝑥𝑠. … –- Concatenate a list of lists concat :: [[a]] -> [a]
22. Let’s code the functions in Haskell and Scala and try them out. def interleave[A](x: A)(xs: List[A]): List[List[A]] = xs match case Nil => List(List(x)) case y::ys => List(x::y::ys) ++ interleave(x)(ys).map(y::_) perms :: [a] -> [[a]] perms [] = [[]] perms (x: xs) = concat (map (interleave x) (perms xs)) haskell> perms [4,5,6] [[4,5,6],[5,4,6],[5,6,4],[4,6,5],[6,4,5],[6,5,4]] scala> perms(List(4,5,6)) val res0: List[List[Int]] = List(List(4, 5, 6), List(5, 4, 6), List(5, 6, 4), List(4, 6, 5), List(6, 4, 5), List(6, 5, 4)) interleave :: a -> [a] -> [[a]] interleave x [] = [[x]] interleave x (y:ys) = [x:y:ys] ++ map (y:) (interleave x ys) def perms[A](as: List[A]): List[List[A]] = as match case Nil => List(Nil) case x::xs => concat(perms(xs).map(interleave(x))) // NOTE – the concat function (alias ++) // provided by Scala appends two lists def concat[A](as: List[List[A]]): List[A] = as.flatten
23. Remember the following equivalence that we came across in part 1? 𝑥 ≫= 𝑓 = 𝑐𝑜𝑛𝑐𝑎𝑡 (𝑚𝑎𝑝 𝑓 𝑥) On the next slide we make use of the equivalence to simplify the definition of 𝑝𝑒𝑟𝑚𝑠. Functional Quantum Programming Shin-Cheng Mu Richard Bird DRAFT Abstract 2 Non-determinism and the list monad … 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. -- 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
24. perms :: [a] -> [[a]] perms [] = [[]] perms (x: xs) = concat (map (interleave x) (perms xs)) def perms[A](as: List[A]): List[List[A]] = as match case Nil => List(Nil) case x::xs => concat(perms(xs).map(interleave(x))) perms :: [a] -> [[a]] perms [] = [[]] perms (x: xs) = perms xs >>= (interleave x) def perms[A](as: List[A]): List[List[A]] = as match case Nil => List(Nil) case x::xs => perms(xs).flatMap(interleave(x)) 𝑥 ≫= 𝑓 𝑐𝑜𝑛𝑐𝑎𝑡 (𝑚𝑎𝑝 𝑓 𝑥) Scala’s equivalent of ≫= is flatMap.
25. Remember when the same paper mentioned how ≫= relates to the do-notation? On the next slide we make use of the do-notation to simplify the first definition of 𝑝𝑒𝑟𝑚𝑠. Functional Quantum Programming Shin-Cheng Mu Richard Bird DRAFT Abstract 2 Non-determinism and the list monad … 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 𝑦 ← 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠 𝑥 𝑧 ← 𝑠𝑢𝑓𝑓𝑖𝑥𝑒𝑠 𝑦 𝑟𝑒𝑡𝑢𝑟𝑛 𝑧 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]. 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠 ∷ 𝑎 → 𝑺𝒆𝒕 [𝑎] 𝑠𝑒𝑔𝑚𝑒𝑛𝑡𝑠 = 𝑐𝑜𝑛𝑐𝑎𝑡 ∘ 𝑚𝑎𝑝 𝑠𝑢𝑓𝑓𝑖𝑥𝑒𝑠 ∘ 𝑝𝑟𝑒𝑓𝑖𝑥𝑒𝑠
26. perms :: [a] -> [[a]] perms [] = [[]] perms (x: xs) = concat (map (interleave x) (perms xs)) def perms[A](as: List[A]): List[List[A]] = as match case Nil => List(Nil) case x::xs => concat(perms(xs).map(interleave(x))) perms :: [a] -> [[a]] perms [] = [[]] perms (x : xs) = do perm <- perms xs result <- interleave x perm return result def perms[A](as: List[A]): List[List[A]] = as match case Nil => List(Nil) case x::xs => for perm <- perms(xs) result <- interleave(x)(perm) yield result 𝒅𝒐 𝑥 ← 𝑥𝑠 𝑦 ← 𝑓 𝑥 𝑟𝑒𝑡𝑢𝑟𝑛 𝑦 𝑐𝑜𝑛𝑐𝑎𝑡 (𝑚𝑎𝑝 𝑓 𝑥𝑠)
27. def perms[A](as: List[A]): List[List[A]] = as match case Nil => List(Nil) case x::xs => concat(perms(xs).map(interleave(x))) perms :: [a] -> [[a]] perms [] = [[]] perms (x: xs) = concat (map (interleave x) (perms xs)) perms :: [a] -> [[a]] perms [] = [[]] perms (x: xs) = perms xs >>= (interleave x) As a recap, here is the code for the three different versions of 𝑝𝑒𝑟𝑚𝑠 that we have covered so far. interleave :: a -> [a] -> [[a]] interleave x [] = [[x]] interleave x (y:ys) = [x:y:ys] ++ map (y:) (interleave x ys) def interleave[A](x: A)(xs: List[A]): List[List[A]] = xs match case Nil => List(List(x)) case y::ys => List(x::y::ys) ++ interleave(x)(ys).map(y::_) def perms[A](as: List[A]): List[List[A]] = as match case Nil => List(Nil) case x::xs => perms(xs).flatMap(interleave(x)) perms :: [a] -> [[a]] perms [] = [[]] perms (x : xs) = do perm <- perms xs result <- interleave x perm return result def perms[A](as: List[A]): List[List[A]] = as match case Nil => List(Nil) case x::xs => for perm <- perms(xs) result <- interleave(x)(perm) yield result
28. def find_all_permutations(nums: List[Int]): List[List[Int]] = val res = List.empty[List[Int]] backtrack(nums, List(), Set(), res) res def backtrack( nums: List[Int], candidate: List[Int], used: Set[Int], res: List[List[Int]] ): Unit = // If the current candidate is a complete // permutation, add it to the result. if candidate.length == nums.length then return res.append(candidate.clone) for num <- nums do if !used.contains(num) then // Add 'num' to the current permutation and mark it as used. candidate.append(num) used.add(num) // Recursively explore all branches using // the updated permutation candidate. backtrack(nums, candidate, used, res) // Backtrack by reversing the changes made. candidate.dropRightInPlace(1) used.remove(num) If we look back at the code of imperative procedural function find_all_permutations, we see that the backtrack function is based on the following concepts: • nums – the numbers that we must include in every permutation • candidate – a permutation that we are currently in the process of generating • used – the numbers that we have so far included in the permutation being generated On the next slide we have a go at writing a functional version of 𝑝𝑒𝑟𝑚𝑠 based on the same notions.
29. perms :: Eq a => [a] -> [[a]] perms [] = [] perms items = perms (length items) where perms 0 = [[]] perms n = do candidate <- perms (n-1) let unused = items \\ candidate item <- unused return (item:candidate) def perms[A](items: List[A]): List[List[A]] = def perms(n: Int): List[List[A]] = if n == 0 then List(Nil) else for candidate <- perms(n-1) unused = items diff candidate item <- unused yield item :: candidate perms(items.size) Here is the new version of perms. Unlike find_all_permutations, which operates on a list of integers, perms is generic: it operates on a list of any type. For that reason, it has a notion of items rather than nums. Also, rather than having a notion of items used so far, it makes more sense for it to have a notion of items still unused, i.e. not yet included in the permutation currently being generated. At any time, computing unused items amounts to computing the difference between items and candidate (see below for the definition of the difference function). Apart from it being more verbose than other versions seen so far, one suboptimal aspect of this version of the perms function is that it computes the unused items from scratch every time it comes out of a recursive call. This is in contrast to the find_all_permutations function, which computes used nums piecemeal by growing them over time. -- The \\ function is list difference (non-associative). In the result of xs \\ ys, the --- first occurrence of each element of ys in turn (if any) has been removed from xs. -- Thus (xs ++ ys) \\ xs == ys. (\\) :: Eq a => [a] -> [a] -> [a] Computes the multiset difference between this sequence and another sequence. Params: that – the sequence of elements to remove Returns: a new sequence which contains all elements of this sequence except some of occurrences of elements that also appear in that. If an element value x appears n times in that, then the first n occurrences of x will not form part of the result, but any following occurrences will. def diff[B >: A](that: Seq[B]): C = …
30. Suppose we wish to generate all the permutations of a set S; that is, all the ways of ordering the items in the set. For instance, the permutations of {1, 2, 3} are {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, and {3, 2, 1}. Here is a plan for generating the permutations of S: For each item x in S, recursively generate the sequence of permutations of S − x 20, and adjoin x to the front of each one. This yields, for each x in S, the sequence of permutations of S that begin with x. Combining these sequences for all x gives all the permutations of S21 : (define (permutations s) (if (null? s) ; empty set? (list nil) ; sequence containing empty set (flatmap (lambda (x) (map (lambda (p) (cons x p)) (permutations (remove x s)))) s))) Notice how this strategy reduces the problem of generating permutations of S to the problem of generating the permutations of sets with fewer elements than S. In the terminal case, we work our way down to the empty list, which represents a set of no elements. For this, we generate (list nil), which is a sequence with one item, namely the set with no elements. The remove procedure used in permutations returns all the items in a given sequence except for a given item. 20 The set S − x is the set of all elements of S, excluding x. 21 Semicolons in Scheme code are used to introduce comments. Everything from the semicolon to the end of the line is ignored by the interpreter. In this book we don’t use many comments; we try to make our programs self-documenting by using descriptive names. Another approach to computing permutations is found in Structure and interpretation of Computer Programs (SICP). See next slide for the Haskell and Scala equivalent. SICP Scheme
31. def perms[A](as: List[A]): List[List[A]] = if as.isEmpty then List(Nil) else as flatMap (a => perms(as diff List(a)) map (a::_)) perms :: Eq a => [a] -> [[a]] perms [] = [[]] perms as = as >>= (\a -> map (a:) (perms (as \\ [a]))) (define (permutations s) (if (null? s) ; empty set? (list nil) ; sequence containing empty set (flatmap (lambda (x) (map (lambda (p) (cons x p)) (permutations (remove x s)))) s)))
32. In part 1, the simplest and most succinct powerset function that we came up with in a declarative functional programming style, used the foldM function provided by both Haskell and Scala’s Cats library (see next slide for a reminder of its signature and of what it does). While all the other versions of the powerset function carried out a recursive computation, the computation carried out by the powerset function using foldM was iterative. Let’s now have a go at defining a iterative version of the perms function sing foldM.
33. https://hackage.haskell.org/package/base-4.15.0.0/docs/Control-Monad.html https://typelevel.org/cats/api/cats/Foldable$.html Cats
34. The next slide is a recap of how we arrived at the definition of powerset that uses foldM.
35. -- powerset of [x1,x2,…,xm ] powersetm = do let [x1,x2,…,xm ]=[1,2,…,m] a1 = [] f xs x = [xs, x:xs] 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 In the top left corner, you see the algorithm that we came up with for computing powersets. It is pseudocode, in the sense that, as the ellipsis indicates, the code changes as the size m of the input list changes. In the top right corner, you see the pseudocode that the Haskell documentation uses to explain how the foldM function works. Because the top left and top right pseudocode `matches`, the pseudocode definition in the middle is able to define the powerset function using foldM. The code at the bottom implements the pseudocode definition above it. powersetm = let f xs x = [xs, x:xs] in foldM f [] [1,2,…,m] import Control.Monad (foldM) powerset :: [a] -> [[a]] powerset = foldM grow [] grow :: [a] -> a -> [[a]] grow as a = [as, a:as]
36. // powerset of List(x1,x2,…,xm ) def powersetm = val List(x1, x2, …,xm) = List(1,2,3,…m) val a1 = Nil val f = (xs:List[Int],x:Int) => List(xs, x::xs) for a2 <- f(a1,x1) a3 <- f(a2,x2) … subset <- f(am,xm) yield subset 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 This slide is the Scala equivalent of the previous one. def powersetm = val f = (xs:List[Int],x:Int) => List(xs, x::xs) List(1,2,…,m).foldM(Nil)(f) 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)
37. -- powerset of [x1,x2,…,xm ] powersetm = do let [x1,x2,…,xm]=[1,2,…,m] a1 = [] f xs x = [xs, x:xs] a2 <- f a1 x1 a3 <- f a2 x2 … f am xm -- permutations of [x1,x2,…,xm ] def perms = ??? What could the corresponding definition be for the perms function? In the next two slidse we come up with one based on the aforementioned notions of candidate and unused.
38. -- powerset of [x1,x2,…,xm ] powersetm = do let [x1,x2,…,xm ]=[1,2,…,m] a1 = [] f xs x = [xs, x:xs] a2 <- f a1 x1 a3 <- f a2 x2 … f am xm -- permutations of [x1,x2,…,xm ] perms = do let (candidate1, unused1) = ([],[1,2,…,m]) item1 <- unused1 let (candidate2, unused2) = (item1:candidate1, delete item1 unused1) item2 <- unused2 let (candidate3, unused3) = (item2:candidate2, delete item2 unused2) … return (itemm:candidatem, delete itemm unusedm) -- permutations of [x1,x2,…,xm ] perms = do ??? Let’s start from the earlier point when we have yet to define function f. Here is how we can define perms based on the notion of candidate and unused. The delete function returns a copy of its second parameter that does not contain its first parameter.
39. -- powerset of [x1,x2,…,xm ] powersetm = do let [x1,x2,…,xm ]=[1,2,…,m] a1 = [] f xs x = [xs, x:xs] a2 <- f a1 x1 a3 <- f a2 x2 … f am xm -- permutations of [x1,x2,…,xm ] perms = do let (candidate1, unused1) = ([],[1,2,…,m]) item1 <- unused1 let (candidate2, unused2) = (item1:candidate1, delete item1 unused1) item2 <- unused2 let (candidate3, unused3) = (item2:candidate2, delete item2 unused2) … return (itemm:candidatem, delete itemm unusedm) -- permutations of [x1,x2,…,xm ] perms = do ??? Rather than returning a list of permutations, this pseudocode function returns a list of (candidate,unused) pairs in which candidate is a sought permutation and unused is an empty list. Once we get to the point when we have coded the function, we’ll then change it to map the list of pairs to a list of permutations. We are now ready to extract function f, which we do on the next slide.
40. -- powerset of [x1,x2,…,xm ] powersetm = do let [x1,x2,…,xm ]=[1,2,…,m] a1 = [] f xs x = [xs, x:xs] a2 <- f a1 x1 a3 <- f a2 x2 … f am xm -- permutations of [x1,x2,…,xm ] perms = do let (candidate1, unused1) = ([],[1,2,…,m]) item1 <- unused1 let (candidate2, unused2) = (item1:candidate1, delete item1 unused1) item2 <- unused2 let (candidate3, unused3) = (item2:candidate2, delete item2 unused2) … return (itemm:candidatem, delete itemm unusedm) -- permutations of [x1,x2,…,xm ] perms = do let [x1,x2,…,xm ] = [1,2,…,m] a1 = ([], [x1,x2,…,xm ]) f (candidate, unused) _ = do item <- unused; return (item:candidate, delete item unused) a2 <- f a1 x1 a3 <- f a2 x2 … f am xm Note that while function f takes a second parameter, it does not use it. The function takes both an accumulator, and a current item from input list [x1,x2,…,xm]. That’s because, as seen before in the case of the subsets function, f is to be passed to foldM, which is what we’ll be doing on the next slide. It just happens that in the case of computing permutations, f doesn’t care what the particular item at hand is. That’s because f can obtain everything it needs from the accumulator.
41. -- powerset of [x1,x2,…,xm ] powersetm = do let [x1,x2,…,xm ]=[1,2,…,m] a1 = [] f xs x = [xs, x:xs] a2 <- f a1 x1 a3 <- f a2 x2 … f am xm -- permutations of [x1,x2,…,xm ] perms = do let (candidate1, unused1) = ([],[1,2,…,m]) item1 <- unused1 let (candidate2, unused2) = (item1:candidate1, delete item1 unused1) item2 <- unused2 let (candidate3, unused3) = (item2:candidate2, delete item2 unused2) … return (itemm:candidatem, delete itemm unusedm) -- permutations of [x1,x2,…,xm ] perms = do let [x1,x2,…,xm ] = [1,2,…,m] a1 = ([], [x1,x2,…,xm ]) f (candidate, unused) _ = do item <- unused; return (item:candidate, delete item unused) a2 <- f a1 x1 a3 <- f a2 x2 … f am xm perms = let f (candidate, unused) _ = do item <- unused; return (item:candidate, delete item unused) in foldM f ([], [x1,x2,…,xm ]) [x1,x2,…,xm ] The actual values in the third parameter of foldM, which is the input list of perms, do not matter because, as seen on the previous slide, f discards them. All that matters is the number of elements in the list, because that’s what governs how many iterations are performed by foldM. On the next slide we implement the above pseudocode.
42. -- powerset of [x1,x2,…,xm ] powersetm = do let [x1,x2,…,xm ]=[1,2,…,m] a1 = [] f xs x = [xs, x:xs] a2 <- f a1 x1 a3 <- f a2 x2 … f am xm -- permutations of [x1,x2,…,xm ] perms = do let (candidate1, unused1) = ([],[1,2,…,m]) item1 <- unused1 let (candidate2, unused2) = (item1:candidate1, delete item1 unused1) item2 <- unused2 let (candidate3, unused3) = (item2:candidate2, delete item2 unused2) … return (itemm:candidatem, delete itemm unusedm) -- permutations of [x1,x2,…,xm ] perms = do let [x1,x2,…,xm ] = [1,2,…,m] a1 = ([], [x1,x2,…,xm ]) f (candidate, unused) _ = do item <- unused; return (item:candidate, delete item unused) a2 <- f a1 x1 a3 <- f a2 x2 … f am xm perms = let f (candidate, unused) _ = do item <- unused; return (item:candidate, delete item unused) in foldM f ([], [x1,x2,…,xm ]) [x1,x2,…,xm ] perms items = foldM grow (candidate, unused) items where (candidate, unused) = ([],items) grow (candidate, unused) _ = do item <- unused; return (item:candidate, delete item unused)
43. As pointed out earlier, now that we have coded the perms function, we need to change it so that rather than returning a list of (candidate, unused) pairs, it maps such a list to a list of permutations. Also, let’s add signatures to both the perms function and its subordinate function grow, and reformat the functions. perms as = foldM grow ([],as) as where (candidate, unused) = ([],items) grow (candidate, unused) _ = do item <- unused; return (item:candidate, delete item unused) perms :: Eq a => [a] -> [[a]] perms items = map fst (foldM grow (candidate, unused) items) where (candidate, unused) = ([],items) grow :: Eq a => ([a],[a]) -> n -> [([a],[a])] grow (candidate, unused) _ = do item <- unused return (item:candidate, delete item unused) On the next slide we translate the function into Scala.
44. def perms[A](items: List[A]): List[List[A]] = items.foldM((candidate = Nil, unused = items))(grow) .map(_.candidate) def grow[A](accumulator: (List[A], List[A]), ignored: A): List[(List[A], List[A])] = accumulator match case (candidate, unused) => for item <- unused yield (item :: candidate, unused diff List(a)) perms :: Eq a => [a] -> [[a]] perms items = map fst (foldM grow (candidate, unused) items) where (candidate, unused) = ([],items) grow :: Eq a => ([a],[a]) -> n -> [([a],[a])] grow (candidate, unused) _ = do item <- unused return (item:candidate, delete item unused)
45. @main def main: Unit: assert( perms(Nil) == List(Nil) ) assert( perms(List(2)) == List(List(2)) ) assert( perms(List(2,5)).toSet == Set(List(2,5),List(5,2)) ) assert( perms(List(2, 5, 7)).toSet == Set(List(7, 5, 2), List(5, 7, 2), List(7, 2, 5), List(2, 7, 5), List(5, 2, 7), List(2, 5, 7))) ) Let’s test a bit the Scala version of the program
46. def find_all_permutations(nums: List[Int]) -> List[List[Int]]: res = [] backtrack(nums, [], set(), res) return res def backtrack( nums: List[Int], candidate: List[Int], used: Set[Int], res: List[List[Int]] ) -> None: # If the current candidate is a complete # permutation, add it to the result. if len(candidate) == len(nums): res.append(candidate[:]) return for num in nums: if num not in used: # Add 'num' to the current permutation and mark it as used. candidate.append(num) used.add(num) # Recursively explore all branches using # the updated permutation candidate. backtrack(nums, candidate, used, res) # Backtrack by reversing the changes made. candidate.pop() used.remove(num) import cats.implicits.* def perms[A](items: List[A]): List[List[A]] = items.foldM((candidate = Nil, unused = items))(grow) .map(_.candidate) def grow[A](accumulator: (List[A], List[A]), ignored: A) : List[(List[A], List[A])] = accumulator match case (candidate, unused) => for item <- unused yield (item :: candidate, unused diff List(a)) import Control.Monad (foldM) perms :: Eq a => [a] -> [[a]] perms items = map fst (foldM grow (candidate, unused) items) where (candidate, unused) = ([],items) grow :: Eq a => ([a],[a]) -> n -> [([a],[a])] grow (candidate, unused) _ = do item <- unused return (item:candidate, delete item unused) Cats
47. That’s all for part two. I hope you enjoyed it. See you in part three.