N-Queens Combinatorial Puzzle meets Cats

This talk was presented on Aug 3rd 2023 during the Scala in the City event at ITV in London https://www.meetup.com/scala-in-the-city/events/292844968/

Visit the following for a description, slideshow, video recording, all slides with transcript, pdf, github repository, etc: http://fpilluminated.com/assets/n-queens-combinatorial-puzzle-meets-cats.html

At the centre of this talk is the N-Queens combinatorial puzzle. The reason why this puzzle features in the Scala book and functional programming course by Martin Odersky (the language’s creator), is that such puzzles are a particularly suitable application area of 'for comprehensions'.

We’ll start by (re)acquainting ourselves with the puzzle, and seeing the role played in it by permutations. Next, we’ll see how, when wanting to visualise candidate puzzle solutions, Cats’ monoidal functions fold and foldMap are a great fit for combining images.

While we are all very familiar with the triad providing the bread, butter and jam of functional programming, i.e. map, filter and fold, not everyone knows about the corresponding functions in Cats’ monadic variant of the triad, i.e. mapM, filterM and foldM, which we are going to learn about next.

As is often the case in functional programming, the traverse function makes an appearance, and we shall grab the opportunity to point out the symmetry that exists in the interrelation of flatMap / foldMap / traverse and flatten / fold / sequence.

Armed with an understanding of foldM, we then look at how such a function can be used to implement an iterative algorithm for the N-Queens puzzle.

The talk ends by pointing out that the iterative algorithm is smarter than the recursive one, because it ‘remembers’ where it has already placed previous queens.

Transcript

