My previous post was about how I learned about Unicode because there was a section in Real World Haskell which implemented the encoding in a real deep down way. After a couple more chapters, I had to ditch that book because of its sheer size. I want to be a bit more versed with how to think in Haskell and then possibly I will tackle the book once again.

Querying on the internet, I came across the recommendation of BiteMyApp’s Chris Allen, who says it is better to start with UPenn’ CIS 194. I have already read a fair amount of theory by reading LYAH (which is an excellent book but lacks both real world examples and exercises) and Programming in Haskell which has exercises but is terse, cold, and glosses over almost all of the concepts. I would not recommend that as a first Haskell book.

I have started with CIS-194 and so far I have completed 5 weeks of lectures and exercises and I can say that some of the exercises really are tough. Especially the week 5 exercise where we are supposed to make a calculator.

It starts from being a simple typeclass which adds and multiplies two numbers to a compiler for a calculator VM to one which allows to plug local variables in expressions. All this using a 1-2 typeclasses and with expressions so clear that it feels like magic.

For instance, this is what we start with:

A simple typeclass which just adds and multiplies:

1
2
3
4

class Expr a where
  lit :: Integer -> a
  add :: a -> a -> a
  mul :: a -> a -> a

Here’s the instance for Integer:

1
2
3
4

instance Expr Integer where
  lit n = n
  add x y = x + y
  mul x y = x * y

Here’s one which works a similar way on Bool:

1
2
3
4
5
6

instance Expr Bool where
  lit n
    | n <= 0 = False
    | otherwise = True
  add x y = x || y
  mul x y = x && y

The next step is to create an instance which allows us to send expressions over to a stack based VM.

The expression may contain one binary operator and 2 operands. The VM takes out the operator and applies that to the next 2 operands on the stack.

1
2
3
4
5
6
7

instance Expr Program where
  lit n = [PushI n]
  add x y = x ++ y ++ [Add]
  mul x y = x ++ y ++ [Mul]

> stackVM [PushI 12, PushI 13, Mul]
Right (IVal 156)

And the last one is about using the expression which contains local variables:

1
2

> withVars [("x", 6), ("y", 3)] $ mul (var "x") (add (var "y") (var "x"))
Just 54

The last one was tricky and it took around 40-50 minutes to come up with a solution – I wasted a lot of time looking at the screen. When I put pen to paper and tried to come up with the solution to parse and pattern match the given expression, I had an aha moment and solution appeared on the paper:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

-- Provided as part of the exercise.
withVars :: [(String, Integer)]
         -> (M.Map String Integer -> Maybe Integer)
         -> Maybe Integer
withVars vs exp = exp $ M.fromList vs

instance HasVars (M.Map String Integer -> Maybe Integer) where
  var s = M.lookup s

instance Expr (M.Map String Integer -> Maybe Integer) where
  lit n   = (\_ -> Just n)
  add x y = \vs -> case (x vs, y vs) of
    (Just n, Just m) -> Just (n + m)
    otherwise -> Nothing
  mul x y = \vs -> case (x vs, y vs) of
    (Just n, Just m) -> Just (n * m)
    otherwise -> Nothing

It certainly looks easy now, but at the time I was so slow that I was almost crawling towards the solution. Especially because I was a bit uncomfortable with the type (M.Map String Integer -> Maybe Integer) and then how to use this type in the add=/=mul clauses. Even the lit clause took a bit of time because I kept thinking about and looking at n. The signature of lit is Integer -> a and I was thinking wrongly of how to return a monster like (M.Map String Integer -> Maybe Integer) from an Integer. Turned out, since these expressions are used later in another function withVars, which uses the expression and pass it a Data.Map, I can pass function which takes this list and works accordingly with it.

This was a remarkable exercise which forced me to think at a high level – the pattern matches, so use it instead of coming up with hacks of how to parse the expression and then use it. Add to that the syntax is so low on noise, it just looks sooo good.

The way I see it, since Haskell demands recursion, it becomes easier to think about and use the concept of pattern matching – which is an inherently recursive construct. Although almost all of the last few weeks’ exercises would look same in Python since it natively supports minimal syntax, first class functions, and list comprehensions, no doubt if I was trying to implement this week’s exercises in Python it would be huge and messy since pattern matching isn’t part of the language.

Now to mess my head some more. Onto week 6.

PS: The solutions are available here.