Wakatta!

Like Eureka!, only cooler

Seven Languages in Seven Weeks Haskell Day 3

Last day with Haskell, and this time we grapple with classes and monads. That’s pretty much where most beginners give up in disgust…

And that’s too bad, because both (and the rest of advanced Haskell features) are very expressive (see below the Maze problem) and powerful. But classes are unusual (and the name tends to confuse Object Oriented people), while monads appear to solve a problem that is trivial in other languages (which is not true, or mostly not true).

Classes

Classes are more properly understood as interfaces, but the comparison can be misleading. Class elements are types that are guaranteed to provide implementation for specific functions. Combined with polymorphism, it allows writing functions that are more intimate with their arguments, while keeping purity and referential transparency (in some sense, it plays a role similar to functors in ML languages).

Classes nicely support monads (and other composition mechanisms) by providing interfaces these abstractions can build upon.

Monads

Monads are mechanisms to compose calculations. They also happen to solve the IO problem in Haskell, which is a nice (and significant) bonus. But the calculation composition is core. With it, one can have backtracking, continuation, probabilistic computing, anything you could think off. Thinking of anything actually is quite hard, as most programmers are not used to such freedom. For IO, it just happens to guarantee sequential evaluation.

There are a number of resources to learn about Monads (indeed, it seems the path to Haskell mastery must include writing at least one Monad tutorial). I found All About Monads very useful. The introduction is really good, but links to this tutorial tend to disappear, unfortunately. There is also the Monads chapter of Real World Haskell (which you should read, but wait for the second edition to buy). This introduction is more complex, as it builds a State Monad rather than the Maybe Monad.

Finally, A Fistful of Monads from Learn You a Haskell for Great Good also covers the Maybe Monad as an introduction. I have the book but did not read it yet, so I cannot comment on it, but I have seen great reviews.

Exercises

Lookup function returning Maybe

The function my_lookup is easy; it iterates over a list of pairs key, value, and returns Just value when the key matches. On empty list, it returns Nothing. There is no need to think about monads at this point. A key,value map is really some data structure that Maybe contains a specific key.

Slightly more difficult was the testData. The nesting was somewhat tricky to get right.

(lookup.hs) download
1
2
3
4
5
6
7
8
module Lookup where

my_lookup key [] = Nothing
my_lookup key ((k, value):rest)
  | key == k  = Just value
  | otherwise = lookup key rest

testData = [(1, []), (2, [("a", [("i", "tada!")]), ("b", [("j", "nope")])]), (3, [("c", [("k", "tada!")])])]

Once this is defined, using it with the >>= operator is really simple:

1
2
3
4
*Lookup> my_lookup 2 testData >>= my_lookup "a" >>= my_lookup "i"
Just "tada!"
*Lookup> my_lookup 2 testData >>= my_lookup "b" >>= my_lookup "i"
Nothing

Solving Maze

Using the List Monad to solve problems is very similar to using Prolog: elements in a list are alternative paths; failure (which must be explicit by calling fail or guard) backtracks to the next alternative; [return] adds a solution to the list of solutions (even if there’s only one possible solution, the List Monad produces a list).

To solve the maze, the algorithm do the following:

  • the loop subfunction is used to explore a given solution; the List Monad hides the iteration and backtracking over alternatives
  • the loop function is always called with the reverse path so far: the first element is actually the current position
  • if the current position is the exit position, the path is reversed then returned as solution
  • otherwise, the current node is checked, and its exits retrieved
  • the positions in the path are first removed from the exits, to avoid looping (so we never go over the same position twice)
  • the List Monad main logic starts there:
    • first guard that the list of possible exits is not empty
    • then select and alternative new position
    • call loop on the new path to explore it

The code is fairly short, and perhaps could be shorter. The backtracking is provided for free by the List Monad, but very effective to implement a search (I used it to solve Sudoku problems).

To be fair, I took some time to track a bug: instead of adding the whole current path to the recursive loop call, I only passed the tail. That caused loop to actually ignore the current path, and run in circle forever. Once fixed, the search was instantaneous.

(maze.hs) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
module Maze where

import Data.List
import Control.Monad

-- a Maze is an array of Node
type Maze = [[Node]]

-- each node can have a number of exits (indicated by locations in the Maze)
data Node = Exits [(Int, Int)]
  deriving (Show)