1. 𝑚𝑎𝑝𝑀 monadic mapping, filtering, folding 𝑓𝑖𝑙𝑡𝑒𝑟𝑀 𝑓𝑜𝑙𝑑𝑀 N-Queens Combinatorial Puzzle meetsCats monoidal functions 𝑓𝑜𝑙𝑑 and 𝑓𝑜𝑙𝑑𝑀𝑎𝑝
2. 2 https://speakerdeck.com/philipschwarz https://fosstodon.org/@philip_schwarz https://www.slideshare.net/pjschwarz https://twitter.com/philip_schwarz If you decide you like this, you can find more content like it on http://fpilluminated.com https://github.com/philipschwarz https://www.linkedin.com/in/philip-schwarz-70576a17/ Some of the other places where you can find me
4. An 8 x 8 chessboard has 64 cells. How many ways are there of placing 8 queens on the board? 4
5. An 8 x 8 chessboard has 64 cells. How many ways are there of placing 8 queens on the board? For the 1st queen, we have a choice of 64 cells 63 for the 2nd queen 62 for the 3rd 61 for the 4th 60 for the 5th 59 for the 6th 58 for the 7th 57 for the 8th 5
6. An 8 x 8 chessboard has 64 cells. How many ways are there of placing 8 queens on the board? For the 1st queen, we have a choice of 64 cells 63 for the 2nd queen 62 for the 3rd 61 for the 4th 60 for the 5th 59 for the 6th 58 for the 7th 57 for the 8th 64 × 63 × 62 × 61 × 60 × 59 × 58 × 57 = 178,462,987,637,760 6
7. An 8 x 8 chessboard has 64 cells. How many ways are there of placing 8 queens on the board? For the 1st queen, we have a choice of 64 cells 63 for the 2nd queen 62 for the 3rd 61 for the 4th 60 for the 5th 59 for the 6th 58 for the 7th 57 for the 8th 64 × 63 × 62 × 61 × 60 × 59 × 58 × 57 = 178,462,987,637,760 Given a particular placement of 8 queens, how many ways are there of arriving at it? We pick one cell at a time, in sequence, so how many different possible sequences are there for picking 8 cells? 7
8. An 8 x 8 chessboard has 64 cells. How many ways are there of placing 8 queens on the board? For the 1st queen, we have a choice of 64 cells 63 for the 2nd queen 62 for the 3rd 61 for the 4th 60 for the 5th 59 for the 6th 58 for the 7th 57 for the 8th 64 × 63 × 62 × 61 × 60 × 59 × 58 × 57 = 178,462,987,637,760 Given a particular placement of 8 queens, how many ways are there of arriving at it? We pick one cell at a time, in sequence, so how many different possible sequences are there for picking 8 cells? For our first pick, we have 8 choices. 7 for the 2nd 6 for the 3rd 5 for the 4th 4 for the 5th 3 for the 6th 2 for the 7th 1 for the 8th 8
9. An 8 x 8 chessboard has 64 cells. How many ways are there of placing 8 queens on the board? For the 1st queen, we have a choice of 64 cells 63 for the 2nd queen 62 for the 3rd 61 for the 4th 60 for the 5th 59 for the 6th 58 for the 7th 57 for the 8th 64 × 63 × 62 × 61 × 60 × 59 × 58 × 57 = 178,462,987,637,760 Given a particular placement of 8 queens, how many ways are there of arriving at it? We pick one cell at a time, in sequence, so how many different possible sequences are there for picking 8 cells? For our first pick, we have 8 choices. 7 for the 2nd 6 for the 3rd 5 for the 4th 4 for the 5th 3 for the 6th 2 for the 7th 1 for the 8th 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 8! = 40,320 9
10. So the number of candidate board configurations for the puzzle is Number of ways of placing 8 queens on the board Number of ways of arriving at each configuraPon An 8 x 8 chessboard has 64 cells. How many ways are there of placing 8 queens on the board? For the 1st queen, we have a choice of 64 cells 63 for the 2nd queen 62 for the 3rd 61 for the 4th 60 for the 5th 59 for the 6th 58 for the 7th 57 for the 8th 64 × 63 × 62 × 61 × 60 × 59 × 58 × 57 = 178,462,987,637,760 Given a particular placement of 8 queens, how many ways are there of arriving at it? We pick one cell at a time, in sequence, so how many different possible sequences are there for picking 8 cells? For our first pick, we have 8 choices. 7 for the 2nd 6 for the 3rd 5 for the 4th 4 for the 5th 3 for the 6th 2 for the 7th 1 for the 8th 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 8! = 40,320 10
11. So the number of candidate board configurations for the puzzle is 64 × 63 × 62 × 61 × 60 × 59 × 58 × 57 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 4,426,165,368 Number of ways of placing 8 queens on the board Number of ways of arriving at each configuraPon An 8 x 8 chessboard has 64 cells. How many ways are there of placing 8 queens on the board? For the 1st queen, we have a choice of 64 cells 63 for the 2nd queen 62 for the 3rd 61 for the 4th 60 for the 5th 59 for the 6th 58 for the 7th 57 for the 8th 64 × 63 × 62 × 61 × 60 × 59 × 58 × 57 = 178,462,987,637,760 Given a particular placement of 8 queens, how many ways are there of arriving at it? We pick one cell at a time, in sequence, so how many different possible sequences are there for picking 8 cells? For our first pick, we have 8 choices. 7 for the 2nd 6 for the 3rd 5 for the 4th 4 for the 5th 3 for the 6th 2 for the 7th 1 for the 8th 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 8! = 40,320 11
12. So the number of candidate board configurations for the puzzle is 64 × 63 × 62 × 61 × 60 × 59 × 58 × 57 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 4,426,165,368 Number of ways of placing 8 queens on the board Number of ways of arriving at each configuraPon An 8 x 8 chessboard has 64 cells. How many ways are there of placing 8 queens on the board? For the 1st queen, we have a choice of 64 cells 63 for the 2nd queen 62 for the 3rd 61 for the 4th 60 for the 5th 59 for the 6th 58 for the 7th 57 for the 8th 64 × 63 × 62 × 61 × 60 × 59 × 58 × 57 = 178,462,987,637,760 Given a particular placement of 8 queens, how many ways are there of arriving at it? We pick one cell at a time, in sequence, so how many different possible sequences are there for picking 8 cells? For our first pick, we have 8 choices. 7 for the 2nd 6 for the 3rd 5 for the 4th 4 for the 5th 3 for the 6th 2 for the 7th 1 for the 8th 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 8! = 40,320 We know that no more than one queen is allowed on each row, since multiple queens on the same row hold each other in check. We can use that fact to drastically reduce the number of candidate boards. 12
13. So the number of candidate board configurations for the puzzle is 64 × 63 × 62 × 61 × 60 × 59 × 58 × 57 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 4,426,165,368 Number of ways of placing 8 queens on the board Number of ways of arriving at each configuraPon An 8 x 8 chessboard has 64 cells. How many ways are there of placing 8 queens on the board? For the 1st queen, we have a choice of 64 cells 63 for the 2nd queen 62 for the 3rd 61 for the 4th 60 for the 5th 59 for the 6th 58 for the 7th 57 for the 8th 64 × 63 × 62 × 61 × 60 × 59 × 58 × 57 = 178,462,987,637,760 Given a particular placement of 8 queens, how many ways are there of arriving at it? We pick one cell at a time, in sequence, so how many different possible sequences are there for picking 8 cells? For our first pick, we have 8 choices. 7 for the 2nd 6 for the 3rd 5 for the 4th 4 for the 5th 3 for the 6th 2 for the 7th 1 for the 8th 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 8! = 40,320 We know that no more than one queen is allowed on each row, since multiple queens on the same row hold each other in check. We can use that fact to drastically reduce the number of candidate boards. To do that, instead of picking 8 cells on the whole board, we consider each of 8 rows in turn, and on each such row, we pick one of 8 columns. 8 × 8 × 8 × 8 × 8 × 8 × 8 × 8 = 88 = 16,777,216 13
14. We know that no more than one queen is allowed on each row, since multiple queens on the same row hold each other in check. We can use that fact to drastically reduce the number of candidate boards. To do that, instead of picking 8 cells on the whole board, we consider each of 8 rows in turn, and on each such row, we pick one of 8 columns. 8 × 8 × 8 × 8 × 8 × 8 × 8 × 8 = 88 = 16,777,216 An 8 x 8 chessboard has 64 cells. How many ways are there of placing 8 queens on the board? For the 1st queen, we have a choice of 64 cells 63 for the 2nd queen 62 for the 3rd 61 for the 4th 60 for the 5th 59 for the 6th 58 for the 7th 57 for the 8th 64 × 63 × 62 × 61 × 60 × 59 × 58 × 57 = 178,462,987,637,760 Given a particular placement of 8 queens, how many ways are there of arriving at it? We pick one cell at a time, in sequence, so how many different possible sequences are there for picking 8 cells? For our first pick, we have 8 choices. 7 for the 2nd 6 for the 3rd 5 for the 4th 4 for the 5th 3 for the 6th 2 for the 7th 1 for the 8th 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 8! = 40,320 We also know that no more than one queen is allowed on each column, so we can again reduce the number of candidate boards. 14 So the number of candidate board configurations for the puzzle is 64 × 63 × 62 × 61 × 60 × 59 × 58 × 57 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 4,426,165,368 Number of ways of placing 8 queens on the board Number of ways of arriving at each configuraPon
15. So the number of candidate board configurations for the puzzle is 64 × 63 × 62 × 61 × 60 × 59 × 58 × 57 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 4,426,165,368 Number of ways of placing 8 queens on the board Number of ways of arriving at each configuraPon We also know that no more than one queen is allowed on each column, so we can again reduce the number of candidate boards. If we pick a column on one row, we cannot pick it again on subsequent rows, i.e. the choice of columns that we can pick decreases as we progress through the rows. 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 8! = 40,320 An 8 x 8 chessboard has 64 cells. How many ways are there of placing 8 queens on the board? For the 1st queen, we have a choice of 64 cells 63 for the 2nd queen 62 for the 3rd 61 for the 4th 60 for the 5th 59 for the 6th 58 for the 7th 57 for the 8th 64 × 63 × 62 × 61 × 60 × 59 × 58 × 57 = 178,462,987,637,760 Given a particular placement of 8 queens, how many ways are there of arriving at it? We pick one cell at a time, in sequence, so how many different possible sequences are there for picking 8 cells? For our first pick, we have 8 choices. 7 for the 2nd 6 for the 3rd 5 for the 4th 4 for the 5th 3 for the 6th 2 for the 7th 1 for the 8th 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 8! = 40,320 We know that no more than one queen is allowed on each row, since multiple queens on the same row hold each other in check. We can use that fact to drastically reduce the number of candidate boards. To do that, instead of picking 8 cells on the whole board, we consider each of 8 rows in turn, and on each such row, we pick one of 8 columns. 8 × 8 × 8 × 8 × 8 × 8 × 8 × 8 = 88 = 16,777,216 15
16. Let’s try to find a solution to the puzzle 16
23. 23 We are stuck. There is nowhere to place queen number 6, because every empty cell on the board is in check from queens 1 to 5.
24. Let’s try again 24
34. 34 We found a solution
35. A particularly suitable application area of for expressions are combinatorial puzzles. An example of such a puzzle is the 8-queens problem: Given a standard chess-board, place eight queens such that no queen is in check from any other (a queen can check another piece if they are on the same column, row, or diagonal). Martin Odersky 35
37. (7, 3) (8, 6) (6, 7) (5, 2) (4, 8) (3, 5) (2, 1) (1, 4) R C O O W L List((8, 6), (7, 3), (6, 7), (5, 2), (4, 8), (3, 5), (2, 1), (1, 4)) 37
38. (6, 2) (7, 5) (5, 6) (4, 1) (3, 7) (2, 4) (1, 0) (0, 3) R C O O W L List(5, 2, 6, 1, 7, 4, 0, 3) 38
40. def show(queens: List[Int]): String = val lines: List[String] = for (col <- queens.reverse) yield Vector.fill(queens.length)("❎ ") .updated(col, s"👑 ") .mkString "\n" + lines.mkString("\n") 40
41. def show(queens: List[Int]): String = val lines: List[String] = for (col <- queens.reverse) yield Vector.fill(queens.length)("❎ ") .updated(col, s"👑 ") .mkString "\n" + lines.mkString("\n") List(5, 2, 6, 1, 7, 4, 0, 3) 41
42. def show(queens: List[Int]): String = val lines: List[String] = for (col <- queens.reverse) yield Vector.fill(queens.length)("❎ ") .updated(col, s"👑 ") .mkString "\n" + lines.mkString("\n") println( show( List(5, 2, 6, 1, 7, 4, 0, 3) ) ) 42
43. def show(queens: List[Int]): String = val lines: List[String] = for (col <- queens.reverse) yield Vector.fill(queens.length)("❎ ") .updated(col, s"👑 ") .mkString "\n" + lines.mkString("\n") ❎ ❎ ❎ 👑 ❎ ❎ ❎ ❎ 👑 ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ 👑 ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ 👑 ❎ 👑 ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ 👑 ❎ ❎ ❎ 👑 ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ 👑 ❎ ❎ 43
44. Compositional Vector Graphics 44
45. val redSquare = Image.square(100).fillColor(Color.red) 45
46. val redSquare = Image.square(100).fillColor(Color.red) val blueSquare = Image.square(100).fillColor(Color.blue) 46
47. val redSquare = Image.square(100).fillColor(Color.red) val blueSquare = Image.square(100).fillColor(Color.blue) val redBesideBlue = redSquare.beside(blueSquare) 47
48. val redSquare = Image.square(100).fillColor(Color.red) val blueSquare = Image.square(100).fillColor(Color.blue) val redBesideBlue = redSquare.beside(blueSquare) val redAboveBlue = redSquare.above(blueSquare) 48
49. Solution 49
50. create Solution red and white square images 50 Image.square Image.fillColor
51. create Solution red and white square images compose composite solution image 51 Image.beside Image.above Image.square Image.fillColor
52. val square: Image = Image.square(100).strokeColor(Color.black) val emptySquare: Image = square.fillColor(Color.white) val fullSquare: Image = square.fillColor(Color.orangeRed) 52
53. def combine(imageGrid: List[List[Image]]): Image = imageGrid .map(_.reduce(_ beside _)) .reduce(_ above _) 53
54. def combine(imageGrid: List[List[Image]]): Image = imageGrid .map(_.reduce(_ beside _)) .reduce(_ above _) m a p 54
55. def combine(imageGrid: List[List[Image]]): Image = imageGrid .map(_.reduce(_ beside _)) .reduce(_ above _) reduce m a p reduce reduce reduce 55 beside
56. def combine(imageGrid: List[List[Image]]): Image = imageGrid .map(_.reduce(_ beside _)) .reduce(_ above _) reduce m a p reduce reduce reduce r e d u c e 56 above beside
57. def combine(imageGrid: List[List[Image]]): Image = imageGrid .map(_.reduce(_ beside _)) .reduce(_ above _) 57
58. def combine(imageGrid: List[List[Image]]): Image = imageGrid .map(_.reduce(_ beside _)) .reduce(_ above _) def combine(imageGrid: List[List[Image]]): Image = imageGrid .map(_.fold(Image.empty)(_ beside _)) .fold(Image.empty)(_ above _) safer to use fold, in case any of the lists is empty 58
59. def combine(imageGrid: List[List[Image]]): Image = imageGrid .map(_.reduce(_ beside _)) .reduce(_ above _) def combine(imageGrid: List[List[Image]]): Image = imageGrid .map(_.fold(Image.empty)(_ beside _)) .fold(Image.empty)(_ above _) def combine(imageGrid: List[List[Image]]): Image = imageGrid .map(_.foldLeft(Image.empty)(_ beside _)) .foldLeft(Image.empty)(_ above _) safer to use fold, in case any of the lists is empty fold is just an alias for foldLeft 59
60. trait Foldable[F[_]] { def foldMap[A, B](as: F[A])(f: A => B)(mb: Monoid[B]): B = foldRight(as)(mb.zero)((a, b) => mb.op(f(a), b)) def foldRight[A, B](as: F[A])(z: B)(f: (A, B) => B): B = foldMap(as)(f.curried)(endoMonoid[B])(z) def concatenate[A](as: F[A])(m: Monoid[A]): A = foldLeft(as)(m.zero)(m.op) def foldLeft[A, B](as: F[A])(z: B)(f: (B, A) => B): B = foldMap(as)(a => (b: B) => f(b, a))(dual(endoMonoid[B]))(z) def toList[A](as: F[A]): List[A] = foldRight(as)(List[A]())(_ :: _) } trait Monoid[A] { def op(a1: A, a2: A): A def zero: A } 60
61. trait Foldable[F[_]] { def foldMap[A, B](as: F[A])(f: A => B)(mb: Monoid[B]): B = foldRight(as)(mb.zero)((a, b) => mb.op(f(a), b)) def foldRight[A, B](as: F[A])(z: B)(f: (A, B) => B): B = foldMap(as)(f.curried)(endoMonoid[B])(z) def concatenate[A](as: F[A])(m: Monoid[A]): A = foldLeft(as)(m.zero)(m.op) def foldLeft[A, B](as: F[A])(z: B)(f: (B, A) => B): B = foldMap(as)(a => (b: B) => f(b, a))(dual(endoMonoid[B]))(z) def toList[A](as: F[A]): List[A] = foldRight(as)(List[A]())(_ :: _) } trait Monoid[A] { def op(a1: A, a2: A): A def zero: A } concatenate fold,combineAll foldMap foldMap foldLeft foldLeft foldRight foldRight 61
67. import cats.Monoid 67 assert(Monoid[Int].combine(2,3) == 5) assert(Monoid[Int].combine(2, Monoid[Int].empty) == 2)
68. import cats.Monoid import cats.syntax.monoid.* 68 assert(Monoid[Int].combine(2,3) == 5) assert(Monoid[Int].combine(2, Monoid[Int].empty) == 2) assert((2 |+| 3) == 5) assert((2 |+| Monoid[Int].empty) == 2)
69. import cats.Monoid import cats.syntax.monoid.* 69 assert(Monoid[Int].combine(2,3) == 5) assert(Monoid[Int].combine(2, Monoid[Int].empty) == 2) assert((2 |+| 3) == 5) assert((2 |+| Monoid[Int].empty) == 2) assert(Monoid[Int].empty == 0)
70. import cats.Monoid import cats.syntax.monoid.* import cats.syntax.foldable.* 70 assert(Monoid[Int].combine(2,3) == 5) assert(Monoid[Int].combine(2, Monoid[Int].empty) == 2) assert((2 |+| 3) == 5) assert((2 |+| Monoid[Int].empty) == 2) assert(Monoid[Int].empty == 0) assert(List.empty[Int].combineAll == 0) assert(List(1, 2, 3, 4).combineAll == 10) trait Foldable[F[_]] { … def concatenate[A](as: F[A])(m: Monoid[A]): A = foldLeft(as)(m.zero)(m.op) … }
71. import cats.Monoid import cats.syntax.monoid.* import cats.syntax.foldable.* 71 assert(Monoid[Int].combine(2,3) == 5) assert(Monoid[Int].combine(2, Monoid[Int].empty) == 2) assert((2 |+| 3) == 5) assert((2 |+| Monoid[Int].empty) == 2) assert(Monoid[Int].empty == 0) assert(List.empty[Int].combineAll == 0) assert(List(1, 2, 3, 4).combineAll == 10) val prodMonoid = cats.Monoid.instance[Int](emptyValue = 1, cmb = _ * _)
72. import cats.Monoid import cats.syntax.monoid.* import cats.syntax.foldable.* 72 assert(Monoid[Int].combine(2,3) == 5) assert(Monoid[Int].combine(2, Monoid[Int].empty) == 2) assert((2 |+| 3) == 5) assert((2 |+| Monoid[Int].empty) == 2) assert(Monoid[Int].empty == 0) assert(List.empty[Int].combineAll == 0) assert(List(1, 2, 3, 4).combineAll == 10) val prodMonoid = cats.Monoid.instance[Int](emptyValue = 1, cmb = _ * _) assert(prodMonoid.combine(2, 3) == 6) assert(prodMonoid.combine(3, prodMonoid.empty) == 3)
73. import cats.Monoid import cats.syntax.monoid.* import cats.syntax.foldable.* 73 assert(Monoid[Int].combine(2,3) == 5) assert(Monoid[Int].combine(2, Monoid[Int].empty) == 2) assert((2 |+| 3) == 5) assert((2 |+| Monoid[Int].empty) == 2) assert(Monoid[Int].empty == 0) assert(List.empty[Int].combineAll == 0) assert(List(1, 2, 3, 4).combineAll == 10) val prodMonoid = cats.Monoid.instance[Int](emptyValue = 1, cmb = _ * _) assert(prodMonoid.combine(2, 3) == 6) assert(prodMonoid.combine(3, prodMonoid.empty) == 3) assert(prodMonoid.empty == 1)
74. import cats.Monoid import cats.syntax.monoid.* import cats.syntax.foldable.* 74 assert(Monoid[Int].combine(2,3) == 5) assert(Monoid[Int].combine(2, Monoid[Int].empty) == 2) assert((2 |+| 3) == 5) assert((2 |+| Monoid[Int].empty) == 2) assert(Monoid[Int].empty == 0) assert(List.empty[Int].combineAll == 0) assert(List(1, 2, 3, 4).combineAll == 10) val prodMonoid = cats.Monoid.instance[Int](emptyValue = 1, cmb = _ * _) assert(prodMonoid.combine(2, 3) == 6) assert(prodMonoid.combine(3, prodMonoid.empty) == 3) assert(prodMonoid.empty == 1) assert(List.empty[Int].combineAll(prodMonoid) == 1) assert(List(1, 2, 3, 4).combineAll(prodMonoid) == 24)
75. def combine(imageGrid: List[List[Image]]): Image = imageGrid .map(_.foldLeft(Image.empty)(_ beside _)) .foldLeft(Image.empty)(_ above _) 75
76. def combine(imageGrid: List[List[Image]]): Image = imageGrid .map(_.foldLeft(Image.empty)(_ beside _)) .foldLeft(Image.empty)(_ above _) import cats.Monoid import cats.implicits.* val beside = Monoid.instance[Image](Image.empty, _ beside _) 76
77. def combine(imageGrid: List[List[Image]]): Image = imageGrid .map(_.foldLeft(Image.empty)(_ beside _)) .foldLeft(Image.empty)(_ above _) def combine(imageGrid: List[List[Image]]): Image = imageGrid .map(_.combineAll(beside)) .foldLeft(Image.empty)(_ above _) import cats.Monoid import cats.implicits.* val beside = Monoid.instance[Image](Image.empty, _ beside _) 77
78. trait Foldable[F[_]] { def foldMap[A, B](as: F[A])(f: A => B)(mb: Monoid[B]): B = foldRight(as)(mb.zero)((a, b) => mb.op(f(a), b)) def foldRight[A, B](as: F[A])(z: B)(f: (A, B) => B): B = foldMap(as)(f.curried)(endoMonoid[B])(z) def concatenate[A](as: F[A])(m: Monoid[A]): A = foldLeft(as)(m.zero)(m.op) def foldLeft[A, B](as: F[A])(z: B)(f: (B, A) => B): B = foldMap(as)(a => (b: B) => f(b, a))(dual(endoMonoid[B]))(z) def toList[A](as: F[A]): List[A] = foldRight(as)(List[A]())(_ :: _) } trait Monoid[A] { def op(a1: A, a2: A): A def zero: A } concatenate fold,combineAll foldMap foldMap foldLeft foldLeft foldRight foldRight The marketing buzzword for foldMap is MapReduce. 78
79. object ListFoldable extends Foldable[List] { override def foldMap[A, B](as:List[A])(f: A => B)(mb: Monoid[B]): B = foldLeft(as)(mb.zero)((b, a) => mb.op(b, f(a))) override def foldRight[A, B](as: List[A])(z: B)(f: (A,B) => B) = as match { case Nil => z case Cons(h, t) => f(h, foldRight(t, z)(f)) } override def foldLeft[A, B](as: List[A])(z: B)(f: (B,A) => B) = as match { case Nil => z case Cons(h, t) => foldLeft(t, f(z,h))(f) } } 79
80. def combine(imageGrid: List[List[Image]]): Image = imageGrid .map(_.combineAll(beside)) .foldLeft(Image.empty)(_ above _) 80
81. def combine(imageGrid: List[List[Image]]): Image = imageGrid .map(_.combineAll(beside)) .foldLeft(Image.empty)(_ above _) purely to make the next step easier to understand, let’s revert to using reduce rather than foldLeft. 81
82. def combine(imageGrid: List[List[Image]]): Image = imageGrid .map(_.combineAll(beside)) .foldLeft(Image.empty)(_ above _) def combine(imageGrid: List[List[Image]]): Image = imageGrid .map(_.combineAll(beside)) .reduce(_ above _) purely to make the next step easier to understand, let’s revert to using reduce rather than foldLeft. 82
83. def combine(imageGrid: List[List[Image]]): Image = imageGrid .map(_.combineAll(beside)) .reduce(_ above _) MapReduce is the marketing buzzword for foldMap 83
84. def combine(imageGrid: List[List[Image]]): Image = imageGrid .map(_.combineAll(beside)) .reduce(_ above _) val above = Monoid.instance[Image](Image.empty, _ above _) MapReduce is the marketing buzzword for foldMap 84
85. def combine(imageGrid: List[List[Image]]): Image = imageGrid .map(_.combineAll(beside)) .reduce(_ above _) def combine(imageGrid: List[List[Image]]): Image = imageGrid.foldMap(_.combineAll(beside))(above) val above = Monoid.instance[Image](Image.empty, _ above _) MapReduce is the marketing buzzword for foldMap 85
86. def combine(imageGrid: List[List[Image]]): Image = imageGrid .map(_.reduce(_ beside _)) .reduce(_ above _) def combine(imageGrid: List[List[Image]]): Image = imageGrid.foldMap(_.combineAll(beside))(above) RECAP 86
87. def combine(imageGrid: List[List[Image]]): Image = imageGrid.foldMap(_.fold(beside))(above) fold f o l d M a p fold fold fold 87 beside above
88. def show(queens: List[Int]): String = val lines: List[String] = for (col <- queens.reverse) yield Vector.fill(queens.length)("❎ ") .updated(col, s"👑 ") .mkString "\n" + lines.mkString("\n") 88 ❎ ❎ ❎ 👑 ❎ ❎ ❎ ❎ 👑 ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ 👑 ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ 👑 ❎ 👑 ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ 👑 ❎ ❎ ❎ 👑 ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ 👑 ❎ ❎
89. def show(queens: List[Int]): String = val lines: List[String] = for (col <- queens.reverse) yield Vector.fill(queens.length)("❎ ") .updated(col, s"👑 ") .mkString "\n" + lines.mkString("\n") 89 def show(queens: List[Int]): Image = val squareImageGrid: List[List[Image]] = for col <- queens.reverse yield List.fill(queens.length)(emptySquare) .updated(col,fullSquare) combine(squareImageGrid) ❎ ❎ ❎ 👑 ❎ ❎ ❎ ❎ 👑 ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ 👑 ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ 👑 ❎ 👑 ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ 👑 ❎ ❎ ❎ 👑 ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ 👑 ❎ ❎
90. def show(queens: List[Int]): String = val lines: List[String] = for (col <- queens.reverse) yield Vector.fill(queens.length)("❎ ") .updated(col, s"👑 ") .mkString "\n" + lines.mkString("\n") ❎ ❎ ❎ 👑 ❎ ❎ ❎ ❎ 👑 ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ 👑 ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ 👑 ❎ 👑 ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ 👑 ❎ ❎ ❎ 👑 ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ ❎ 👑 ❎ ❎ 90 def show(queens: List[Int]): Image = val squareImageGrid: List[List[Image]] = for col <- queens.reverse yield List.fill(queens.length)(emptySquare) .updated(col,fullSquare) combine(squareImageGrid)
92. We can do a bit more though 92
93. 93 The images that we have been creating up to now have been centered on the origin of the coordinate system
94. val (x,y) = … squareImage = squareImageAtOrigin.at(x,y) val (x,y) = … boardImage = boardImageAtOrigin.at(x,y) 94 But we can use an image’s at function to specify a desired position for the image And if we are prepared to do that, we can further simplify the way we combine images
95. def combine(imageGrid: List[List[Image]]): Image = imageGrid.foldMap(_ combineAll beside)(above) 95
96. def combine(imageGrid: List[List[Image]]): Image = imageGrid.foldMap(_ combineAll beside)(above) val on = Monoid.instance[Image](Image.empty, _ on _) 96
97. def combine(imageGrid: List[List[Image]]): Image = imageGrid.foldMap(_ combineAll on)(on) def combine(imageGrid: List[List[Image]]): Image = imageGrid.foldMap(_ combineAll beside)(above) val on = Monoid.instance[Image](Image.empty, _ on _) 97
98. val on = Monoid.instance[Image](Image.empty, _ on _) def combine(imageGrid: List[List[Image]]): Image = imageGrid.foldMap(_ combineAll on)(on) 98
99. given Monoid.instance[Image] = Monoid.instance[Image](Image.empty, _ on _) def combine(imageGrid: List[List[Image]]): Image = imageGrid.foldMap(_ combineAll) val on = Monoid.instance[Image](Image.empty, _ on _) def combine(imageGrid: List[List[Image]]): Image = imageGrid.foldMap(_ combineAll on)(on) 99
100. def combine(imageGrid: List[List[Image]]): Image = imageGrid .map(_.reduce(_ beside _)) .reduce(_ above _) FULL RECAP 100
101. given Monoid.instance[Image] = Monoid.instance[Image](Image.empty, _ on _) def combine(imageGrid: List[List[Image]]): Image = imageGrid.foldMap(_ combineAll) def combine(imageGrid: List[List[Image]]): Image = imageGrid .map(_.reduce(_ beside _)) .reduce(_ above _) FULL RECAP 101
102. 8 × 8 × 8 × 8 × 8 × 8 × 8 × 8 = 88 = 16,777,216 i.e. # of permutations of 8 queens (repetition allowed) Earlier we looked at the number of ways of placing 8 queens on the board, one queen per row 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 8! = 40,320 “ “ “ “ “ without repetition 102
103. Earlier we looked at the number of ways of placing 8 queens on the board, one queen per row So the formulas for arbitrary N are the following: 𝑁𝑁 # of permutations of N queens (repetition allowed) 𝑁! # of permutations of N queens without repetition 8 × 8 × 8 × 8 × 8 × 8 × 8 × 8 = 88 = 16,777,216 i.e. # of permutations of 8 queens (repetition allowed) 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 8! = 40,320 “ “ “ “ “ without repetition 103
104. How do we compute the permutations of N queens, e.g. for N=4? 104
105. def permutations(): List[List[Int]] = { for firstQueen <- 1 to 4 secondQueen <- 1 to 4 thirdQueen <- 1 to 4 fourthQueen <- 1 to 4 queens = List(firstQueen, secondQueen, thirdQueen, fourthQueen) yield queens }.toList 105
106. List( List(1, 1, 1, 1), List(1, 1, 1, 2), List(1, 1, 1, 3), List(1, 1, 1, 4), List(1, 1, 2, 1), List(1, 1, 2, 2), List(1, 1, 2, 3), List(1, 1, 2, 4), List(1, 1, 3, 1), List(1, 1, 3, 2), List(1, 1, 3, 3), List(1, 1, 3, 4), List(1, 1, 4, 1), List(1, 1, 4, 2), List(1, 1, 4, 3), List(1, 1, 4, 4), List(1, 2, 1, 1), List(1, 2, 1, 2), List(1, 2, 1, 3), List(1, 2, 1, 4), List(1, 2, 2, 1), List(1, 2, 2, 2), List(1, 2, 2, 3), List(1, 2, 2, 4), List(1, 2, 3, 1), List(1, 2, 3, 2), List(1, 2, 3, 3), List(1, 2, 3, 4), List(1, 2, 4, 1), List(1, 2, 4, 2), List(1, 2, 4, 3), List(1, 2, 4, 4), List(1, 3, 1, 1), List(1, 3, 1, 2), List(1, 3, 1, 3), List(1, 3, 1, 4), List(1, 3, 2, 1), List(1, 3, 2, 2), List(1, 3, 2, 3), List(1, 3, 2, 4), List(1, 3, 3, 1), List(1, 3, 3, 2), List(1, 3, 3, 3), List(1, 3, 3, 4), List(1, 3, 4, 1), List(1, 3, 4, 2), List(1, 3, 4, 3), List(1, 3, 4, 4), List(1, 4, 1, 1), List(1, 4, 1, 2), List(1, 4, 1, 3), List(1, 4, 1, 4), List(1, 4, 2, 1), List(1, 4, 2, 2), List(1, 4, 2, 3), List(1, 4, 2, 4), List(1, 4, 3, 1), List(1, 4, 3, 2), List(1, 4, 3, 3), List(1, 4, 3, 4), List(1, 4, 4, 1), List(1, 4, 4, 2), List(1, 4, 4, 3), List(1, 4, 4, 4), List(2, 1, 1, 1), List(2, 1, 1, 2), List(2, 1, 1, 3), List(2, 1, 1, 4), List(2, 1, 2, 1), List(2, 1, 2, 2), List(2, 1, 2, 3), List(2, 1, 2, 4), List(2, 1, 3, 1), List(2, 1, 3, 2), List(2, 1, 3, 3), List(2, 1, 3, 4), List(2, 1, 4, 1), List(2, 1, 4, 2), List(2, 1, 4, 3), List(2, 1, 4, 4), List(2, 2, 1, 1), List(2, 2, 1, 2), List(2, 2, 1, 3), List(2, 2, 1, 4), List(2, 2, 2, 1), List(2, 2, 2, 2), List(2, 2, 2, 3), List(2, 2, 2, 4), List(2, 2, 3, 1), List(2, 2, 3, 2), List(2, 2, 3, 3), List(2, 2, 3, 4), List(2, 2, 4, 1), List(2, 2, 4, 2), List(2, 2, 4, 3), List(2, 2, 4, 4), List(2, 3, 1, 1), List(2, 3, 1, 2), List(2, 3, 1, 3), List(2, 3, 1, 4), List(2, 3, 2, 1), List(2, 3, 2, 2), List(2, 3, 2, 3), List(2, 3, 2, 4), List(2, 3, 3, 1), List(2, 3, 3, 2), List(2, 3, 3, 3), List(2, 3, 3, 4), List(2, 3, 4, 1), List(2, 3, 4, 2), List(2, 3, 4, 3), List(2, 3, 4, 4), List(2, 4, 1, 1), List(2, 4, 1, 2), List(2, 4, 1, 3), List(2, 4, 1, 4), List(2, 4, 2, 1), List(2, 4, 2, 2), List(2, 4, 2, 3), List(2, 4, 2, 4), List(2, 4, 3, 1), List(2, 4, 3, 2), List(2, 4, 3, 3), List(2, 4, 3, 4), List(2, 4, 4, 1), List(2, 4, 4, 2), List(2, 4, 4, 3), List(2, 4, 4, 4), List(3, 1, 1, 1), List(3, 1, 1, 2), List(3, 1, 1, 3), List(3, 1, 1, 4), List(3, 1, 2, 1), List(3, 1, 2, 2), List(3, 1, 2, 3), List(3, 1, 2, 4), List(3, 1, 3, 1), List(3, 1, 3, 2), List(3, 1, 3, 3), List(3, 1, 3, 4), List(3, 1, 4, 1), List(3, 1, 4, 2), List(3, 1, 4, 3), List(3, 1, 4, 4), List(3, 2, 1, 1), List(3, 2, 1, 2), List(3, 2, 1, 3), List(3, 2, 1, 4), List(3, 2, 2, 1), List(3, 2, 2, 2), List(3, 2, 2, 3), List(3, 2, 2, 4), List(3, 2, 3, 1), List(3, 2, 3, 2), List(3, 2, 3, 3), List(3, 2, 3, 4), List(3, 2, 4, 1), List(3, 2, 4, 2), List(3, 2, 4, 3), List(3, 2, 4, 4), List(3, 3, 1, 1), List(3, 3, 1, 2), List(3, 3, 1, 3), List(3, 3, 1, 4), List(3, 3, 2, 1), List(3, 3, 2, 2), List(3, 3, 2, 3), List(3, 3, 2, 4), List(3, 3, 3, 1), List(3, 3, 3, 2), List(3, 3, 3, 3), List(3, 3, 3, 4), List(3, 3, 4, 1), List(3, 3, 4, 2), List(3, 3, 4, 3), List(3, 3, 4, 4), List(3, 4, 1, 1), List(3, 4, 1, 2), List(3, 4, 1, 3), List(3, 4, 1, 4), List(3, 4, 2, 1), List(3, 4, 2, 2), List(3, 4, 2, 3), List(3, 4, 2, 4), List(3, 4, 3, 1), List(3, 4, 3, 2), List(3, 4, 3, 3), List(3, 4, 3, 4), List(3, 4, 4, 1), List(3, 4, 4, 2), List(3, 4, 4, 3), List(3, 4, 4, 4), List(4, 1, 1, 1), List(4, 1, 1, 2), List(4, 1, 1, 3), List(4, 1, 1, 4), List(4, 1, 2, 1), List(4, 1, 2, 2), List(4, 1, 2, 3), List(4, 1, 2, 4), List(4, 1, 3, 1), List(4, 1, 3, 2), List(4, 1, 3, 3), List(4, 1, 3, 4), List(4, 1, 4, 1), List(4, 1, 4, 2), List(4, 1, 4, 3), List(4, 1, 4, 4), List(4, 2, 1, 1), List(4, 2, 1, 2), List(4, 2, 1, 3), List(4, 2, 1, 4), List(4, 2, 2, 1), List(4, 2, 2, 2), List(4, 2, 2, 3), List(4, 2, 2, 4), List(4, 2, 3, 1), List(4, 2, 3, 2), List(4, 2, 3, 3), List(4, 2, 3, 4), List(4, 2, 4, 1), List(4, 2, 4, 2), List(4, 2, 4, 3), List(4, 2, 4, 4), List(4, 3, 1, 1), List(4, 3, 1, 2), List(4, 3, 1, 3), List(4, 3, 1, 4), List(4, 3, 2, 1), List(4, 3, 2, 2), List(4, 3, 2, 3), List(4, 3, 2, 4), List(4, 3, 3, 1), List(4, 3, 3, 2), List(4, 3, 3, 3), List(4, 3, 3, 4), List(4, 3, 4, 1), List(4, 3, 4, 2), List(4, 3, 4, 3), List(4, 3, 4, 4), List(4, 4, 1, 1), List(4, 4, 1, 2), List(4, 4, 1, 3), List(4, 4, 1, 4), List(4, 4, 2, 1), List(4, 4, 2, 2), List(4, 4, 2, 3), List(4, 4, 2, 4), List(4, 4, 3, 1), List(4, 4, 3, 2), List(4, 4, 3, 3), List(4, 4, 3, 4), List(4, 4, 4, 1), List(4, 4, 4, 2), List(4, 4, 4, 3), List(4, 4, 4, 4)) 106
107. 107 # of results = 256 (size of result) # of permutations with repetition allowed = 256 (44) # of permutations with repetition disallowed = 24 (4!) def permutations(): List[List[Int]] = { for firstQueen <- 1 to 4 secondQueen <- 1 to 4 thirdQueen <- 1 to 4 fourthQueen <- 1 to 4 queens = List(firstQueen, secondQueen, thirdQueen, fourthQueen) yield queens }.toList println(s"# of results = ${results.size}") println(s"# of permutations with repetition allowed = ${4 * 4 * 4 * 4}") // NN println(s"# of permutations with repetition disallowed = ${4 * 3 * 2 * 1}") // N!
108. N = 4 # of permutations = 44 = 256 108
109. N = 4 # of permutations = 44 = 256 How many of these are solutions? 109
110. N N-queens solution count 1 1 2 0 3 0 4 2 5 10 6 4 7 40 8 92 9 352 10 724 11 2,680 12 14,200 13 73,712 14 365,596 15 2,279,184 16 14,772,512 17 95,815,104 18 666,090,624 19 4,968,057,848 20 39,029,188,884 21 314,666,222,712 22 2,691,008,701,644 23 24,233,937,684,440 24 227,514,171,973,736 25 2,207,893,435,808,352 26 22,317,699,616,364,044 27 234,907,967,154,122,528 data source: https://en.wikipedia.org/wiki/Eight_queens_puzzle 110
111. N = 4 # of permutations = 44 = 256 # of solutions = 2 111
112. How do we find the solutions? 112
113. A full solution can not be found in a single step. It needs to be built up gradually, by occupying successive rows with queens. This suggests a recursive algorithm. Martin Odersky 113
114. Martin Odersky Assume you have already generated all solutions of placing k queens on a board of size N x N, where k is less than N. … Now, to place the next queen in row k + 1, generate all possible extensions of each previous solution by one more queen. 114
115. Martin Odersky Assume you have already generated all solutions of placing k queens on a board of size N x N, where k is less than N. … Now, to place the next queen in row k + 1, generate all possible extensions of each previous solution by one more queen. This yields another list of solutions lists, this time of length k + 1. Continue the process until you have obtained all solutions of the size of the chess-board N. 115
116. def permutations(): List[List[Int]] = { for firstQueen <- 1 to 4 secondQueen <- 1 to 4 thirdQueen <- 1 to 4 fourthQueen <- 1 to 4 queens = List(firstQueen, secondQueen, thirdQueen, fourthQueen) yield queens }.toList 116
117. def permutations(n:Int = 4): List[List[Int]] = if n == 0 then List(List()) else for queens <- permutations(n-1) queen <- 1 to 4 yield queen :: queens def permutations(): List[List[Int]] = { for firstQueen <- 1 to 4 secondQueen <- 1 to 4 thirdQueen <- 1 to 4 fourthQueen <- 1 to 4 queens = List(firstQueen, secondQueen, thirdQueen, fourthQueen) yield queens }.toList simplify by using recursion 117
118. def permutations(n:Int = 4): List[List[Int]] = if n == 0 then List(List()) else for queens <- permutations(n-1) queen <- 1 to 4 yield queen :: queens def permutations(): List[List[Int]] = { for firstQueen <- 1 to 4 secondQueen <- 1 to 4 thirdQueen <- 1 to 4 fourthQueen <- 1 to 4 queens = List(firstQueen, secondQueen, thirdQueen, fourthQueen) yield queens }.toList simplify by using recursion 118
119. def permutations(n:Int = 4): List[List[Int]] = if n == 0 then List(List()) else for queens <- permutations(n-1) queen <- 1 to 4 yield queen :: queens def permutations(): List[List[Int]] = { for firstQueen <- 1 to 4 secondQueen <- 1 to 4 thirdQueen <- 1 to 4 fourthQueen <- 1 to 4 queens = List(firstQueen, secondQueen, thirdQueen, fourthQueen) yield queens }.toList simplify by using recursion 119
120. def permutations(n:Int = 4): List[List[Int]] = if n == 0 then List(List()) else for queens <- permutations(n-1) queen <- 1 to 4 yield queen :: queens def permutations(): List[List[Int]] = { for firstQueen <- 1 to 4 secondQueen <- 1 to 4 thirdQueen <- 1 to 4 fourthQueen <- 1 to 4 queens = List(firstQueen, secondQueen, thirdQueen, fourthQueen) yield queens }.toList simplify by using recursion 120
121. def permutations(n:Int = 4): List[List[Int]] = if n == 0 then List(List()) else for queens <- permutations(n-1) queen <- 1 to 4 yield queen :: queens def permutations(): List[List[Int]] = { for firstQueen <- 1 to 4 secondQueen <- 1 to 4 thirdQueen <- 1 to 4 fourthQueen <- 1 to 4 queens = List(firstQueen, secondQueen, thirdQueen, fourthQueen) yield queens }.toList simplify by using recursion 121
122. N = 4 # of permutations = 44 = 256 Same result as before using recursion 122
123. def queens(n: Int): List[List[(Int,Int)]] = { def placeQueens(k: Int): List[List[(Int,Int)]] = if (k == 0) List(List()) else for { queens <- placeQueens(k - 1) column <- 1 to n queen = (k, column) if isSafe(queen, queens) } yield queen :: queens placeQueens(n) } def queens(n: Int): Set[List[Int]] = { def placeQueens(k: Int): Set[List[Int]] = if (k == 0) Set(List()) else for { queens <- placeQueens(k - 1) col <- 0 until n if isSafe(col, queens) } yield col :: queens placeQueens(n) } def isSafe(queen: (Int, Int), queens: List[(Int, Int)]) = queens forall (q => !inCheck(queen, q)) def inCheck(q1: (Int, Int), q2: (Int, Int)) = q1._1 == q2._1 || // same row q1._2 == q2._2 || // same column (q1._1 - q2._1).abs == (q1._2 - q2._2).abs // on diagonal def isSafe(col: Int, queens: List[Int]): Boolean = { val row = queens.length val queensWithRow = (row - 1 to 0 by -1) zip queens queensWithRow forall { case (r, c) => col != c && math.abs(col - c) != row - r } } Martin Odersky This algorithmic idea is embodied in function placeQueens. 123
124. def queens(n: Int): List[List[(Int,Int)]] = { def placeQueens(k: Int): List[List[(Int,Int)]] = if (k == 0) List(List()) else for { queens <- placeQueens(k - 1) column <- 1 to n queen = (k, column) if isSafe(queen, queens) } yield queen :: queens placeQueens(n) } def permutations(n:Int = 4): List[List[Int]] = if n == 0 then List(List()) else for queens <- permutations(n-1) queen <- 1 to 4 yield queen :: queens 124
125. The only remaining bit is the isSafe method, which is used to check whether a given queen is in check from any other element in a list of queens. Here is the definition: The isSafe method expresses that a queen is safe with respect to some other queens if it is not in check from any other queen. The inCheck method expresses that queens q1 and q2 are mutually in check. It returns true in one of three cases: 1. If the two queens have the same row coordinate. 2. If the two queens have the same column coordinate. 3. If the two queens are on the same diagonal (i.e., the difference between their rows and the difference between their columns are the same). The first case – that the two queens have the same row coordinate – cannot happen in the application because placeQueens already takes care to place each queen in a different row. So you could remove the test without changing the functionality of the program. def isSafe(queen: (Int, Int), queens: List[(Int, Int)]) = queens forall (q => !inCheck(queen, q)) def inCheck(q1: (Int, Int), q2: (Int, Int)) = q1._1 == q2._1 || // same row q1._2 == q2._2 || // same column (q1._1 - q2._1).abs == (q1._2 - q2._2).abs // on diagonal Martin Odersky 125
126. def permutations(n:Int = 4): List[List[Int]] = if n == 0 then List(List()) else for queens <- permutations(n-1) queen <- 1 to 4 yield queen :: queens 126
127. def permutations(n:Int = 4): List[List[Int]] = if n == 0 then List(List()) else for queens <- permutations(n-1) queen <- 1 to 4 if isSafe(queen,queens) yield queen :: queens use isSafe function def permutations(n:Int = 4): List[List[Int]] = if n == 0 then List(List()) else for queens <- permutations(n-1) queen <- 1 to 4 yield queen :: queens 127
128. List( List(1, 1, 1, 1), List(1, 1, 1, 2), List(1, 1, 1, 3), List(1, 1, 1, 4), List(1, 1, 2, 1), List(1, 1, 2, 2), List(1, 1, 2, 3), List(1, 1, 2, 4), List(1, 1, 3, 1), List(1, 1, 3, 2), List(1, 1, 3, 3), List(1, 1, 3, 4), List(1, 1, 4, 1), List(1, 1, 4, 2), List(1, 1, 4, 3), List(1, 1, 4, 4), List(1, 2, 1, 1), List(1, 2, 1, 2), List(1, 2, 1, 3), List(1, 2, 1, 4), List(1, 2, 2, 1), List(1, 2, 2, 2), List(1, 2, 2, 3), List(1, 2, 2, 4), List(1, 2, 3, 1), List(1, 2, 3, 2), List(1, 2, 3, 3), List(1, 2, 3, 4), List(1, 2, 4, 1), List(1, 2, 4, 2), List(1, 2, 4, 3), List(1, 2, 4, 4), List(1, 3, 1, 1), List(1, 3, 1, 2), List(1, 3, 1, 3), List(1, 3, 1, 4), List(1, 3, 2, 1), List(1, 3, 2, 2), List(1, 3, 2, 3), List(1, 3, 2, 4), List(1, 3, 3, 1), List(1, 3, 3, 2), List(1, 3, 3, 3), List(1, 3, 3, 4), List(1, 3, 4, 1), List(1, 3, 4, 2), List(1, 3, 4, 3), List(1, 3, 4, 4), List(1, 4, 1, 1), List(1, 4, 1, 2), List(1, 4, 1, 3), List(1, 4, 1, 4), List(1, 4, 2, 1), List(1, 4, 2, 2), List(1, 4, 2, 3), List(1, 4, 2, 4), List(1, 4, 3, 1), List(1, 4, 3, 2), List(1, 4, 3, 3), List(1, 4, 3, 4), List(1, 4, 4, 1), List(1, 4, 4, 2), List(1, 4, 4, 3), List(1, 4, 4, 4), List(2, 1, 1, 1), List(2, 1, 1, 2), List(2, 1, 1, 3), List(2, 1, 1, 4), List(2, 1, 2, 1), List(2, 1, 2, 2), List(2, 1, 2, 3), List(2, 1, 2, 4), List(2, 1, 3, 1), List(2, 1, 3, 2), List(2, 1, 3, 3), List(2, 1, 3, 4), List(2, 1, 4, 1), List(2, 1, 4, 2), List(2, 1, 4, 3), List(2, 1, 4, 4), List(2, 2, 1, 1), List(2, 2, 1, 2), List(2, 2, 1, 3), List(2, 2, 1, 4), List(2, 2, 2, 1), List(2, 2, 2, 2), List(2, 2, 2, 3), List(2, 2, 2, 4), List(2, 2, 3, 1), List(2, 2, 3, 2), List(2, 2, 3, 3), List(2, 2, 3, 4), List(2, 2, 4, 1), List(2, 2, 4, 2), List(2, 2, 4, 3), List(2, 2, 4, 4), List(2, 3, 1, 1), List(2, 3, 1, 2), List(2, 3, 1, 3), List(2, 3, 1, 4), List(2, 3, 2, 1), List(2, 3, 2, 2), List(2, 3, 2, 3), List(2, 3, 2, 4), List(2, 3, 3, 1), List(2, 3, 3, 2), List(2, 3, 3, 3), List(2, 3, 3, 4), List(2, 3, 4, 1), List(2, 3, 4, 2), List(2, 3, 4, 3), List(2, 3, 4, 4), List(2, 4, 1, 1), List(2, 4, 1, 2), List(2, 4, 1, 3), List(2, 4, 1, 4), List(2, 4, 2, 1), List(2, 4, 2, 2), List(2, 4, 2, 3), List(2, 4, 2, 4), List(2, 4, 3, 1), List(2, 4, 3, 2), List(2, 4, 3, 3), List(2, 4, 3, 4), List(2, 4, 4, 1), List(2, 4, 4, 2), List(2, 4, 4, 3), List(2, 4, 4, 4), List(3, 1, 1, 1), List(3, 1, 1, 2), List(3, 1, 1, 3), List(3, 1, 1, 4), List(3, 1, 2, 1), List(3, 1, 2, 2), List(3, 1, 2, 3), List(3, 1, 2, 4), List(3, 1, 3, 1), List(3, 1, 3, 2), List(3, 1, 3, 3), List(3, 1, 3, 4), List(3, 1, 4, 1), List(3, 1, 4, 2), List(3, 1, 4, 3), List(3, 1, 4, 4), List(3, 2, 1, 1), List(3, 2, 1, 2), List(3, 2, 1, 3), List(3, 2, 1, 4), List(3, 2, 2, 1), List(3, 2, 2, 2), List(3, 2, 2, 3), List(3, 2, 2, 4), List(3, 2, 3, 1), List(3, 2, 3, 2), List(3, 2, 3, 3), List(3, 2, 3, 4), List(3, 2, 4, 1), List(3, 2, 4, 2), List(3, 2, 4, 3), List(3, 2, 4, 4), List(3, 3, 1, 1), List(3, 3, 1, 2), List(3, 3, 1, 3), List(3, 3, 1, 4), List(3, 3, 2, 1), List(3, 3, 2, 2), List(3, 3, 2, 3), List(3, 3, 2, 4), List(3, 3, 3, 1), List(3, 3, 3, 2), List(3, 3, 3, 3), List(3, 3, 3, 4), List(3, 3, 4, 1), List(3, 3, 4, 2), List(3, 3, 4, 3), List(3, 3, 4, 4), List(3, 4, 1, 1), List(3, 4, 1, 2), List(3, 4, 1, 3), List(3, 4, 1, 4), List(3, 4, 2, 1), List(3, 4, 2, 2), List(3, 4, 2, 3), List(3, 4, 2, 4), List(3, 4, 3, 1), List(3, 4, 3, 2), List(3, 4, 3, 3), List(3, 4, 3, 4), List(3, 4, 4, 1), List(3, 4, 4, 2), List(3, 4, 4, 3), List(3, 4, 4, 4), List(4, 1, 1, 1), List(4, 1, 1, 2), List(4, 1, 1, 3), List(4, 1, 1, 4), List(4, 1, 2, 1), List(4, 1, 2, 2), List(4, 1, 2, 3), List(4, 1, 2, 4), List(4, 1, 3, 1), List(4, 1, 3, 2), List(4, 1, 3, 3), List(4, 1, 3, 4), List(4, 1, 4, 1), List(4, 1, 4, 2), List(4, 1, 4, 3), List(4, 1, 4, 4), List(4, 2, 1, 1), List(4, 2, 1, 2), List(4, 2, 1, 3), List(4, 2, 1, 4), List(4, 2, 2, 1), List(4, 2, 2, 2), List(4, 2, 2, 3), List(4, 2, 2, 4), List(4, 2, 3, 1), List(4, 2, 3, 2), List(4, 2, 3, 3), List(4, 2, 3, 4), List(4, 2, 4, 1), List(4, 2, 4, 2), List(4, 2, 4, 3), List(4, 2, 4, 4), List(4, 3, 1, 1), List(4, 3, 1, 2), List(4, 3, 1, 3), List(4, 3, 1, 4), List(4, 3, 2, 1), List(4, 3, 2, 2), List(4, 3, 2, 3), List(4, 3, 2, 4), List(4, 3, 3, 1), List(4, 3, 3, 2), List(4, 3, 3, 3), List(4, 3, 3, 4), List(4, 3, 4, 1), List(4, 3, 4, 2), List(4, 3, 4, 3), List(4, 3, 4, 4), List(4, 4, 1, 1), List(4, 4, 1, 2), List(4, 4, 1, 3), List(4, 4, 1, 4), List(4, 4, 2, 1), List(4, 4, 2, 2), List(4, 4, 2, 3), List(4, 4, 2, 4), List(4, 4, 3, 1), List(4, 4, 3, 2), List(4, 4, 3, 3), List(4, 4, 3, 4), List(4, 4, 4, 1), List(4, 4, 4, 2), List(4, 4, 4, 3), List(4, 4, 4, 4)) List( List(3,1,4,2), List(2,4,1,3)) ) BEFORE AFTER adding filtering (isSafe function) 128
129. BEFORE AFTER adding filtering (isSafe function) 129
130. Let’s visualise how the filtering reduces the problem space 130
135. Candidate boards generated and tested: 60 (out of 256) 135
136. N = 4 2 solutions 136
137. N = 5 10 solutions 137
138. N = 6 4 solutions 138
139. N = 7 40 solutions 139
140. N = 8 92 solutions 140
141. 92 boards N = 5 N = 6 N = 4 N = 7 N = 8 40 boards 4 boards 10 boards 2 boards
142. queens n = placeQueens n where placeQueens 0 = [[]] placeQueens k = [queen:queens | queens <- placeQueens(k-1), queen <- [1..n], safe queen queens] safe queen queens = all safe (zipWithRows queens) where safe (r,c) = c /= col && not (onDiagonal col row c r) row = length queens col = queen onDiagonal row column otherRow otherColumn = abs (row - otherRow) == abs (column - otherColumn) zipWithRows queens = zip rowNumbers queens where rowCount = length queens rowNumbers = [rowCount-1,rowCount-2..0] def queens(n: Int): List[List[Int]] = def placeQueens(k: Int): List[List[Int]] = if k == 0 then List(List()) else for queens <- placeQueens(k - 1) queen <- 1 to n if safe(queen, queens) yield queen :: queens placeQueens(n) def onDiagonal(row: Int, column: Int, otherRow: Int, otherColumn: Int) = math.abs(row - otherRow) == math.abs(column - otherColumn) def safe(queen: Int, queens: List[Int]): Boolean = val (row, column) = (queens.length, queen) val safe: ((Int,Int)) => Boolean = (nextRow, nextColumn) => column != nextColumn && !onDiagonal(column, row, nextColumn, nextRow) zipWithRows(queens) forall safe def zipWithRows(queens: List[Int]): Iterable[(Int,Int)] = val rowCount = queens.length val rowNumbers = rowCount - 1 to 0 by -1 rowNumbers zip queens Recursive Algorithm 142
143. https://rosettacode.org/wiki/N-queens_problem#Haskell On the Rosetta Code site, I came across a Haskell N-Queens puzzle program which • does not use recursion • uses a function called foldM • it is succinct, but relies on comments to help understand how it works https://rosettacode.org/wiki/ 143
144. In the rest of this talk we shall • gain an understanding of the foldM function • see how it can be used to write an iterative solution to the puzzle 144
145. We are all very familiar with the 3 functions that are the bread, butter, and jam of Functional Programming 145
146. We are all very familiar with the 3 functions that are the bread, butter, and jam of Functional Programming map λ I am (of course) referring to the triad of map, filter and fold 146
147. map λ mapM λ Let’s gain an understanding of the foldM function by looking at the monadic variant of the triad 147
148. λ mapM 148
149. Generic functions An important benefit of abstracting out the concept of monads is the ability to define generic functions that can be used with any monad. … For example, a monadic version of the map function on list can be defined as follows: mapM :: Monad m => (a -> m b) -> [a] -> m [b] mapM f [] = return [] mapM f (x:xs) = do y <- f x ys <- mapM f xs return (y:ys) Note that mapM has the same type as map, except that the argument function and the function itself now have monadic return types. Graham Hutton @haskellhutt 149
150. map :: (a -> b) -> [a] -> [b] 150
151. mapM :: Monad m => (a -> m b) -> [a] -> m [b] mapM f [] = return [] mapM f (x:xs) = do y <- f x ys <- mapM f xs return (y:ys) map :: (a -> b) -> [a] -> [b] 151
152. import cats.Monad import cats.syntax.functor.* // map import cats.syntax.flatMap.* // flatMap import cats.syntax.applicative.* // pure def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => for b <- f(a) bs <- mapM(as)(f) yield b::bs mapM :: Monad m => (a -> m b) -> [a] -> m [b] mapM f [] = return [] mapM f (x:xs) = do y <- f x ys <- mapM f xs return (y:ys) Cats map :: (a -> b) -> [a] -> [b] 152
153. mapM ? ? 153
154. Paul Chiusano Runar Bjarnason @pchiusano @runarorama FP in Scala There turns out to be a startling number of operations that can be defined in the most general possible way in terms of sequence and/or traverse 154
155. A quick refresher on the traverse function 155
156. final def traverse[A, B, M <: (IterabelOnce)] (in: M[A]) (fn: A => Future[B]) (implicit bf: BuildFrom[M[A], B, M[B]], executor: ExecutionContext) : Future[M[B]] Asynchronously and non-blockingly transforms a IterableOnce[A] into a Future[IterableOnce[B]] using the provided function A => Future[B]. This is useful for performing a parallel map. For example, to apply a function to all items of a list in parallel. final def sequence[A, CC <: (IterabelOnce), To] (in: CC[Future[A]]) (implicit bf: BuildFrom[CC[Future[A]], A, To], executor: ExecutionContext) : Future[To] Simple version of Future.traverse. 156 While there is a traverse function in Scala’s standard library, it is specific to Future, and IterableOnce.
157. scala> import scala.concurrent.Future | import concurrent.ExecutionContext.Implicits.global 157
158. scala> import scala.concurrent.Future | import concurrent.ExecutionContext.Implicits.global // list of integers scala> val listOfInts = List(1,2,3) val listOfInts: List[Int] = List(1, 2, 3) 158
159. scala> import scala.concurrent.Future | import concurrent.ExecutionContext.Implicits.global // list of integers scala> val listOfInts = List(1,2,3) val listOfInts: List[Int] = List(1, 2, 3) // list of future integers scala> val listOfFutureInts = listOfInts.map{ n => Future(n*10) } 159
160. scala> import scala.concurrent.Future | import concurrent.ExecutionContext.Implicits.global // list of integers scala> val listOfInts = List(1,2,3) val listOfInts: List[Int] = List(1, 2, 3) // list of future integers scala> val listOfFutureInts = listOfInts.map{ n => Future(n*10) } val listOfFutureInts: List[Future[Int]] = List(Future(Success(10)), Future(Success(20)), Future(Success(30))) 160
161. scala> import scala.concurrent.Future | import concurrent.ExecutionContext.Implicits.global // list of integers scala> val listOfInts = List(1,2,3) val listOfInts: List[Int] = List(1, 2, 3) // list of future integers scala> val listOfFutureInts = listOfInts.map{ n => Future(n*10) } val listOfFutureInts: List[Future[Int]] = List(Future(Success(10)), Future(Success(20)), Future(Success(30))) // turn List[Future[Int]] into Future[List[Int]] // i.e. it turns the nesting of Future within List inside out scala> val futureListOfInts = Future.sequence(listOfFutureInts) 161
162. scala> import scala.concurrent.Future | import concurrent.ExecutionContext.Implicits.global // list of integers scala> val listOfInts = List(1,2,3) val listOfInts: List[Int] = List(1, 2, 3) // list of future integers scala> val listOfFutureInts = listOfInts.map{ n => Future(n*10) } val listOfFutureInts: List[Future[Int]] = List(Future(Success(10)), Future(Success(20)), Future(Success(30))) // turn List[Future[Int]] into Future[List[Int]] // i.e. it turns the nesting of Future within List inside out scala> val futureListOfInts = Future.sequence(listOfFutureInts) val futureListOfInts: Future[List[Int]] = Future(Success(List(10, 20, 30))) 162
163. scala> import scala.concurrent.Future | import concurrent.ExecutionContext.Implicits.global // list of integers scala> val listOfInts = List(1,2,3) val listOfInts: List[Int] = List(1, 2, 3) // list of future integers scala> val listOfFutureInts = listOfInts.map{ n => Future(n*10) } val listOfFutureInts: List[Future[Int]] = List(Future(Success(10)), Future(Success(20)), Future(Success(30))) // turn List[Future[Int]] into Future[List[Int]] // i.e. it turns the nesting of Future within List inside out scala> val futureListOfInts = Future.sequence(listOfFutureInts) val futureListOfInts: Future[List[Int]] = Future(Success(List(10, 20, 30))) turn inside out 163
164. scala> import scala.concurrent.Future | import concurrent.ExecutionContext.Implicits.global // list of integers scala> val listOfInts = List(1,2,3) val listOfInts: List[Int] = List(1, 2, 3) // list of future integers scala> val listOfFutureInts = listOfInts.map{ n => Future(n*10) } val listOfFutureInts: List[Future[Int]] = List(Future(Success(10)), Future(Success(20)), Future(Success(30))) // turn List[Future[Int]] into Future[List[Int]] // i.e. it turns the nesting of Future within List inside out scala> val futureListOfInts = Future.sequence(listOfFutureInts) val futureListOfInts: Future[List[Int]] = Future(Success(List(10, 20, 30))) // first map List[Int] to List[Future[Int]] // and then turn List[Future[Int]] into Future[List[Int]] scala> val futureListOfInts = Future.traverse(listOfInts) { n => Future(n*10) } 164
165. scala> import scala.concurrent.Future | import concurrent.ExecutionContext.Implicits.global // list of integers scala> val listOfInts = List(1,2,3) val listOfInts: List[Int] = List(1, 2, 3) // list of future integers scala> val listOfFutureInts = listOfInts.map{ n => Future(n*10) } val listOfFutureInts: List[Future[Int]] = List(Future(Success(10)), Future(Success(20)), Future(Success(30))) // turn List[Future[Int]] into Future[List[Int]] // i.e. it turns the nesting of Future within List inside out scala> val futureListOfInts = Future.sequence(listOfFutureInts) val futureListOfInts: Future[List[Int]] = Future(Success(List(10, 20, 30))) // first map List[Int] to List[Future[Int]] // and then turn List[Future[Int]] into Future[List[Int]] scala> val futureListOfInts = Future.traverse(listOfInts) { n => Future(n*10) } val futureListOfInts: Future[List[Int]] = Future(Success(List(10, 20, 30))) 165
166. scala> import scala.concurrent.Future | import concurrent.ExecutionContext.Implicits.global // list of integers scala> val listOfInts = List(1,2,3) val listOfInts: List[Int] = List(1, 2, 3) // list of future integers scala> val listOfFutureInts = listOfInts.map{ n => Future(n*10) } val listOfFutureInts: List[Future[Int]] = List(Future(Success(10)), Future(Success(20)), Future(Success(30))) // turn List[Future[Int]] into Future[List[Int]] // i.e. it turns the nesting of Future within List inside out scala> val futureListOfInts = Future.sequence(listOfFutureInts) val futureListOfInts: Future[List[Int]] = Future(Success(List(10, 20, 30))) // first map List[Int] to List[Future[Int]] // and then turn List[Future[Int]] into Future[List[Int]] scala> val futureListOfInts = Future.traverse(listOfInts) { n => Future(n*10) } val futureListOfInts: Future[List[Int]] = Future(Success(List(10, 20, 30))) same result 166
167. That was the quick refresher on the traverse function 167
168. class (Functor t, Foldable t) => Traversable t where traverse :: Applicative f => (a -> f b) -> t a -> f (t b) 168
169. mapM :: Monad m => (a -> m b) -> [a] -> m [b] map :: (a -> b) -> [a] -> [b] class (Functor t, Foldable t) => Traversable t where traverse :: Applicative f => (a -> f b) -> t a -> f (t b) 169
170. mapM :: Monad m => (a -> m b) -> [a] -> m [b] map :: (a -> b) -> [a] -> [b] class (Functor t, Foldable t) => Traversable t where traverse :: Applicative f => (a -> f b) -> t a -> f (t b) 170
171. mapM :: Monad m => (a -> m b) -> [a] -> m [b] map :: (a -> b) -> [a] -> [b] class (Functor t, Foldable t) => Traversable t where traverse :: Applicative f => (a -> f b) -> t a -> f (t b) 171
172. mapM :: Monad m => (a -> m b) -> [a] -> m [b] map :: (a -> b) -> [a] -> [b] class (Functor t, Foldable t) => Traversable t where traverse :: Applicative f => (a -> f b) -> t a -> f (t b) … mapM :: Monad m => (a -> m b) -> t a -> m (t b) mapM = traverse 172
173. /** * Traverse, also known as Traversable. * * Traversal over a structure with an effect. * * Traversing with the [[cats.Id]] effect is equivalent to [[cats.Functor]]#map. * Traversing with the [[cats.data.Const]] effect where the first type parameter has * a [[cats.Monoid]] instance is equivalent to [[cats.Foldable]]#fold. * * See: [[https://www.cs.ox.ac.uk/jeremy.gibbons/publications/iterator.pdf The Essence of the Iterator Pattern]] */ trait Traverse[F[_]] extends Functor[F] with Foldable[F] with UnorderedTraverse[F] { self => /** * Given a function which returns a G effect, thread this effect * through the running of this function on all the values in F, * returning an F[B] in a G context. def traverse[G[_]: Applicative, A, B](fa: F[A])(f: A => G[B]): G[F[B]] class (Functor t, Foldable t) => Traversable t where traverse :: Applicative f => (a -> f b) -> t a -> f (t b) … mapM :: Monad m => (a -> m b) -> t a -> m (t b) mapM = traverse mapM :: Monad m => (a -> m b) -> [a] -> m [b] map :: (a -> b) -> [a] -> [b] 173
174. import cats.{Applicative, Monad} import cats.syntax.traverse.* import cats.Traverse extension[A, B, M[_] : Monad] (as: List[A]) def mapM(f: A => M[B]): M[List[B]] = as.traverse(f) def mapM [A, B, M[_]: Monad](as: List[A])(f: A => M[B]): M[List[B]] mapM :: Monad m => (a -> m b) -> [a] -> m [b] 174
175. trait Traverse[F[_]] extends Functor[F] with Foldable[F] { … def traverse[G[_],A,B](fa: F[A])(f: A => G[B])(implicit G: Applicative[G]): G[F[B]] … } 🤯 175 I am not really surprised that mapM is just traverse. As seen in the red book…
176. G = Id Monad trait Traverse[F[_]] extends Functor[F] with Foldable[F] { … def map[A,B](fa: F[A])(f: A => B): F[B] = traverse… def traverse[G[_],A,B](fa: F[A])(f: A => G[B])(implicit G: Applicative[G]): G[F[B]] … } 🤯 176 … traverse is so general that it can be used to define map…
177. G = Id Monad G = Applicative Monoid trait Traverse[F[_]] extends Functor[F] with Foldable[F] { … def map[A,B](fa: F[A])(f: A => B): F[B] = traverse… def foldMap[A,M](as: F[A])(f: A => M)(mb: Monoid[M]): M = traverse… def traverse[G[_],A,B](fa: F[A])(f: A => G[B])(implicit G: Applicative[G]): G[F[B]] … } 🤯 177 … and foldMap
178. A quick mention of the Symmetry that exists in the interrelation of flatMap/foldMap/traverse and flatten/fold/sequence 178
179. def flatMap[A,B](ma: F[A])(f: A ⇒ F[B]): F[B] = flatten(map(ma)(f)) 179
180. def flatMap[A,B](ma: F[A])(f: A ⇒ F[B]): F[B] = flatten(map(ma)(f)) def flatten[A](mma: F[F[A]]): F[A] = flatMap(mma)(x ⇒ x) 180
181. def flatMap[A,B](ma: F[A])(f: A ⇒ F[B]): F[B] = flatten(map(ma)(f)) def foldMap[A,B:Monoid](fa: F[A])(f: A ⇒ B): B = fold(map(fa)(f)) def flatten[A](mma: F[F[A]]): F[A] = flatMap(mma)(x ⇒ x) 181
182. def flatMap[A,B](ma: F[A])(f: A ⇒ F[B]): F[B] = flatten(map(ma)(f)) def foldMap[A,B:Monoid](fa: F[A])(f: A ⇒ B): B = fold(map(fa)(f)) def flatten[A](mma: F[F[A]]): F[A] = flatMap(mma)(x ⇒ x) def fold[A:Monoid](fa: F[A]): A = foldMap(fa)(x ⇒ x) 182
183. def flatMap[A,B](ma: F[A])(f: A ⇒ F[B]): F[B] = flatten(map(ma)(f)) def foldMap[A,B:Monoid](fa: F[A])(f: A ⇒ B): B = fold(map(fa)(f)) def traverse[M[_]:Applicative,A,B](fa: F[A])(f: A ⇒ M[B]): M[F[B]] = sequence(map(fa)(f)) def flatten[A](mma: F[F[A]]): F[A] = flatMap(mma)(x ⇒ x) def fold[A:Monoid](fa: F[A]): A = foldMap(fa)(x ⇒ x) 183
184. def flatMap[A,B](ma: F[A])(f: A ⇒ F[B]): F[B] = flatten(map(ma)(f)) def foldMap[A,B:Monoid](fa: F[A])(f: A ⇒ B): B = fold(map(fa)(f)) def traverse[M[_]:Applicative,A,B](fa: F[A])(f: A ⇒ M[B]): M[F[B]] = sequence(map(fa)(f)) def flatten[A](mma: F[F[A]]): F[A] = flatMap(mma)(x ⇒ x) def fold[A:Monoid](fa: F[A]): A = foldMap(fa)(x ⇒ x) def sequence[M[_]:Applicative,A](fma: F[M[A]]): M[F[A]] = traverse(fma)(x ⇒ x) 184
185. def flatMap[A,B](ma: F[A])(f: A ⇒ F[B]): F[B] = flatten(map(ma)(f)) def foldMap[A,B:Monoid](fa: F[A])(f: A ⇒ B): B = fold(map(fa)(f)) def traverse[M[_]:Applicative,A,B](fa: F[A])(f: A ⇒ M[B]): M[F[B]] = sequence(map(fa)(f)) def flatten[A](mma: F[F[A]]): F[A] = flatMap(mma)(x ⇒ x) def fold[A:Monoid](fa: F[A]): A = foldMap(fa)(x ⇒ x) def sequence[M[_]:Applicative,A](fma: F[M[A]]): M[F[A]] = traverse(fma)(x ⇒ x) Symmetry in the interrelation of flatMap/foldMap/traverse and flatten/fold/sequence 185
186. Examples of mapM usage Example Monadic Context How the result of mapM is affected 1 2 3 186
187. Examples of mapM usage Example Monadic Context How the result of mapM is affected 1 Option There may or may not be a result. 2 3 187
188. To illustrate how it might be used, consider a function that converts a digit character to its numeric value, provided that the character is indeed a digit: conv :: Char -> Maybe Int conv c | isDigit c = Just (digitToInt c) | otherwise = Nothing (The functions isDigit and digitToInt are provided in Data.Char.) Then applying mapM to the conv function gives a means of converting a string of digits into the corresponding list of numeric values, which succeeds if every character in the string is a digit, and fails otherwise: > mapM conv "1234" Just [1,2,3,4] > mapM conv "123a" Nothing Graham Hutton @haskellhutt def convert(c: Char): Option[Int] = Option.when(c.isDigit)(c.asDigit) assert("12a4".toList.mapM(convert) == None) assert("1234".toList.mapM(convert) == Some(List(1, 2, 3, 4))) def mapM [A, B, M[_]: Monad](as: List[A])(f: A => M[B]): M[List[B]] M = Option mapM :: Monad m => (a -> m b) -> [a] -> m [b] 188
189. Let’s look at three examples of mapM usage: Example Monadic Context How the result of mapM is affected 1 Option There may or may not be a result. 2 3 189
190. Let’s look at three examples of mapM usage: Example Monadic Context How the result of mapM is affected 1 Option There may or may not be a result. 2 List There may be zero, one, or more results. 3 190
191. • X is combined first with 1, and then with 2, and the results are paired X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } 191
192. • X is combined first with 1, and then with 2, and the results are paired List("X", "Y").map{ c => List(c + "1", c + "2") } X Y 1 2 192
193. List(List("X1","X2")) • X is combined first with 1, and then with 2, and the results are paired List("X", "Y").map{ c => List(c + "1", c + "2") } X Y 1 2 193
194. List(List("X1","X2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } 194
195. List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } 195
196. List("X", "Y").mapM{ c => List( c + "1", c + "2") } List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired • X is combined with 1 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 X Y 1 2 X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => for b <- f(a) bs <- mapM(as)(f) yield b::bs 196 M = List
197. List("X", "Y").mapM{ c => List( c + "1", c + "2") } List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired • X is combined with 1 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 X Y 1 2 X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => // "X"::List("Y") for b <- f(a) bs <- mapM(as)(f) yield b::bs 197
198. List("X", "Y").mapM{ c => List( c + "1", c + "2") } List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired • X is combined with 1 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 X Y 1 2 X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => // "X"::List("Y") for b <- f(a) // List("X1","X2")) bs <- mapM(as)(f) yield b::bs 198
199. List("X", "Y").mapM{ c => List( c + "1", c + "2") } List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired • X is combined with 1 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 X Y 1 2 X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => // "X"::List("Y") for b <- f(a) // List("X1","X2")) bs <- mapM(as)(f) yield b::bs 199
200. List("X", "Y").mapM{ c => List( c + "1", c + "2") } List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired • X is combined with 1 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 X Y 1 2 X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => // "X"::List("Y") for b <- f(a) // List("X1","X2")) bs <- mapM(as)(f) // ?? yield b::bs 200
201. List("X", "Y").mapM{ c => List( c + "1", c + "2") } List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired • X is combined with 1 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 X Y 1 2 X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => // "Y"::List() for b <- f(a) bs <- mapM(as)(f) yield b::bs 201 à recursive call for List("Y")
202. List("X", "Y").mapM{ c => List( c + "1", c + "2") } List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired • X is combined with 1 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 X Y 1 2 X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => // "Y"::List() for b <- f(a) // List("Y1","Y2") bs <- mapM(as)(f) yield b::bs 202 à recursive call for List("Y")
203. List("X", "Y").mapM{ c => List( c + "1", c + "2") } List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired • X is combined with 1 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 X Y 1 2 X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => // "Y"::List() for b <- f(a) // List("Y1","Y2") bs <- mapM(as)(f) yield b::bs 203 à recursive call for List("Y")
204. List("X", "Y").mapM{ c => List( c + "1", c + "2") } List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired • X is combined with 1 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 X Y 1 2 X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => // "Y"::List() for b <- f(a) // List("Y1","Y2") bs <- mapM(as)(f) // ?? yield b::bs 204 à recursive call for List("Y")
205. List("X", "Y").mapM{ c => List( c + "1", c + "2") } List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired • X is combined with 1 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 X Y 1 2 X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure // List(List()) case a::as => for b <- f(a) bs <- mapM(as)(f) yield b::bs 205 à recursive call for List("Y") à recursive call for List()
206. List("X", "Y").mapM{ c => List( c + "1", c + "2") } List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired • X is combined with 1 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 X Y 1 2 X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => // "Y"::List() for b <- f(a) // List("Y1","Y2") bs <- mapM(as)(f) // List(List()) yield b::bs 206 à recursive call for List("Y") à recursive call for List()
207. List("X", "Y").mapM{ c => List( c + "1", c + "2") } List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired • X is combined with 1 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 X Y 1 2 X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => // "Y"::List() for b <- f(a) // List("Y1","Y2") bs <- mapM(as)(f) // List(List()) yield b::bs 207 à recursive call for List("Y") à recursive call for List()
208. List("X", "Y").mapM{ c => List( c + "1", c + "2") } List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired • X is combined with 1 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 X Y 1 2 X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => // "Y"::List() for b <- f(a) // List("Y1","Y2") bs <- mapM(as)(f) // List(List()) yield b::bs // "Y1"::List() 208 à recursive call for List("Y") à recursive call for List() List("Y1")
209. List("X", "Y").mapM{ c => List( c + "1", c + "2") } List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired • X is combined with 1 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 X Y 1 2 X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => // "Y"::List() for b <- f(a) // List("Y1","Y2") bs <- mapM(as)(f) // ?? yield b::bs 209 à recursive call for List("Y") à recursive call for List() List("Y1")
210. List("X", "Y").mapM{ c => List( c + "1", c + "2") } List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired • X is combined with 1 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 X Y 1 2 X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure // List(List()) case a::as => for b <- f(a) bs <- mapM(as)(f) yield b::bs 210 à recursive call for List("Y") à recursive call for List() à recursive call for List() List("Y1")
211. List("X", "Y").mapM{ c => List( c + "1", c + "2") } List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired • X is combined with 1 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 X Y 1 2 X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => // "Y"::List() for b <- f(a) // List("Y1","Y2") bs <- mapM(as)(f) // List(List()) yield b::bs 211 à recursive call for List("Y") à recursive call for List() à recursive call for List() List("Y1")
212. List("X", "Y").mapM{ c => List( c + "1", c + "2") } List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired • X is combined with 1 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 X Y 1 2 X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => // "Y"::List() for b <- f(a) // List("Y1","Y2") bs <- mapM(as)(f) // List(List()) yield b::bs 212 à recursive call for List("Y") à recursive call for List() à recursive call for List() List("Y1")
213. List("X", "Y").mapM{ c => List( c + "1", c + "2") } List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired • X is combined with 1 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 X Y 1 2 X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => // "Y"::List() for b <- f(a) // List("Y1","Y2") bs <- mapM(as)(f) // List(List()) yield b::bs // "Y2"::List() 213 à recursive call for List("Y") à recursive call for List() à recursive call for List() List("Y1") List("Y2")
214. List("X", "Y").mapM{ c => List( c + "1", c + "2") } List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired • X is combined with 1 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 X Y 1 2 X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => // "X"::List("Y") for b <- f(a) // List("X1","X2") bs <- mapM(as)(f) // List(List("Y1"),List("Y2")) yield b::bs 214 M = List à recursive call for List("Y") à recursive call for List() à recursive call for List()
215. List("X", "Y").mapM{ c => List( c + "1", c + "2") } List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired • X is combined with 1 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 X Y 1 2 X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => // "X"::List("Y") for b <- f(a) // List("X1","X2") bs <- mapM(as)(f) // List(List("Y1"),List("Y2")) yield b::bs 215 M = List à recursive call for List("Y") à recursive call for List() à recursive call for List()
216. List("X", "Y").mapM{ c => List( c + "1", c + "2") } List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired X Y 1 2 X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => // "X"::List("Y") for b <- f(a) // List("X1","X2") bs <- mapM(as)(f) // List(List("Y1"),List("Y2")) yield b::bs // List("X1", "Y1") 216 à recursive call for List("Y") à recursive call for List() à recursive call for List() List(List("X1","Y1")) • X is combined with 1 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2
217. List("X", "Y").mapM{ c => List( c + "1", c + "2") } List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired List(List("X1","Y1")) • X is combined with 1 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 X Y 1 2 X Y 1 2 X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => // "X"::List("Y") for b <- f(a) // List("X1","X2") bs <- mapM(as)(f) // List(List("Y1"),List("Y2")) yield b::bs 217
218. List("X", "Y").mapM{ c => List( c + "1", c + "2") } List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired List(List("X1","Y1")) • X is combined with 1 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 X Y 1 2 X Y 1 2 X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => // "X"::List("Y") for b <- f(a) // List("X1","X2") bs <- mapM(as)(f) // List(List("Y1"),List("Y2")) yield b::bs 218
219. List("X", "Y").mapM{ c => List( c + "1", c + "2") } List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired List(List("X1","Y1"), List("X1","Y2")) • X is combined with 1 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 X Y 1 2 X Y 1 2 X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => // "X"::List("Y") for b <- f(a) // List("X1","X2") bs <- mapM(as)(f) // List(List("Y1"),List("Y2")) yield b::bs // List("X1","Y2") 219
220. List("X", "Y").mapM{ c => List( c + "1", c + "2") } List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired List(List("X1","Y1"), List("X1","Y2")) • X is combined with 1 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 • X is combined with 2 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 X Y 1 2 X Y 1 2 X Y 1 2 X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => // "X"::List("Y") for b <- f(a) // List("X1","X2") bs <- mapM(as)(f) // List(List("Y1"),List("Y2")) yield b::bs 220
221. List("X", "Y").mapM{ c => List( c + "1", c + "2") } List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired List(List("X1","Y1"), List("X1","Y2")) • X is combined with 1 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 • X is combined with 2 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 X Y 1 2 X Y 1 2 X Y 1 2 X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => // "X"::List("Y") for b <- f(a) // List("X1","X2") bs <- mapM(as)(f) // List(List("Y1"),List("Y2")) yield b::bs 221
222. List("X", "Y").mapM{ c => List( c + "1", c + "2") } List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired List(List("X1","Y1"), List("X1","Y2"), List("X2","Y1")) • X is combined with 1 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 • X is combined with 2 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 X Y 1 2 X Y 1 2 X Y 1 2 X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => // "X"::List("Y") for b <- f(a) // List("X1","X2") bs <- mapM(as)(f) // List(List("Y1"),List("Y2")) yield b::bs // List("X2","Y1") 222
223. List("X", "Y").mapM{ c => List( c + "1", c + "2") } List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired List(List("X1","Y1"), List("X1","Y2"), List("X2","Y1")) • X is combined with 1 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 • X is combined with 2 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 X Y 1 2 X Y 1 2 X Y 1 2 X Y 1 2 X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => // "X"::List("Y") for b <- f(a) // List("X1","X2") bs <- mapM(as)(f) // List(List("Y1"),List("Y2")) yield b::bs 223
224. List("X", "Y").mapM{ c => List( c + "1", c + "2") } List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired List(List("X1","Y1"), List("X1","Y2"), List("X2","Y1")) • X is combined with 1 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 • X is combined with 2 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 X Y 1 2 X Y 1 2 X Y 1 2 X Y 1 2 X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => // "X"::List("Y") for b <- f(a) // List("X1","X2") bs <- mapM(as)(f) // List(List("Y1"),List("Y2")) yield b::bs 224
225. List("X", "Y").mapM{ c => List( c + "1", c + "2") } List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired List(List("X1","Y1"), List("X1","Y2"), List("X2","Y1"), List("X2","Y2")) • X is combined with 1 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 • X is combined with 2 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 X Y 1 2 X Y 1 2 X Y 1 2 X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => // "X"::List("Y") for b <- f(a) // List("X1","X2") bs <- mapM(as)(f) // List(List("Y1"),List("Y2")) yield b::bs // List("X2","Y2") 225 X Y 1 2
226. List("X", "Y").mapM{ c => List( c + "1", c + "2") } List(List("X1","X2"), List("Y1","Y2")) • X is combined first with 1, and then with 2, and the results are paired • Y is combined first with 1, and then with 2, and the results are paired List(List("X1","Y1"), List("X1","Y2"), List("X2","Y1"), List("X2","Y2")) • X is combined with 1 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 • X is combined with 2 and paired, first with the result of combining Y with 1, and then with the result of combining Y with 2 X Y 1 2 X Y 1 2 X Y 1 2 X Y 1 2 X Y 1 2 List("X", "Y").map{ c => List(c + "1", c + "2") } def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => // "X"::List("Y") for b <- f(a) // List("X1","X2") bs <- mapM(as)(f) // List(List("Y1"),List("Y2")) yield b::bs // List("X2","Y2") 226 X Y 1 2
227. Examples of mapM usage Example Monadic Context How the result of mapM is affected 1 Option There may or may not be a result. 2 List There may be zero, one, or more results. 3 227
228. Examples of mapM usage Example Monadic Context How the result of mapM is affected 1 Option There may or may not be a result. 2 List There may be zero, one, or more results. 3 IO The result suspends any side effects. 228
229. import cats.effect.IO import cats.effect.unsafe.implicits.global import scala.io.StdIn.readLine def getNumber(msg: String): IO[Int] = (IO.print(msg) *> IO.readLine).map(_.toIntOption.getOrElse(0)) 229 side effects suspended in pure value
230. import cats.effect.IO import cats.effect.unsafe.implicits.global import scala.io.StdIn.readLine def getNumber(msg: String): IO[Int] = (IO.print(msg) *> IO.readLine).map(_.toIntOption.getOrElse(0)) val messages = List("Enter a number: ", "Enter another: ") 230
231. import cats.effect.IO import cats.effect.unsafe.implicits.global import scala.io.StdIn.readLine def getNumber(msg: String): IO[Int] = (IO.print(msg) *> IO.readLine).map(_.toIntOption.getOrElse(0)) val messages = List("Enter a number: ", "Enter another: ") val getNumbers: IO[List[Int]] = messages.mapM{ getNumber } 231 side effects suspended in pure value
232. import cats.effect.IO import cats.effect.unsafe.implicits.global import scala.io.StdIn.readLine def getNumber(msg: String): IO[Int] = (IO.print(msg) *> IO.readLine).map(_.toIntOption.getOrElse(0)) val messages = List("Enter a number: ", "Enter another: ") val getNumbers: IO[List[Int]] = messages.mapM{ getNumber } val numbers: List[Int] = getNumbers.unsafeRunSync() Enter a number: 3 Enter another: 2 232 side effects occur
233. import cats.effect.IO import cats.effect.unsafe.implicits.global import scala.io.StdIn.readLine def getNumber(msg: String): IO[Int] = (IO.print(msg) *> IO.readLine).map(_.toIntOption.getOrElse(0)) val messages = List("Enter a number: ", "Enter another: ") val getNumbers: IO[List[Int]] = messages.mapM{ getNumber } val numbers: List[Int] = getNumbers.unsafeRunSync() println(s"The two numbers add up to ${numbers.sum}") Enter a number: 3 Enter another: 2 The two numbers add up to 5 233
234. import cats.effect.IO import cats.effect.unsafe.implicits.global import scala.io.StdIn.readLine def getNumber(msg: String): IO[Int] = (IO.print(msg) *> IO.readLine).map(_.toIntOption.getOrElse(0)) val messages = List("Enter a number: ", "Enter another: ") val getNumbers: IO[List[Int]] = messages.mapM{ getNumber } val numbers: List[Int] = getNumbers.unsafeRunSync() println(s"The two numbers add up to ${numbers.sum}") if getNumber cannot parse an input, it returns 0 234 Enter a number: 3 Enter another: a The two numbers add up to 3
235. import cats.effect.IO import cats.effect.unsafe.implicits.global import scala.io.StdIn.readLine def getNumber(msg: String): IO[Int] = (IO.print(msg) *> IO.readLine).map(_.toIntOption.getOrElse(0)) val messages = List("Enter a number: ", "Enter another: ") val getNumbers: IO[List[Int]] = messages.mapM{ getNumber } val numbers: List[Int] = getNumbers.unsafeRunSync() println(s"The two numbers add up to ${numbers.sum}") 235 If IO.readLine hangs waiting for input, so does the whole program Enter a number: ⏳…
236. import cats.effect.IO import cats.effect.unsafe.implicits.global import scala.io.StdIn.readLine def getNumber(msg: String): IO[Int] = (IO.print(msg) *> IO.readLine).map(_.toIntOption.getOrElse(0)) val messages = List("Enter a number: ", "Enter another: ") val getNumbers: IO[List[Int]] = messages.mapM{ getNumber } val numbers: List[Int] = getNumbers.unsafeRunSync() println(s"The two numbers add up to ${numbers.sum}") 236 If IO.readLine throws an exception, so does the whole program Enter a number: ⚡⚡⚡
237. mapM λ 237
238. mapM λ 238
239. mapM λ 239
240. A monadic version of the filter function on lists is defined by generalizing its type and definition in a similar manner to mapM: filterM :: Monad m => (a -> m Bool) -> [a] -> m [a] filterM p [] = return [] filterM p (x:xs) = do b <- p x ys <- filterM p xs return (if b then x:ys else ys) Graham Hutton @haskellhutt 240
241. import cats.Monad import cats.syntax.functor.* // map import cats.syntax.flatMap.* // flatMap import cats.syntax.applicative.* // pure def filterM[A, M[_]: Monad](l: List[A])(f: A => M[Boolean]): M[List[B]] = l match case Nil => Nil.pure case a::as => for retainingA <- p(a) retainedAs <- filterM(as)(p) yield if retainingA then a::retainedAs else retainedAs filterM :: Monad m => (a -> m Bool) -> [a] -> m [a] filterM p [] = return [] filterM p (x:xs) = do b <- p x ys <- filterM p xs return (if b then x:ys else ys) Cats filter :: (a -> Bool) -> [a] -> [a] 241
242. import cats.Monad import cats.syntax.functor.* // map import cats.syntax.flatMap.* // flatMap import cats.syntax.applicative.* // pure def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => for b <- f(a) bs <- mapM(as)(f) yield b::bs Cats import cats.Monad import cats.syntax.functor.* // map import cats.syntax.flatMap.* // flatMap import cats.syntax.applicative.* // pure def filterM[A, M[_]: Monad](l: List[A])(p: A => M[Boolean]): M[List[B]] = l match case Nil => Nil.pure case a::as => for retainingA <- p(a) retainedAs <- filterM(as)(p) yield if retainingA then a::retainedAs else retainedAs mapM filterM 242
243. import cats.Monad import cats.syntax.functor.* // map import cats.syntax.flatMap.* // flatMap import cats.syntax.applicative.* // pure def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => for b <- f(a) bs <- mapM(as)(f) yield b::bs Cats import cats.Monad import cats.syntax.functor.* // map import cats.syntax.flatMap.* // flatMap import cats.syntax.applicative.* // pure def filterM[A, M[_]: Monad](l: List[A])(p: A => M[Boolean]): M[List[B]] = l match case Nil => Nil.pure case a::as => for retainingA <- p(a) retainedAs <- filterM(as)(p) yield if retainingA then a::retainedAs else retainedAs mapM filterM 243
244. import cats.Monad import cats.syntax.functor.* // map import cats.syntax.flatMap.* // flatMap import cats.syntax.applicative.* // pure def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => for b <- f(a) bs <- mapM(as)(f) yield b::bs Cats import cats.Monad import cats.syntax.functor.* // map import cats.syntax.flatMap.* // flatMap import cats.syntax.applicative.* // pure def filterM[A, M[_]: Monad](l: List[A])(p: A => M[Boolean]): M[List[B]] = l match case Nil => Nil.pure case a::as => for retainingA <- p(a) retainedAs <- filterM(as)(p) yield if retainingA then a::retainedAs else retainedAs mapM filterM 244
245. import cats.Monad import cats.syntax.functor.* // map import cats.syntax.flatMap.* // flatMap import cats.syntax.applicative.* // pure def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => for b <- f(a) bs <- mapM(as)(f) yield b::bs Cats import cats.Monad import cats.syntax.functor.* // map import cats.syntax.flatMap.* // flatMap import cats.syntax.applicative.* // pure def filterM[A, M[_]: Monad](l: List[A])(p: A => M[Boolean]): M[List[B]] = l match case Nil => Nil.pure case a::as => for retainingA <- p(a) retainedAs <- filterM(as)(p) yield if retainingA then a::retainedAs else retainedAs mapM filterM 245
246. import cats.Monad import cats.syntax.functor.* // map import cats.syntax.flatMap.* // flatMap import cats.syntax.applicative.* // pure def mapM[A, B, M[_]: Monad](l: List[A])(f: A => M[B]): M[List[B]] = l match case Nil => Nil.pure case a::as => for b <- f(a) bs <- mapM(as)(f) yield b::bs Cats import cats.Monad import cats.syntax.functor.* // map import cats.syntax.flatMap.* // flatMap import cats.syntax.applicative.* // pure def filterM[A, M[_]: Monad](l: List[A])(p: A => M[Boolean]): M[List[B]] = l match case Nil => Nil.pure case a::as => for retainingA <- p(a) retainedAs <- filterM(as)(p) yield if retainingA then a::retainedAs else retainedAs mapM filterM 246
247. filterM ? 247
248. https://typelevel.org/cats/api/cats/TraverseFilter.html 248
249. import cats.Monad import cats.syntax.traverseFilter.* extension[A, M[_]: Monad](as: List[A]) def filterM(f: A => M[Boolean]): M[List[A]] = as.filterA(f) def filterM [A, M[_]: Monad](as: List[A])(f: A => M[Boolean]): M[List[A]] filterM :: Monad m => (a -> m Bool) -> [a] -> m [a] 249
250. Examples of filterM usage Example Monadic Context 1 2 250
251. Examples of filterM usage Example Monadic Context 1 Option 2 251
252. conv :: Char -> Maybe Int conv c | isDigit c = Just (digitToInt c) | otherwise = Nothing > mapM conv "1234" Just [1,2,3,4] > mapM conv "123a" Nothing def convert(c: Char): Option[Int] = Option.when(c.isDigit)(c.asDigit) assert( "1234".toList.mapM(convert) == Some(List(1, 2, 3, 4)) ) assert( "1234a".toList.mapM(convert) == None ) 252 conv function returns Int in an Option monadic context
253. conv :: Char -> Maybe Int conv c | isDigit c = Just (digitToInt c) | otherwise = Nothing > mapM conv "1234" Just [1,2,3,4] > mapM conv "123a" Nothing maybeIsEven :: Char -> Maybe Bool maybeIsEven c | isDigit c = Just (even (digitToInt c)) | otherwise = Nothing > filterM maybeIsEven "1234" Just [2,4] > mapM maybeIsEven "123a" Nothing def conv(c: Char): Option[Int] = Option.when(c.isDigit)(c.asDigit) assert( "12a4".toList.mapM(conv) == None ) assert( "1234".toList.mapM(conv) == Some(List(1, 2, 3, 4)) ) def maybeIsEven(c: Char): Option[Boolean] = Option.when(c.isDigit)(c.asDigit % 2 == 0) assert( "12a4".toList.filterM(maybeIsEven) == None ) assert( "1234".toList.filterM(maybeIsEven) == Some(List('2','4’)) ) 253 conv function returns Int in an Option monadic context maybeIsEven function returns a Boolean in an Option monadic context
254. Examples of filterM usage Example Monadic Context 1 Option 2 254
255. Examples of filterM usage Example Monadic Context 1 Option 2 List 255
256. For example, in the case of the list monad, using filterM provides a particularly concise means of computing the powerset of a list, which is given by all possible ways of including or excluding each element of the list: > filterM (\x -> [True,False]) [1,2,3] [[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]] Graham Hutton @haskellhutt assert( List(1, 2, 3).filterM(_ => List(true, false)) == List(List(1, 2, 3), List(1, 2), List(1, 3), List(1), List(2, 3), List(2), List(3), List()) ) 256 the anonymous function returns a Boolean in a List monadic context
257. def filterM[A, M[_]: Monad](l: List[A])(p: A => M[Boolean]): M[List[B]] = l match case Nil => Nil.pure case a::as => for keepingA <- p(a) filteredAs <- filterM(as)(p) yield if keepingA then a::filteredAs else filteredAs [] List().filterM(_ => List(true, false)) 257
258. def filterM[A, M[_]: Monad](l: List[A])(p: A => M[Boolean]): M[List[B]] = l match case Nil => Nil.pure case a::as => for keepingA <- p(a) filteredAs <- filterM(as)(p) yield if keepingA then a::filteredAs else filteredAs [] [[]] List().filterM(_ => List(true, false)) 258
259. def filterM[A, M[_]: Monad](l: List[A])(p: A => M[Boolean]): M[List[B]] = l match case Nil => Nil.pure case a::as => for keepingA <- p(a) // List(true, false) filteredAs <- filterM(as)(p) // List(List()) yield if keepingA then a::filteredAs else filteredAs [] [3] 3:: [[]] List(3).filterM(_ => List(true, false)) 259
260. def filterM[A, M[_]: Monad](l: List[A])(p: A => M[Boolean]): M[List[B]] = l match case Nil => Nil.pure case a::as => for keepingA <- p(a) // List(true, false) filteredAs <- filterM(as)(p) // List(List()) yield if keepingA then a::filteredAs else filteredAs [] [3] [] 3:: [[]] List(3).filterM(_ => List(true, false)) 260
261. def filterM[A, M[_]: Monad](l: List[A])(p: A => M[Boolean]): M[List[B]] = l match case Nil => Nil.pure case a::as => for keepingA <- p(a) // List(true, false) filteredAs <- filterM(as)(p) // List(List()) yield if keepingA then a::filteredAs else filteredAs [] [3] [] 3:: [[]] [[3],[]] List(3).filterM(_ => List(true, false)) 261
262. def filterM[A, M[_]: Monad](l: List[A])(p: A => M[Boolean]): M[List[B]] = l match case Nil => Nil.pure case a::as => for keepingA <- p(a) // List(true, false) filteredAs <- filterM(as)(p) // List(List(3),List()) yield if keepingA then a::filteredAs else filteredAs [] [3] [] [2,3] 2: 3: [[]] [[3],[]] List(2, 3).filterM(_ => List(true, false)) 262
263. def filterM[A, M[_]: Monad](l: List[A])(p: A => M[Boolean]): M[List[B]] = l match case Nil => Nil.pure case a::as => for keepingA <- p(a) // List(true, false) filteredAs <- filterM(as)(p) // List(List(3),List()) yield if keepingA then a::filteredAs else filteredAs [] [3] [] [2,3] [2] 2: 2: 3: [[]] [[3],[]] List(2, 3).filterM(_ => List(true, false)) 263
264. def filterM[A, M[_]: Monad](l: List[A])(p: A => M[Boolean]): M[List[B]] = l match case Nil => Nil.pure case a::as => for keepingA <- p(a) // List(true, false) filteredAs <- filterM(as)(p) // List(List(3),List()) yield if keepingA then a::filteredAs else filteredAs [] [3] [] [2,3] [3] 2: 3: [[]] [[3],[]] List(2, 3).filterM(_ => List(true, false)) 264 [2] 2:
265. def filterM[A, M[_]: Monad](l: List[A])(p: A => M[Boolean]): M[List[B]] = l match case Nil => Nil.pure case a::as => for keepingA <- p(a) // List(true, false) filteredAs <- filterM(as)(p) // List(List(3),List()) yield if keepingA then a::filteredAs else filteredAs [] [3] [] [2,3] [3] [2] [] 2: 2: 3: [[]] [[3],[]] List(2, 3).filterM(_ => List(true, false)) 265
266. def filterM[A, M[_]: Monad](l: List[A])(p: A => M[Boolean]): M[List[B]] = l match case Nil => Nil.pure case a::as => for keepingA <- p(a) // List(true, false) filteredAs <- filterM(as)(p) // List(List(3),List()) yield if keepingA then a::filteredAs else filteredAs [] [3] [] [2,3] [3] [2] [] 2: 2: 3: [[]] [[3],[]] [[2,3],[2],[3],[]] List(2, 3).filterM(_ => List(true, false)) 266
267. def filterM[A, M[_]: Monad](l: List[A])(p: A => M[Boolean]): M[List[B]] = l match case Nil => Nil.pure case a::as => for keepingA <- p(a) // List(true, false) filteredAs <- filterM(as)(p) // List(List(2,3),List(2),List(3),List()) yield if keepingA then a::filteredAs else filteredAs [] [3] [] [2,3] [3] [2] [] [1,2,3] 1: 2: 2: 3: [[]] [[3],[]] [[2,3],[2],[3],[]] List(1, 2, 3).filterM(_ => List(true, false)) 267
268. def filterM[A, M[_]: Monad](l: List[A])(p: A => M[Boolean]): M[List[B]] = l match case Nil => Nil.pure case a::as => for keepingA <- p(a) // List(true, false) filteredAs <- filterM(as)(p) // List(List(2,3),List(2),List(3),List()) yield if keepingA then a::filteredAs else filteredAs [] [3] [] [2,3] [3] [2] [] [1,2,3] 1: 2: 2: 3: [[]] [[3],[]] [[2,3],[2],[3],[]] List(1, 2, 3).filterM(_ => List(true, false)) 268 [1,2] 1:
269. def filterM[A, M[_]: Monad](l: List[A])(p: A => M[Boolean]): M[List[B]] = l match case Nil => Nil.pure case a::as => for keepingA <- p(a) // List(true, false) filteredAs <- filterM(as)(p) // List(List(2,3),List(2),List(3),List()) yield if keepingA then a::filteredAs else filteredAs [] [3] [] [2,3] [3] [2] [] [1,2,3] [1,3] [1,2] 1: 1: 1: 2: 2: 3: [[]] [[3],[]] [[2,3],[2],[3],[]] List(1, 2, 3).filterM(_ => List(true, false)) 269
270. def filterM[A, M[_]: Monad](l: List[A])(p: A => M[Boolean]): M[List[B]] = l match case Nil => Nil.pure case a::as => for keepingA <- p(a) // List(true, false) filteredAs <- filterM(as)(p) // List(List(2,3),List(2),List(3),List()) yield if keepingA then a::filteredAs else filteredAs [] [3] [] [2,3] [3] [2] [] [1,2,3] [1,3] [1,2] [1] 1: 1: 1: 1: 2: 2: 3: [[]] [[3],[]] [[2,3],[2],[3],[]] List(1, 2, 3).filterM(_ => List(true, false)) 270
271. def filterM[A, M[_]: Monad](l: List[A])(p: A => M[Boolean]): M[List[B]] = l match case Nil => Nil.pure case a::as => for keepingA <- p(a) // List(true, false) filteredAs <- filterM(as)(p) // List(List(2,3),List(2),List(3),List()) yield if keepingA then a::filteredAs else filteredAs [] [3] [] [2,3] [3] [2] [] [1,2,3] [2,3] 3: 2: 2: 3: [[]] [[3],[]] [[2,3],[2],[3],[]] List(1, 2, 3).filterM(_ => List(true, false)) 271 [1,3] [1,2] [1] 1: 1: 1:
272. def filterM[A, M[_]: Monad](l: List[A])(p: A => M[Boolean]): M[List[B]] = l match case Nil => Nil.pure case a::as => for keepingA <- p(a) // List(true, false) filteredAs <- filterM(as)(p) // List(List(2,3),List(2),List(3),List()) yield if keepingA then a::filteredAs else filteredAs [] [3] [] [2,3] [3] [2] [] [1,2,3] [2,3] [1,3] [1,2] [2] 1: 1: 1: 2: 2: 3: [[]] [[3],[]] [[2,3],[2],[3],[]] List(1, 2, 3).filterM(_ => List(true, false)) 272 [1] 1:
273. def filterM[A, M[_]: Monad](l: List[A])(p: A => M[Boolean]): M[List[B]] = l match case Nil => Nil.pure case a::as => for keepingA <- p(a) // List(true, false) filteredAs <- filterM(as)(p) // List(List(2,3),List(2),List(3),List()) yield if keepingA then a::filteredAs else filteredAs [] [3] [] [2,3] [3] [2] [] [1,2,3] [2,3] [1,3] [3] 1: 1: 2: 2: 3: [[]] [[3],[]] [[2,3],[2],[3],[]] List(1, 2, 3).filterM(_ => List(true, false)) 273 [1,2] [1] 1: 1: [2]
274. def filterM[A, M[_]: Monad](l: List[A])(p: A => M[Boolean]): M[List[B]] = l match case Nil => Nil.pure case a::as => for keepingA <- p(a) // List(true, false) filteredAs <- filterM(as)(p) // List(List(2,3),List(2),List(3),List()) yield if keepingA then a::filteredAs else filteredAs [] [3] [] [2,3] [3] [2] [] [1,2,3] [2,3] [1,3] [3] [1,2] [2] [1] [] 1: 1: 1: 1: 2: 2: 3: [[]] [[3],[]] [[2,3],[2],[3],[]] List(1, 2, 3).filterM(_ => List(true, false)) 274
275. def filterM[A, M[_]: Monad](l: List[A])(p: A => M[Boolean]): M[List[B]] = l match case Nil => Nil.pure case a::as => for keepingA <- p(a) filteredAs <- filterM(as)(p) yield if keepingA then a::filteredAs else filteredAs [] [3] [] [2,3] [3] [2] [] [1,2,3] [2,3] [1,3] [3] [1,2] [2] [1] [] 1: 1: 1: 1: 2: 2: 3: [[]] [[3],[]] [[2,3],[2],[3],[]] [[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]] List(1, 2, 3).filterM(_ => List(true, false)) 275
276. mapM λ 276
277. mapM λ 277
278. mapM λ 278
279. foldl :: (a -> b -> a) -> a -> [b] -> a def foldLeft[B](z: B)(op: (B, A) => B): B Applies a binary operator to a start value and all elements of this collection, going left to right. 279
280. Miran Lipovača Let’s sum a list of numbers with a fold: > foldl (\acc x -> acc + x) 0 [2,8,3,1] 14 … Now what if we wanted to sum a list of numbers but with the added condition that if any number is greater than 9 in the list, the whole thing fails? … 280
281. Miran Lipovača foldM The monadic counterpart to foldl is foldM. … The type of foldl is this: foldl :: (a -> b -> a) -> a -> [b] -> a Whereas foldM has the following type: foldM :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a The value that the binary function returns is monadic and so the result of the whole fold is monadic as well. 281
282. Miran Lipovača foldM The monadic counterpart to foldl is foldM. … The type of foldl is this: foldl :: (a -> b -> a) -> a -> [b] -> a Whereas foldM has the following type: foldM :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a The value that the binary function returns is monadic and so the result of the whole fold is monadic as well. 282
283. https://typelevel.org/cats/api/cats/Foldable$.html https://hackage.haskell.org/package/base-4.15.0.0/docs/Control-Monad.html 283
284. Examples of foldM usage: Example Monadic Context How the result of foldM is affected 1 2 284
285. Examples of foldM usage: Example Monadic Context How the result of foldM is affected 1 Option There may or may not be a result. 2 285
286. binSmalls :: Int -> Int -> Maybe Int binSmalls acc x | x > 9 = Nothing | otherwise = Just (acc + x) ghci> foldM binSmalls 0 [2,8,3,1] Just 14 ghci> foldM binSmalls 0 [2,11,3,1] Nothing Excellent! Because one number in the list was greater than 9, the whole thing resulted in a Nothing. Miran Lipovača def foldM[G[_], B](z: B)(f: (B, A) => G[B])(implicit G: Monad[G]): G[B] import cats.syntax.foldable._ assert( List(2,11,3,1).foldM(0)(binSmalls) == None ) assert( List(2,8,3,1).foldM(0)(binSmalls) == Some(14) ) def binSmalls(acc: Int, x: Int): Option[Int] = x match case x if x > 9 => None case otherwise => Some(acc + x) 286
287. That example of using foldM with a binary function that returns an optional value is useful. 287
288. That example of using foldM with a binary function that returns an optional value is useful. Things get a bit harder to understand when the binary function returns a list of values. 288
289. That example of using foldM with a binary function that returns an optional value is useful. Things get a bit harder to understand when the binary function returns a list of values. The way we are going to solve the N-Queens puzzle using foldM is by passing the latter a binary function returning a list of values. 289
290. That example of using foldM with a binary function that returns an optional value is useful. Things get a bit harder to understand when the binary function returns a list of values. The way we are going to solve the N-Queens puzzle using foldM is by passing the latter a binary function returning a list of values. So in upcoming slides we are going to look at a number of examples that do just that. 290
291. That example of using foldM with a binary function that returns an optional value is useful. Things get a bit harder to understand when the binary function returns a list of values. The way we are going to solve the N-Queens puzzle using foldM is by passing the latter a binary function returning a list of values. So in upcoming slides we are going to look at a number of examples that do just that. This is to strengthen our understanding of the foldM function. 291
292. That example of using foldM with a binary function that returns an optional value is useful. Things get a bit harder to understand when the binary function returns a list of values. The way we are going to solve the N-Queens puzzle using foldM is by passing the latter a binary function returning a list of values. So in upcoming slides we are going to look at a number of examples that do just that. This is to strengthen our understanding of the foldM function. Before we do that though, let’s take another look at the definition of foldM. 292
293. https://hackage.haskell.org/package/base-4.15.0.0/docs/Control-Monad.html foldM f a1 [x1, x2, ..., xm] == do a2 <- f a1 x1 -- access the value that is wrapped in a monadic context a3 <- f a2 x2 -- access the value that is wrapped in a monadic context ... f am xm – return the value leaving it wrapped in a monadic context 293
294. foldM f a1 [x1, x2, ..., xm] == do a2 <- f a1 x1 a3 <- f a2 x2 ... f am xm 294
295. foldM f a1 [x1, x2, ..., xm] == do 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 ... return f am xm we can look at the above as follows 295
296. foldM f a1 [x1, x2, ..., xm] == do a2 <- f a1 x1 a3 <- f a2 x2 ... f am xm List(x1, x2, ..., xm).foldM(a1)(f) == (for a2 <- f(a1,x1) a3 <- f(a2,x2) ... yield f(am,xm)).flatten foldM f a1 [x1, x2, ..., xm] == do a2 <- f a1 x1 a3 <- f a2 x2 ... return f am xm we can look at the above as follows which translates to 296
297. Examples of foldM usage: Example Monadic Context How the result of foldM is affected 1 Option There may or may not be a result. 2 297
298. Examples of foldM usage: Example Monadic Context How the result of foldM is affected 1 Option There may or may not be a result. 2 List There may be zero, one, or more results. So foldM manages zero, one, or more accumulators. 298
299. In the following examples, the following property holds… If foldM is applied to • a list of length n • an initial accumulator z • a function returning a list of length m Then foldM returns a list of length m ^ n. assert( List(...).foldM(...)((acc, val) => List(...)) == List(...) ) m=? z n=? m^n=? 299
300. In the following examples, the following property holds… If foldM is applied to • a list of length n • an initial accumulator z • a function returning a list of length m Then foldM returns a list of length m ^ n. assert( List(...).foldM(...)((acc, val) => List(...)) == List(...) ) m=? z n=? m^n=? assert( List().foldM(...)((acc, val) => List(...)) == List(z) ) m=? z n=0 m^n=1 when n=0, the returned list is a singleton containing z 300
301. assert( List().foldM(9)((_, _) => List(0, 0)) == List(9) ) m=2 z n=0 m^n = 2^0 = 1 In this first example, let’s choose a binary function that ignores both its parameters. This is to stress the fact that the property holds regardless of the particular values contained in the lists. assert( List(1, 2, 3).foldM(9)((_, _) => List(0, 0)) == List(0, 0, 0, 0, 0, 0, 0, 0) ) m=2 z n=3 m^n = 2^3 = 8 Let f = (_, _) => List(0, 0) List(x1,x2,x3) = List(1,2,3) a1 = 9 In List(x1, x2, ..., xm).foldM(a1)(f) i.e. (for a2 <- f(a1,x1) a3 <- f(a2,x2) ... yield f(am,xm)).flatten Result: List(0,0,0,0,0,0,0,0) 301
302. Invocation m n Result Result length (m^n) foldM (\_ -> \_ -> [0,0]) 9 [] 2 0 [9] 2^0=1 foldM (\_ -> \_ -> [0,0]) 9 [1] 2 1 [0,0] 2^1=2 302 \_ -> \_ -> [0,0] x => y => List(0,0)
303. [0,0] [0,0] 303 Invocation m n Result Result length (m^n) foldM (\_ -> \_ -> [0,0]) 9 [] 2 0 [9] 2^0=1 foldM (\_ -> \_ -> [0,0]) 9 [1] 2 1 [0,0] 2^1=2
304. [0,0] [0,0] [0,0] Invocation m n Result Result length (m^n) foldM (\_ -> \_ -> [0,0]) 9 [] 2 0 [9] 2^0=1 foldM (\_ -> \_ -> [0,0]) 9 [1] 2 1 [0,0] 2^1=2 foldM (\_ -> \_ -> [0,0]) 9 [1,2] 2 2 [0,0,0,0] 2^2=4 [0,0,0,0] [0,0] 304
305. [0,0] [0,0] [0,0] [0,0] [0,0] [0,0] [0,0] Invocation m n Result Result length (m^n) foldM (\_ -> \_ -> [0,0]) 9 [] 2 0 [9] 2^0=1 foldM (\_ -> \_ -> [0,0]) 9 [1] 2 1 [0,0] 2^1=2 foldM (\_ -> \_ -> [0,0]) 9 [1,2] 2 2 [0,0,0,0] 2^2=4 foldM (\_ -> \_ -> [0,0]) 9 [1,2,3] 2 3 [0,0,0,0,0,0,0,0] 2^3=8 [0,0,0,0,0,0,0,0] [0,0,0,0] [0,0] 305
306. [0,0] [0,0] [0,0] [0,0] [0,0] [0,0] [0,0] [0,0] [0,0] [0,0] [0,0] [0,0] [0,0] [0,0] [0,0] Invocation m n Result Result length (m^n) foldM (\_ -> \_ -> [0,0]) 9 [] 2 0 [9] 2^0=1 foldM (\_ -> \_ -> [0,0]) 9 [1] 2 1 [0,0] 2^1=2 foldM (\_ -> \_ -> [0,0]) 9 [1,2] 2 2 [0,0,0,0] 2^2=4 foldM (\_ -> \_ -> [0,0]) 9 [1,2,3] 2 3 [0,0,0,0,0,0,0,0] 2^3=8 foldM (\_ -> \_ -> [0,0]) 9 [1,2,3,4] 2 4 [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 2^4=16 [0,0,0,0,0,0,0,0] [0,0,0,0] [0,0] [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 306
307. In this second example, we change the binary function that we pass to foldM so that… 307
308. In this second example, we change the binary function that we pass to foldM so that… …rather than ignoring its two parameters (the accumulator acc and the current list element x) and always returning the same two-element list List(0,0) … (_, _) => List(0, 0) 308
309. In this second example, we change the binary function that we pass to foldM so that… …rather than ignoring its two parameters (the accumulator acc and the current list element x) and always returning the same two-element list List(0,0) … (_, _) => List(0, 0) …the function now returns a two-element list containing 1. the result of adding the current element to the accumulator and 2. the result of subtracting the current element from the accumulator (acc,x) => List(acc+x, acc-x) 309
310. Let f = (acc,x) => List(acc+x, acc-x) List(x1,x2,x3) = List(1,2,3) a1 = 0 In List(x1, x2, ..., xm).foldM(a1)(f) i.e. (for a2 <- f(a1,x1) a3 <- f(a2,x2) ... yield f(am,xm)).flatten Result: List(6,0,2,-4,4,-2,0,-6)) assert( List(1,2,3).foldM(0)((acc,x) => List(acc+x, acc-x)) == List(6,0,2,-4,4,-2,0,-6) ) 310
311. Invocation Result Result length (m^n) foldM (\acc x -> [acc + x, acc - x]) 0 [] [0] 2^0=1 0 [0] 311
312. Invocation Result Result length (m^n) foldM (\acc x -> [acc + x, acc - x]) 0 [] [0] 2^0=1 foldM (\acc x -> [acc + x, acc - x]) 0 [1] [1,-1] 2^1=2 0 1 -1 +1 -1 [1,-1] [0] 312
313. Invocation Result Result length (m^n) foldM (\acc x -> [acc + x, acc - x]) 0 [] [0] 2^0=1 foldM (\acc x -> [acc + x, acc - x]) 0 [1] [1,-1] 2^1=2 foldM (\acc x -> [acc + x, acc - x]) 0 [1,2] [3,-1,1,-3] 2^2=4 0 1 -1 +1 -1 -1 3 -3 1 +2 -2 +2 -2 [3,-1,1,-3] [1,-1] [0] 313
314. Invocation Result Result length (m^n) foldM (\acc x -> [acc + x, acc - x]) 0 [] [0] 2^0=1 foldM (\acc x -> [acc + x, acc - x]) 0 [1] [1,-1] 2^1=2 foldM (\acc x -> [acc + x, acc - x]) 0 [1,2] [3,-1,1,-3] 2^2=4 foldM (\acc x -> [acc + x, acc - x]) 0 [1,2,3] [6,0,2,-4,4,-2,0,-6] 2^3=8 0 1 -1 +1 -1 -1 3 -3 1 0 6 -4 2 -2 4 -6 0 +2 -2 +2 -2 +3 -3 +3 -3 +3 -3 +3 -3 [6,0,2,-4,4,-2,0,-6] [3,-1,1,-3] [1,-1] [0] 314
315. In this third example, we change the binary function that we pass to foldM so that… 315
316. In this third example, we change the binary function that we pass to foldM so that… …rather than returning a two-element list containing 1) the result of adding the current element x to the accumulator 2) the result of subtracting x from the accumulator (acc,x) => List(acc+x, acc-x) 316
317. In this third example, we change the binary function that we pass to foldM so that… …rather than returning a two-element list containing 1) the result of adding the current element x to the accumulator 2) the result of subtracting x from the accumulator (acc,x) => List(acc+x, acc-x) …it returns a two element list containing 1) the result of adding x to the front of the accumulator list 2) the accumulator list (acc,x) => List(x::acc, acc) As a result, foldM computes the powerset of its list parameter. 317
318. Let f = (acc,x) => List(x::acc, acc) List(x1,x2,x3) = List(1,2,3) a1 = List.empty In List(x1, x2, ..., xm).foldM(a1)(f) i.e. (for a2 <- f(a1,x1) a3 <- f(a2,x2) ... yield f(am,xm)).flatten Result: List( List(3,2,1), List(2,1), List(3,1), List(1), List(3,2), List(2), List(3), List())) assert( List(1,2,3).foldM(List.empty)((acc,x) => List(x::acc, acc)) == List( List(3,2,1), List(2,1), List(3,1), List(1), List(3,2), List(2), List(3), List()) ) ) 318
319. Invocation Result Result length (m^n) foldM (\acc x -> [x:acc,acc]) [] [] [[]] 2^0=1 [] [[]] 319
320. Invocation Result Result length (m^n) foldM (\acc x -> [x:acc,acc]) [] [] [[]] 2^0=1 foldM (\acc x -> [x:acc,acc]) [] [1] [[1],[]] 2^1=2 [] [1] [] 1: [[]] [[1],[]] 320
321. Invocation Result Result length (m^n) foldM (\acc x -> [x:acc,acc]) [] [] [[]] 2^0=1 foldM (\acc x -> [x:acc,acc]) [] [1] [[1],[]] 2^1=2 foldM (\acc x -> [x:acc,acc]) [] [1,2] [[2,1],[1],[2],[]] 2^2=4 [] [1] [] [2,1] [1] [2] [] 2: 2: 1: [[]] [[1],[]] [[2,1],[1],[2],[]] 321
322. Invocation Result Result length (m^n) foldM (\acc x -> [x:acc,acc]) [] [] [[]] 2^0=1 foldM (\acc x -> [x:acc,acc]) [] [1] [[1],[]] 2^1=2 foldM (\acc x -> [x:acc,acc]) [] [1,2] [[2,1],[1],[2],[]] 2^2=4 foldM (\acc x -> [x:acc,acc]) [] [1,2,3] [[3,2,1],[2,1],[3,1],[1],[3,2],[2],[3],[]] 2^3=8 [] [1] [] [2,1] [1] [2] [] [3,2,1] [2,1] [3,1] [1] [3,2] [2] [3] [] 3: 3: 3: 3: 2: 2: 1: [[]] [[1],[]] [[2,1],[1],[2],[]] [[3,2,1],[2,1],[3,1],[1],[3,2],[2],[3],[]] 322
323. Invocation Result Result length (m^n) foldM (\acc x -> [x:acc,acc]) [] [] [[]] 2^0=1 foldM (\acc x -> [x:acc,acc]) [] [1] [[1],[]] 2^1=2 foldM (\acc x -> [x:acc,acc]) [] [1,2] [[2,1],[1],[2],[]] 2^2=4 foldM (\acc x -> [x:acc,acc]) [] [1,2,3] [[3,2,1],[2,1],[3,1],[1],[3,2],[2],[3],[]] 2^3=8 [] [1] [] [2,1] [1] [2] [] [3,2,1] [2,1] [3,1] [1] [3,2] [2] [3] [] 3: 3: 3: 3: 2: 2: 1: [[]] [[1],[]] [[2,1],[1],[2],[]] [[3,2,1],[2,1],[3,1],[1],[3,2],[2],[3],[]] Yes, this is the same process that we saw in this previous example: List(1, 2, 3).filterM(_ => List(true, false)) So the following also computes the powerset of the input list: List(1, 2, 3).foldM(List.empty)((acc,x) => List(x::acc, acc)) 323
324. assert( List(1,2,3,4).foldM(9)((_,_) => List(0, 0)) == List(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)) assert( List(1,2,3).foldM(0)((acc,x) => List(acc+x, acc-x)) == List(6,0,2,-4,4,-2,0,-6)) assert( List(1,2,3).foldM(List.empty)((acc,x) => List(x::acc,acc)) == List(List(3,2,1),List(2,1),List(3,1),List(1),List(3,2),List(2),List(3),List())) assertEqual "foldM test 1" (foldM (\_ _ -> [0,0]) 9 [1,2,3,4]) [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] assertEqual "foldM test 2" (foldM (\acc x -> [acc+x,acc-x]) 0 [1,2,3]) [6,0,2,-4,4,-2,0,-6] assertEqual "foldM test 3" (foldM (\acc x -> [x:acc,acc])[] [1,2,3]) [[3,2,1],[2,1],[3,1],[1],[3,2],[2],[3],[]] import cats.syntax.foldable._ import Control.Monad Cats The three foldM examples that we have just gone through In the rest of this talk we’ll refer to the function passed to foldM as an updater function 324
325. mapM λ 325
326. mapM λ 326
327. Now that we have gained some familiarity with the foldM function... …let’s begin to see how it can be used to solve the N-Queens combinatorial problem. 327
328. Let’s refer to the solution that uses foldM as the folding queens solution. The folding queens solution needs to generate the permutations of a list of integers. 328
329. N = 4 # of permutations = 44 = 256 Permutations with repetition allowed def permutations(n:Int = 4): List[List[Int]] = if n == 0 then List(List()) else for queens <- permutations(n-1) queen <- 1 to 4 yield queen :: queens 329
330. 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 Permutations 1 2 3 List The number of permutations of a list of length n is n!, the factorial of n. e.g. the number of permutations of a list of three elements is 3! = 3 * 2 * 1 = 6 Permutations with repetition not allowed 330
331. 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 Permutations 1 2 3 List 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 Permutations 1 2 3 List The number of permutations of a list of length n is n!, the factorial of n. e.g. the number of permutations of a list of three elements is 3! = 3 * 2 * 1 = 6 Permutations with repetition not allowed 331
332. Permutations List 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 Permutations 1 2 3 List 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 Permutations 1 2 3 List The number of permutations of a list of length n is n!, the factorial of n. e.g. the number of permutations of a list of three elements is 3! = 3 * 2 * 1 = 6 Permutations with repetition not allowed 332
333. update :: Eq a => ([a], [a]) -> p -> [([a], [a])] update (permutation,choices) _ = [(choice:permutation, delete choice choices) | choice <- choices] Let’s look at an updater function that can be used to generate the permutations of a list. 333
334. update :: Eq a => ([a], [a]) -> p -> [([a], [a])] update (permutation,choices) _ = [(choice:permutation, delete choice choices) | choice <- choices] Invocation foldM update ([],[1,2,3]) [1,2,3] Result [([3,2,1],[]), ([2,3,1],[]), ([3,1,2],[]), ([1,3,2],[]), ([2,1,3],[]), ([1,2,3],[])] Let’s look at an updater function that can be used to generate the permutations of a list. 334
335. [] [1,2,3] ( , ) Invocation Result foldM update ([],[1,2,3]) [] [([],[1,2,3])] 335
336. [1] [2,3] [3] [1,2] ( , ) ( , ) [] [1,2,3] ( , ) [2] [1,3] ( , ) Invocation Result foldM update ([],[1,2,3]) [] [([],[1,2,3])] foldM update ([],[1,2,3]) [1] [([1],[2,3]), ([2],[1,3]), ([3],[1,2])] choose 1 choose 2 choose 3 336
337. ( , ) ( , ) ( , ) ( , ) ( , ) ( , ) [2,3] [1,3] [3,2] [1,2] [3,1] [2,1] [3] [1] [2,3] [3] [1,2] ( , ) ( , ) [] [1,2,3] ( , ) [2] [1,3] ( , ) [3] [1] [2] [1] [2] Invocation Result foldM update ([],[1,2,3]) [] [([],[1,2,3])] foldM update ([],[1,2,3]) [1] [([1],[2,3]), ([2],[1,3]), ([3],[1,2])] foldM update ([],[1,2,3]) [1,2] [([2,1],[3]), ([3,1],[2]), ([1,2],[3]), ([3,2],[1]), ([1,3],[2]), ([2,3],[1])] choose 1 choose 2 choose 3 choose 2 choose 3 choose 1 choose 3 choose 1 choose 2 337
338. ( , ) ( , ) ( , ) ( , ) ( , ) ( , ) ( , ) ( , ) ( , ) ( , ) ( , ) ( , ) [1,2,3] [2,1,3] [1,3,2] [3,1,2] [2,3,1] [2,3] [1,3] [3,2] [1,2] [3,1] [2,1] [3] [1] [2,3] [3] [1,2] ( , ) ( , ) [] [1,2,3] ( , ) [2] [1,3] ( , ) [3] [1] [2] [1] [2] [3,2,1] [] [] [] [] [] [] Invocation Result foldM update ([],[1,2,3]) [] [([],[1,2,3])] foldM update ([],[1,2,3]) [1] [([1],[2,3]), ([2],[1,3]), ([3],[1,2])] foldM update ([],[1,2,3]) [1,2] [([2,1],[3]), ([3,1],[2]), ([1,2],[3]), ([3,2],[1]), ([1,3],[2]), ([2,3],[1])] foldM update ([],[1,2,3]) [1,2,3] [([3,2,1],[]), ([2,3,1],[]), ([3,1,2],[]), ([1,3,2],[]), ([2,1,3],[]), ([1,2,3],[])] choose 1 choose 2 choose 3 choose 2 choose 3 choose 1 choose 3 choose 1 choose 2 choose 3 choose 2 choose 3 choose 1 choose 2 choose 1 338 Size of input list being folded: N Size of output list containing permutations: N!
339. The result of foldM is not exactly a list of permutations, but rather, a list of a pair of a permutation and the empty list. 339
340. permute :: Eq a => [a] -> [([a], [a])] permute xs = foldM update ([],xs) xs permutations :: (Eq a) => [a] -> [[a]] permutations xs = map fst (permute xs) > permutations [] [[]] > permutations [1] [[1]] > permutations [1,2] [[2,1],[1,2]] > permutations [1,2,3] [[3,2,1],[2,3,1],[3,1,2],[1,3,2],[2,1,3],[1,2,3]] > permutations [1,2,3,4] [[4,3,2,1],[3,4,2,1],[4,2,3,1],[2,4,3,1],[3,2,4,1] ,[2,3,4,1],[4,3,1,2],[3,4,1,2],[4,1,3,2],[1,4,3,2] ,[3,1,4,2],[1,3,4,2],[4,2,1,3],[2,4,1,3],[4,1,2,3] ,[1,4,2,3],[2,1,4,3],[1,2,4,3],[3,2,1,4],[2,3,1,4] ,[3,1,2,4],[1,3,2,4],[2,1,3,4],[1,2,3,4]] The result of foldM is not exactly a list of permutations, but rather, a list of a pair of a permutation and the empty list. Let’s defined a couple of helper functions to make it more convenient to get hold of the desired list of permutations. 340
341. def update[A](acc:(List[A], List[A]), a:A): List[(List[A], List[A])] = acc match case (permutation, choices) => for choice <- choices yield (choice :: permutation, choices.diff(List(choice))) assert( List(1,2,3).foldM((List.empty[Int],List(1,2,3)))(update) == List( (List(3,2,1),List()), (List(2,3,1),List()), (List(3,1,2),List()), (List(1,3,2),List()), (List(2,1,3),List()), (List(1,2,3),List())) ) Cats 341
342. def permute[A](as: List[A]): List[(List[A], List[A])] = as.foldM((List.empty[A], as))(update) def permutations[A](as: List[A]): List[List[A]] = permute(as).map(_.head) Cats assert( permutations(List(1,2,3)) == List( List(3, 2, 1), List(2, 3, 1), List(3, 1, 2), List(1, 3, 2), List(2, 1, 3), List(1, 2, 3) ) ) 342
343. update (permutation,choices) _ = [(choice:permutation, delete choice choices) | choice <- choices] oneMoreQueen (queens,emptyColumns) _ = [(queen:queens, delete queen emptyColumns) | queen <- emptyColumns] We want to use foldM to solve the N-Queens combinatorial problem. So let’s rename the variables of the update function to reflect the fact that the permutations that we want to generate are the possible lists of positions (columns) of 𝑛 queens on an 𝑛×𝑛 board. def oneMoreQueen[A](acc:(List[A], List[A]), a:A): List[(List[A], List[A])] = acc match case (queens, emptyColumns) => for queen <- emptyColumns yield (queen :: queens, emptyColumns.diff(List(queen))) def update[A](acc:(List[A], List[A]), a:A): List[(List[A], List[A])] = acc match case (permutation, choices) => for choice <- choices yield (choice :: permutation, choices.diff(List(choice))) 343
344. Not all permutations are valid though: we need to filter out unsafe permutations. Just like in the recursive solution, we are going to determine if a permutation is safe is by using a safe function. Let’s add to oneMoreQueen a filter that invokes the safe function. oneMoreQueen (queens, emptyColumns) _ = [(queen:queens, delete queen emptyColumns) | queen <- emptyColumns] oneMoreQueen (queens, emptyColumns) _ = [(queen:queens, delete queen emptyColumns) | queen <- emptyColumns,isSafe queen] def oneMoreQueen[A](acc:(List[A], List[A]), a:A): List[(List[A], List[A])] = acc match case (queens, emptyColumns) => for queen <- emptyColumns yield (queen :: queens, emptyColumns.diff(List(queen))) def oneMoreQueen[A](acc:(List[A], List[A]), a:A): List[(List[A], List[A])] = acc match case (queens, emptyColumns) => for queen <- emptyColumns if isSafe(queen) yield (queen :: queens, emptyColumns.diff(List(queen))) 344
345. Earlier we tried out our update function as follows (to compute permutations) foldM update ([],[1,2,3]) [1,2,3] List(1,2,3).foldM((List.empty[Int],List(1,2,3)))(update) 345
346. Earlier we tried out our update function as follows (to compute permutations) foldM update ([],[1,2,3]) [1,2,3] List(1,2,3).foldM((List.empty[Int],List(1,2,3)))(update) The queens function that we need to implement is this: queens :: Int -> [[Int]] queens n = ??? def queens(n: Int): List[List[Int]] = ??? 346 queens(4) List(List(3,1,4,2),List(2,4,1,3)))
347. Earlier we tried out our update function as follows (to compute permutations) foldM update ([],[1,2,3]) [1,2,3] List(1,2,3).foldM((List.empty[Int],List(1,2,3)))(update) The queens function that we need to implement is this: queens :: Int -> [[Int]] queens n = ??? def queens(n: Int): List[List[Int]] = ??? Given that we have renamed update to oneMoreQueen, here is how we need to call foldM: foldM oneMoreQueen ([],[1..n]) [1..n] List(1 to n *).foldM(List.empty[Int], List(1 to n *))(oneMoreQueen) 347 queens(4) List(List(3,1,4,2),List(2,4,1,3))) update oneMoreQueen 1..3 1..n
348. Earlier we tried out our update function as follows (to compute permutations) foldM update ([],[1,2,3]) [1,2,3] List(1,2,3).foldM((List.empty[Int],List(1,2,3)))(update) The queens function that we need to implement is this: queens :: Int -> [[Int]] queens n = ??? def queens(n: Int): List[List[Int]] = ??? Given that we have renamed update to oneMoreQueen, here is how we need to call foldM: foldM oneMoreQueen ([],[1..n]) [1..n] List(1 to n *).foldM(Nil, List(1 to n *))(oneMoreQueen) We saw earlier that in order to extract the list of permutations / queens from the result of update / oneMoreQueen, we need to map over the result list a function that takes the first element of each pair in the list. So here is how we implement queens: queens :: Int -> [[Int]] queens n = map fst (foldM oneMoreQueen ([],[1..n]) [1..n]) def queens(n: Int): List[List[Int]] = List(1 to n *).foldM(Nil, List(1 to n *))(oneMoreQueen).map(_.head) 348 queens(4) List(List(3,1,4,2),List(2,4,1,3))) update oneMoreQueen 1..3 1..n List[(List[Int], List[Int])] List[List[Int]]
349. def queens(n: Int): List[List[Int]] = def oneMoreQueen(acc:(List[Int],List[Int]),x:Int): List[(List[Int],List[Int])] = acc match { case (queens, emptyColumns) => def isSafe(x:Int): Boolean = { for (c,n) <- queens zip (1 to n) yield x != c + n && x != c – n } forall identity for queen <- emptyColumns if isSafe(queen) yield (queen::queens, emptyColumns diff List(queen)) } val oneToN = List(1 to n *) oneToN.foldM(Nil, oneToN)(oneMoreQueen).map(_.head) queens :: Int -> [[Int]] queens n = map fst (foldM oneMoreQueen ([],[1..n]) [1..n]) where oneMoreQueen (queens, emptyColumns) _ = [(queen:queens, delete queen emptyColumns) | queen <- emptyColumns, isSafe queen] where isSafe x = and [x /= c + n && x /= c - n | (n,c) <- zip [1..] queens] import cats.syntax.foldable._ Cats import Control.Monad 349
350. Iterative Algorithm Recursive Algorithm 350
351. queens n = placeQueens n where placeQueens 0 = [[]] placeQueens k = [queen:queens | queens <- placeQueens(k-1), queen <- [1..n], isSafe queen queens] isSafe queen queens = all safe (zipWithRows queens) where safe (r,c) = c /= col && not (onDiagonal col row c r) row = length queens col = queen onDiagonal row column otherRow otherColumn = abs (row - otherRow) == abs (column - otherColumn) zipWithRows queens = zip rowNumbers queens where rowCount = length queens rowNumbers = [rowCount-1,rowCount-2..0] def queens(n: Int): List[List[Int]] = def placeQueens(k: Int): List[List[Int]] = if k == 0 then List(List()) else for queens <- placeQueens(k - 1) queen <- 1 to n if isSafe(queen, queens) yield queen :: queens placeQueens(n) def onDiagonal(row: Int, column: Int, otherRow: Int, otherColumn: Int) = math.abs(row - otherRow) == math.abs(column - otherColumn) def isSafe(queen: Int, queens: List[Int]): Boolean = val (row, column) = (queens.length, queen) val safe: ((Int,Int)) => Boolean = (nextRow, nextColumn) => column != nextColumn && !onDiagonal(column, row, nextColumn, nextRow) zipWithRows(queens) forall safe def zipWithRows(queens: List[Int]): Iterable[(Int,Int)] = val rowCount = queens.length val rowNumbers = rowCount - 1 to 0 by -1 rowNumbers zip queens Recursive Algorithm 351
352. queens n = placeQueens n where placeQueens 0 = [[]] placeQueens k = [queen:queens | queens <- placeQueens(k-1), queen <- [1..n], isSafe queen queens] queens :: Int -> [[Int]] queens n = map fst (foldM oneMoreQueen ([],[1..n]) [1..n]) where oneMoreQueen (queens,emptyColumns) _ = [(queen:queens, delete queen emptyColumns) | queen <- emptyColumns, isSafe queen] where isSafe x = and [x /= c + n && x /= c - n | (n,c) <- zip [1..] queens] Recursive Algorithm Iterative Algorithm 352
353. queens :: Int -> [[Int]] queens n = map fst (foldM oneMoreQueen ([],[1..n]) [1..n]) where oneMoreQueen (queens, emptyColumns) _ = [(queen:queens, delete queen emptyColumns) | queen <- emptyColumns, isSafe queen] where isSafe x = and [x /= c + n && x /= c - n | (n,c) <- zip [1..] queens] -- given n, "queens n" solves the n-queens problem, returning a list of all the -- safe arrangements. each solution is a list of the columns where the queens are -- located for each row queens :: Int -> [[Int]] queens n = map fst $ foldM oneMoreQueen ([],[1..n]) [1..n] where -- foldM :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a -- foldM folds (from left to right) in the list monad, which is convenient for -- "nondeterminstically" finding "all possible solutions" of something. the -- initial value [] corresponds to the only safe arrangement of queens in 0 rows -- given a safe arrangement y of queens in the first i rows, and a list of -- possible choices, "oneMoreQueen y _" returns a list of all the safe -- arrangements of queens in the first (i+1) rows along with remaining choices oneMoreQueen (y,d) _ = [(x:y, delete x d) | x <- d, safe x] where -- "safe x" tests whether a queen at column x is safe from previous queens safe x = and [x /= c + n && x /= c - n | (n,c) <- zip [1..] y] https://rosettacode.org/wiki/N-queens_problem#Haskell Rosetta Code Version Our Version 353
354. def queens(n: Int): List[List[Int]] = def placeQueens(k: Int): List[List[Int]] = if k == 0 then List(List()) else for queens <- placeQueens(k - 1) queen <- 1 to n if safe(queen, queens) yield queen :: queens placeQueens(n) Recursive Algorithm def queens(n: Int): List[List[Int]] = def oneMoreQueen(acc: (List[Int],List[Int]), x: Int): List[(List[Int],List[Int])] = acc match case (queens, emptyColumns) => def isSafe(queen:Int): Boolean = … for queen <- emptyColumns if isSafe(queen) yield (queen::queens, emptyColumns diff List(queen)) List(1 to n *).foldM(Nil, List(1 to n *))(oneMoreQueen).map(_.head) import cats.syntax.foldable._ Cats Iterative Algorithm 354
355. N = 8 92 solutions 355
356. > queens 8 [[4,2,7,3,6,8,5,1],[5,2,4,7,3,8,6,1],[3,5,2,8,6,4,7,1],[3,6,4,2,8,5,7,1],[5,7,1,3,8,6,4,2] ,[4,6,8,3,1,7,5,2],[3,6,8,1,4,7,5,2],[5,3,8,4,7,1,6,2],[5,7,4,1,3,8,6,2],[4,1,5,8,6,3,7,2] ,[3,6,4,1,8,5,7,2],[4,7,5,3,1,6,8,2],[6,4,2,8,5,7,1,3],[6,4,7,1,8,2,5,3],[1,7,4,6,8,2,5,3] ,[6,8,2,4,1,7,5,3],[6,2,7,1,4,8,5,3],[4,7,1,8,5,2,6,3],[5,8,4,1,7,2,6,3],[4,8,1,5,7,2,6,3] ,[2,7,5,8,1,4,6,3],[1,7,5,8,2,4,6,3],[2,5,7,4,1,8,6,3],[4,2,7,5,1,8,6,3],[5,7,1,4,2,8,6,3] ,[6,4,1,5,8,2,7,3],[5,1,4,6,8,2,7,3],[5,2,6,1,7,4,8,3],[6,3,7,2,8,5,1,4],[2,7,3,6,8,5,1,4] ,[7,3,1,6,8,5,2,4],[5,1,8,6,3,7,2,4],[1,5,8,6,3,7,2,4],[3,6,8,1,5,7,2,4],[6,3,1,7,5,8,2,4] ,[7,5,3,1,6,8,2,4],[7,3,8,2,5,1,6,4],[5,3,1,7,2,8,6,4],[2,5,7,1,3,8,6,4],[3,6,2,5,8,1,7,4] ,[6,1,5,2,8,3,7,4],[8,3,1,6,2,5,7,4],[2,8,6,1,3,5,7,4],[5,7,2,6,3,1,8,4],[3,6,2,7,5,1,8,4] ,[6,2,7,1,3,5,8,4],[3,7,2,8,6,4,1,5],[6,3,7,2,4,8,1,5],[4,2,7,3,6,8,1,5],[7,1,3,8,6,4,2,5] ,[1,6,8,3,7,4,2,5],[3,8,4,7,1,6,2,5],[6,3,7,4,1,8,2,5],[7,4,2,8,6,1,3,5],[4,6,8,2,7,1,3,5] ,[2,6,1,7,4,8,3,5],[2,4,6,8,3,1,7,5],[3,6,8,2,4,1,7,5],[6,3,1,8,4,2,7,5],[8,4,1,3,6,2,7,5] ,[4,8,1,3,6,2,7,5],[2,6,8,3,1,4,7,5],[7,2,6,3,1,4,8,5],[3,6,2,7,1,4,8,5],[4,7,3,8,2,5,1,6] ,[4,8,5,3,1,7,2,6],[3,5,8,4,1,7,2,6],[4,2,8,5,7,1,3,6],[5,7,2,4,8,1,3,6],[7,4,2,5,8,1,3,6] ,[8,2,4,1,7,5,3,6],[7,2,4,1,8,5,3,6],[5,1,8,4,2,7,3,6],[4,1,5,8,2,7,3,6],[5,2,8,1,4,7,3,6] ,[3,7,2,8,5,1,4,6],[3,1,7,5,8,2,4,6],[8,2,5,3,1,7,4,6],[3,5,2,8,1,7,4,6],[3,5,7,1,4,2,8,6] ,[5,2,4,6,8,3,1,7],[6,3,5,8,1,4,2,7],[5,8,4,1,3,6,2,7],[4,2,5,8,6,1,3,7],[4,6,1,5,2,8,3,7] ,[6,3,1,8,5,2,4,7],[5,3,1,6,8,2,4,7],[4,2,8,6,1,3,5,7],[6,3,5,7,1,4,2,8],[6,4,7,1,3,5,2,8] ,[4,7,5,2,6,1,3,8],[5,7,2,6,3,1,4,8]] > length (queens 8) 92 356
357. assert( queens(8) == List( List(4,2,7,3,6,8,5,1),List(5,2,4,7,3,8,6,1),List(3,5,2,8,6,4,7,1),List(3,6,4,2,8,5,7,1),List(5,7,1,3,8,6,4,2), List(4,6,8,3,1,7,5,2),List(3,6,8,1,4,7,5,2),List(5,3,8,4,7,1,6,2),List(5,7,4,1,3,8,6,2),List(4,1,5,8,6,3,7,2), List(3,6,4,1,8,5,7,2),List(4,7,5,3,1,6,8,2),List(6,4,2,8,5,7,1,3),List(6,4,7,1,8,2,5,3),List(1,7,4,6,8,2,5,3), List(6,8,2,4,1,7,5,3),List(6,2,7,1,4,8,5,3),List(4,7,1,8,5,2,6,3),List(5,8,4,1,7,2,6,3),List(4,8,1,5,7,2,6,3), List(2,7,5,8,1,4,6,3),List(1,7,5,8,2,4,6,3),List(2,5,7,4,1,8,6,3),List(4,2,7,5,1,8,6,3),List(5,7,1,4,2,8,6,3), List(6,4,1,5,8,2,7,3),List(5,1,4,6,8,2,7,3),List(5,2,6,1,7,4,8,3),List(6,3,7,2,8,5,1,4),List(2,7,3,6,8,5,1,4), List(7,3,1,6,8,5,2,4),List(5,1,8,6,3,7,2,4),List(1,5,8,6,3,7,2,4),List(3,6,8,1,5,7,2,4),List(6,3,1,7,5,8,2,4), List(7,5,3,1,6,8,2,4),List(7,3,8,2,5,1,6,4),List(5,3,1,7,2,8,6,4),List(2,5,7,1,3,8,6,4),List(3,6,2,5,8,1,7,4), List(6,1,5,2,8,3,7,4),List(8,3,1,6,2,5,7,4),List(2,8,6,1,3,5,7,4),List(5,7,2,6,3,1,8,4),List(3,6,2,7,5,1,8,4), List(6,2,7,1,3,5,8,4),List(3,7,2,8,6,4,1,5),List(6,3,7,2,4,8,1,5),List(4,2,7,3,6,8,1,5),List(7,1,3,8,6,4,2,5), List(1,6,8,3,7,4,2,5),List(3,8,4,7,1,6,2,5),List(6,3,7,4,1,8,2,5),List(7,4,2,8,6,1,3,5),List(4,6,8,2,7,1,3,5), List(2,6,1,7,4,8,3,5),List(2,4,6,8,3,1,7,5),List(3,6,8,2,4,1,7,5),List(6,3,1,8,4,2,7,5),List(8,4,1,3,6,2,7,5), List(4,8,1,3,6,2,7,5),List(2,6,8,3,1,4,7,5),List(7,2,6,3,1,4,8,5),List(3,6,2,7,1,4,8,5),List(4,7,3,8,2,5,1,6), List(4,8,5,3,1,7,2,6),List(3,5,8,4,1,7,2,6),List(4,2,8,5,7,1,3,6),List(5,7,2,4,8,1,3,6),List(7,4,2,5,8,1,3,6), List(8,2,4,1,7,5,3,6),List(7,2,4,1,8,5,3,6),List(5,1,8,4,2,7,3,6),List(4,1,5,8,2,7,3,6),List(5,2,8,1,4,7,3,6), List(3,7,2,8,5,1,4,6),List(3,1,7,5,8,2,4,6),List(8,2,5,3,1,7,4,6),List(3,5,2,8,1,7,4,6),List(3,5,7,1,4,2,8,6), List(5,2,4,6,8,3,1,7),List(6,3,5,8,1,4,2,7),List(5,8,4,1,3,6,2,7),List(4,2,5,8,6,1,3,7),List(4,6,1,5,2,8,3,7), List(6,3,1,8,5,2,4,7),List(5,3,1,6,8,2,4,7),List(4,2,8,6,1,3,5,7),List(6,3,5,7,1,4,2,8),List(6,4,7,1,3,5,2,8), List(4,7,5,2,6,1,3,8),List(5,7,2,6,3,1,4,8)) ) assert(queens(8).size == 92) 357
358. The recursive algorithm has no ‘memory’ of the columns in which queens have already been placed, so it will generate and test a permutation for safety, even if it contains repetitions, like the following one. The iterative algorithm does have ‘memory’, in that permutations with repetition, like the one above, are not even considered as candidate solutions, i.e. it ‘remembers’ where it has already placed previous queens. 358
359. Without the isSafe function, the recursive algorithm would generate 44 = 256 candidate solution boards. 359
360. With the isSafe function, the recursive algorithm generates 60 boards. 360
361. recursive solution (no memory) 361
362. recursive solution (no memory) 362
363. recursive solution (no memory) 363
364. recursive solution (no memory) 364
365. recursive solution (no memory) Boards generated & ested (in red): 60 (out of 256) 365
366. Of the 60 boards generated, 16 are candidate solution boards. 366
367. recursive solution (no memory) Boards generated & ested (in red): 60 (out of 256) 367
368. recursive solution (no memory) Candidate boards enerated & tested in pink): 16 368
369. Lets compare that with the iterative solution 369
370. Without the isSafe function, the iterative algorithm would generate 4! = 24 candidate solution boards. 370
371. With the isSafe function, the iterative algorithm generates 32 boards. 371
372. iterative solution (has memory) 372
373. iterative solution (has memory) 373
374. iterative solution (has memory) 374
375. iterative solution (has memory) 375
376. iterative solution (has memory) 376 Boards generated & ested (in red): 32 (out of 256)
377. Of the 32 boards generated, 4 are candidate solution boards. 377
378. iterative solution (has memory) Boards generated & ested (in red): 32 (out of 256) 378
379. iterative solution (has memory) Candidate boards generated & tested in pink): 4 379
380. Algorithm without isSafe function with isSafe function Boards Generated (All of them candidate solutions) Boards Generated Candidate Boards Generated Recursive 256 (44) 60 16 Iterative 24 (4!) 32 4 N=4; 2 solutions 380
381. 381 Algorithm without isSafe function with isSafe function Boards Generated (All of them candidate solutions) Boards Generated Candidate Boards Generated Recursive 3,125 (55) 220 60 Iterative 120 (5!) 101 12 N=5; 10 solutions Algorithm without isSafe function with isSafe function Boards Generated (All of them candidate solutions) Boards Generated Candidate Boards Generated Recursive 46,656 (66) 893 240 Iterative 720 (6!) 356 40 N=6; 4 solutions
382. 382 Algorithm without isSafe function with isSafe function Boards Generated (All of them candidate solutions) Boards Generated Candidate Boards Generated Recursive 823,543 (77) 3,581 657 Iterative 5,040 (7!) 1,344 93 N=7; 40 solutions Algorithm without isSafe function with isSafe function Boards Generated (All of them candidate solutions) Boards Generated Candidate Boards Generated Recursive 16,777,216 (88) 15,718 2,495 Iterative 40,320 (8!) 5,506 312 N=8; 92 solutions
383. Without using isSafe function 𝑁! 𝑁𝑁 383
384. Using isSafe function 384
385. Using isSafe function 385