loading...
Cover image for Haskell as Training Wheels

Haskell as Training Wheels

deciduously profile image Ben Lovy ・6 min read

I don't write a lot of Haskell. In fact, I don't really write any Haskell. My total lifetime output is well under 1000 lines. Every time I sit down to write some Haskell, though, I get reminded of why I like it so much.

Functional programming can be a tricky paradigm to get your head around, but I don't think it's fundamentally challenging. Rather, it's at odds with the instincts you've already built. Thus, when trying to program functionally in a more familiar language, it's quite easy to cheat. JavaScript is a great example. Modern JS is a great language for functional programming, but there is nothing keeping you on the rails, so to speak. You might be leaning on imperative crutches without even realizing you're doing it. Sure, you might be using reduce or newfangled stuff like flatMap all over the place, but the language itself doesn't care about how sound your code is, it will do almost anything you ask and never complain if you're breaking rules to make things easier on yourself.

Haskell forces you stay in the box. Its draconian compiler means that your code doesn't run unless you've done it right. This feels like a limitation at first, but by forcing you to solve problems functionally it...well...forces you to solve problems functionally.

What's prompting this is yesterday's Dev.to challenge:

I had a long train ride yesterday, and figured a coding challenge would be a great way to pass the time. Immediately upon reading the problem spec, I had an outline of how to solve this problem. I've been spending most of my time over the last few weeks writing either C++ or Rust, so my mental outline was very imperative. You'd traverse the string iteratively, increment a score based on markers that are present, and then adjust that score based on any extra bonuses. I'm reasonably certain this instinctive solution would have worked with a little massaging.

Where's the fun in that, though?

So, of course, I decided to whip out my dusty old Haskell compiler and see if I still knew how to drive it.

I find the most useful one-sentence summary of "functional programming" to be that instead of telling the computer how to compute the result, you just tell the computer what the result is. This can be easier said than done, and requires you to re-frame how you think about the problem.

In this specific problem, we are given a string and must return how high that string scores per Scrabble rules. There are a few curveballs - the * character is used to double or triple scores, the ^ indicates a blank so the previous letter shouldn't be scored, and words can be appended with a multiplier like hello(d) or hello(t) to signal that the final result should be doubled or tripled.

The way to frame this is to think about what a scrabble score actually is. Instead of building up the score a piece at a time, say, adding the letters one by one and then checking to see if it needs adjustment, we want an equation that will score any word. This looks something like the following:

rawScore * wordMultiplier + sevenLetterBonus

This equation fits any input - we can just default the multiplier to 1 and the bonus to 0, so that most words that don't need these get rawScore * 1 + 0, which is clearly equivalent to rawScore.

So, that's what the answer is. We just need to manipulate the string passed in so that each of these values is correctly populated by the time we get there. The simplest part is sevenLetterBonus. If the raw word is exactly 7 letters, we add 50 points. Our input string may have extra bits like the asterisk or the multiplier suffix, so just strip those to get the actual word:

stripMarkers :: String -> String
stripMarkers = filter (\c -> c /= '*' && c /= '^') $ takeWhile (/= '(')

Good. Again, this function just describes what the end result is - it's the original word up to a ( character, with the marker characters filtered out. Quite declarative. Then we can build the bonus:

sevenLetterBonus = if (length $ stripMarkers w) == 7 then 50 else 0

Perfect, this now works on any input. The multiplier, too, is easy. Some inputs will have a suffix, and if so, check which. If not, the multiplier is 1:

wordMultiplier =
    let
        suffix = dropWhile (/= '(') w
    in
        if length suffix > 0 then
            case suffix !! 1 of
                't' -> 3
                'd' -> 2
                _   -> 1
        else 1