-- solve a maze using List monad:
-- 
solveMaze :: Maze -> (Int, Int) -> (Int, Int)-> Maybe [(Int, Int)]
solveMaze m pos (e1, e2) =
  case loop [pos] of
    [] -> Nothing
    (p:_) -> Just $ p
  where
    loop path@((i, j):_) =
      if i == e1 && j == e2
      then return $ reverse path
      else
        let (Exits exits) = ((m !! i) !! j)
            poss = exits \\ path
        in do guard (not $ null poss)
              pos <- poss
              loop (pos:path)

-- the problem is parsed by looking at characters around
-- every even position (position with even x and y)
-- if the character in a direction is a space, there's an exit
parseMaze :: [String] -> Maze
parseMaze raw =
  let rows = floor $ (fromIntegral $ length raw) / 2
      cols = floor $ (fromIntegral $ length $ head raw) / 2
  in [[makeNode i j | j <- [1..cols]] | i <- [1..rows]]
 where
  makeNode i j = Exits $ concatMap (makeExit i j)
                           [(-1,0), (0,1), (1,0), (0,-1) ]
  makeExit i j (y, x) = if (raw !! (2*i + y - 1) !! (2*j + x - 1)) == ' '
                        then [(i+y-1, j+x-1)]
                        else []

data Problem = Prob (Int, Int) (Int, Int) [String]
  deriving (Show)

-- updateAt runs an update function on the nth element in a list
-- keeps the rest
updateAt n f ls =
  case splitAt n ls of
    (pre, (u:rest)) -> pre ++ ((f u):rest)

-- update the prob description with path iteratively
displaySol prob sol =
  foldl' update prob sol
 where
  update prob (i,j) = updateAt (2*i+1) (updateAt (2*j+1) (const '*')) prob

solveProblem :: FilePath -> IO ()
solveProblem f =
  do (Prob start end prob) <- readProblem f
     let maze   = parseMaze prob
     case solveMaze maze start end of
       Just sol -> putStrLn $ unlines $ displaySol prob sol
       Nothing  -> putStrLn "no solution found"

-- special code for sample mazes from
-- http://benjamin-meyer.blogspot.com/2005/01/ascii-maze-ment-puzzle.html
readProblem :: FilePath -> IO Problem
readProblem f =
  do raw <- readFile f
     let filtered = case filterMaze raw of
                      (l:ls) -> ((init $ init l):ls)
         (i, j) = (length filtered, length (head filtered))
     return $ Prob ((i `div` 2) - 1, 0) (0, (j `div` 2) - 1) filtered

splitAtEvery :: Int -> [a] -> [[a]]
splitAtEvery _ [] = []
splitAtEvery n ls =
  case splitAt n ls of
    (pre, rest) -> pre:splitAtEvery n rest

removeExtraSpaces (l:ls) = l:(concatMap tail $ splitAtEvery 3 ls)

filterMaze = map removeExtraSpaces . map (drop 5) . lines

The rest of the code includes a parser for a specific maze description (I found sample mazes here), and code to process a problem into a Maze instance, and code to display a solution.

Testing (test data here):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
*Maze> solveProblem "input1.txt"
 ___________________
|   | |   |        *|
| __| | __|___  __  |
|   | |       |   |*|
| __| |_____  |_  | |
|   | | | |       |*|
| __| | | |_______| |
|            * * * *|
| __________  __    |
| |   |    * *| | | |
|_|   |___  __| | |_|
|   |     |*| | | | |
|_  |_    | | | |_| |
|   |   |  *|       |
| __|_  |_  | __    |
| |     |  * *| | | |
|_| __  | __  | |_|_|
| |   | | |  *  |   |
| |   | |_|_  __|_  |
|   | | |   |* *  | |
| __|_| | __|_    | |
| | |   |  * * *|   |
|_| | __|_  __  |___|
| | |     |*| | |   |
| | | ____| | |_|_  |
|   | |* * *        |
|_  |_|   __  ______|
|    * *| |     |   |
|     __| |_  __| __|
| | |*  |   |   |   |
| |_| __|___|___|_  |
|   |* *|     |     |
|___|   |   __| ____|
|   | |* *|     |   |
| __|_|_  |     | __|
|       |*| | |     |
|_____  | |_| |_  __|
|* * *|  *|     |   |
|     |_  | __  |   |
|*| |* * *|   | | | |
|_|_|_____|___|_|_|_|

Wrapping up Day 3 and Haskell

The exercises (ok, just the maze one) were challenging and show or at least hint at Haskell strength: the ability to compose calculations from basic elements and add advanced control mechanisms almost transparently.

I enjoy Haskell; it allows to think at a higher level, to see computations from different angles, in a way that expands the mind (sometimes painfully). And while it is certainly not mainstream, there are high quality niches (banking and financial companies) that justify investing (stupid pun intended) in Haskell.

Comments