It only looks at any part of the string after a ( character, and acts accordingly. This also already handles any string we throw at it - most will hit that else block because there is no ( present and get assigned a 1, which won't change the raw score.

The trickiest part of this for me functionally was handling the asterisks. My instincts tell me to solve this with an iterative loop, but Haskell is not going to let me get away with that. If it did, I likely would have been tempted to take the easy way out. But, of course, I couldn't.

Scoring a list of letters is easy - you just replace each letter with it's numerical value, and sum the list:

sum $ map (\c -> scores ! c) $ word

The mapping function is just performing a lookup in a mapping from characters to ints. In order for this to work, we need to have a string containing just the letters that will be scored. In order for this little snippet to work on any input, that input should be pre-processed to only contain letters. Any letter we want omitted can be, well, omitted, and letters to count multiple times can just appear multiple times. I don't know if I handled this as cleanly or as elegantly as a Haskeller would have, but this does the trick:

expandMarkers :: String -> String
expandMarkers [] = []
expandMarkers (c:[]) = [c]
expandMarkers (c:rest) =
    case head rest of
        '*' ->
            if (head $ tail rest) == '*' then
                [c] ++ [c] ++ [c] ++ (expandMarkers $ drop 2 rest) else
                [c] ++ [c] ++ (expandMarkers $ tail rest)
        '^' -> expandMarkers $ tail rest
        _ -> [c] ++ expandMarkers rest

It consumes the string recursively. On each letter, it looks one forward, and then continues the process based on what it finds. An asterisk will get removed and replaced with a copy of the letter we're on, unless the next one is also an asterisk, in which case it will replace both of them, and a carat will cause the character we're on to just not appear in the result. This function turns he*ll^o** into heelooo - ready to be scored as is via the simple character-to-int substitution.

The full code just puts all this together:

import Data.Map (Map, (!))
import qualified Data.Map as Map

scores :: Map Char Int
scores = Map.fromList pairs
    where
        pairs = [
            ('a', 1),
            ('b', 3),
            ('c', 3),
            ('d', 2),
            ('e', 1),
            ('f', 4),
            ('g', 2),
            ('h', 4),
            ('i', 1),
            ('j', 8),
            ('k', 5),
            ('l', 1),
            ('m', 3),
            ('n', 1),
            ('o', 1),
            ('p', 3),
            ('q', 10),
            ('r', 1),
            ('s', 1),
            ('t', 1),
            ('u', 1),
            ('v', 4),
            ('w', 4),
            ('x', 8),
            ('y', 4),
            ('z', 10)]

scoreWord :: String -> Int
scoreWord w =
    let
        sevenLetterBonus = if (length $ stripMarkers w) == 7 then 50 else 0
        wordMultiplier =
            let
                suffix = dropWhile (/= '(') w
            in
                if length suffix > 0 then
                    case suffix !! 1 of
                        't' -> 3
                        'd' -> 2
                        _ -> 1
                else 1
        -- 
        preparedWord = expandMarkers $ takeWhile (/= '(') w
        rawScore = sum $ map (\c -> scores ! c) $ preparedWord
    in
        rawScore * wordMultiplier + sevenLetterBonus

-- transform doubles, triples, carats
-- if we hit an asterisk, replace it with the previous letter
-- if we hit a carat, drop the previous letter
expandMarkers :: String -> String
expandMarkers [] = []
expandMarkers (c:[]) = [c]
expandMarkers (c:rest) =
    case head rest of
        '*' ->
            if (head $ tail rest) == '*' then
                [c] ++ [c] ++ [c] ++ (expandMarkers $ drop 2 rest) else
                [c] ++ [c] ++ (expandMarkers $ tail rest)
        '^' -> expandMarkers $ tail rest
        _ -> [c] ++ expandMarkers rest

-- remove suffix and all markers for deciding on the 7-letter bonus
stripMarkers :: String -> String
stripMarkers w = filter (\c -> c /= '*' && c /= '^') $ takeWhile (/= '(') w

This solution, that pre-processes every input into something that can be easily scored the same way, bears little to no resemblance to the code I wrote in my head when I read the spec. That's pretty cool, and I think it's a decent solution in any language.

That's why Haskell is worth it. In order to make it go, you cannot fall back on instinct. You have to actually solve the problem differently, and it won't work until it does. I have no delusions about this being nice, idiomatic Haskell, but it is working Haskell, which means I've come up with a working solution that I can now bring to a more familiar environment and implement. If I had sat down to write this in JavaScript instead, I would not have arrived in the same place without a lot more thought and self-discipline, because I would have just written it out how I thought about it first, and deprived myself of the experience of looking at the problem in a new way. Now the next time I approach a similar problem, my toolbox has expanded and my first instinct might actually look more like this. Thanks, Haskell!

Photo by Michal Vrba on Unsplash

Posted on by:

Discussion

markdown guide
 

My main gripe with Haskell is that IMHO there’s not enough focus on the pragmatic core of the language in the community, though admittedly that got a lot better in the last 10 or so years since I’ve been following the language. Sure, a lot of the more advanced stuff is also useful, but I’d wager that one can get quite a lot of stuff done without deeper understanding of monads or category theory. Alas a lot of the learning materials and blog posts focus more on yet another monad tutorial instead of e.g. building a web application end to end.

 

Totally agreed. Haskell is really big and powerful, and I can see the appeal for the category theory nuts, but this code, for example, doesn't use anything fancy. I'm just using GHC to verify that my code actually conforms to the paradigm, but there's nothing here that couldn't be expressed in JS.

I think there's a definite place for both communities, but beginners (like me) all too often get turned off by the slew of content that's almost entirely irrelevant. Documentation of libraries can be sparse, too, often just amounting to an enumeration of the API. It's not always clear how to start from there, but is useful as you get going.

I'd like to make a more concerted effort to use it pragmatically more often, because it really is fun to do simple things like this. The reason there's no beginner tutorials is that nobody's writing them...but the fix for that is to write 'em :)

 

I think there's a definite place for both communities

There is for sure, but alas the Real World Haskell book is getting a bit dated (it's from 2008) and is also quit long (700+ pages). What I'd like to see is something ~300ish pages that focuses on e.g. building a full web app or something like that. Anyway, I'm not writing those either (I settled on F# as my functional language of choice), so it's not for me to complain.

I like F# too. It it just doesn't quite occupy the same niche for me - it's got escape hatches, it's strictly evaluated, and it's tied to the CLR.

Spot on, though tradeoffs I’m happy to make. Escape hatches seem like a pragmatic alternative to forcing a messy outside world into purity and I never believed that laziness by default is that big a deal if a language offers it at all. Anyway, totally agreed that they’re quite different, so in the end it’s up to personal preference.

Yup. Definitely a pragmatic choice, but I specifically gravitate towards Haskell as a teaching tool. I'm glad both exist for what they are!