# "Haskell": 17 Points in Scrabble™

This has been in my `_drafts` directory for months and now that I re-read it, it seems trivial, but it’s time to start good habits and just post things instead of feeling like it’s inadequate.

I’ve been in the process of learning Haskell for a while now, but only recently have gotten to a point where I feel like I know enough to actually do anything with it. While laying in bed, I was thinking of things I could write that would be easy, but not too easy and decided a simple little program to find all the possible word combinations given a set of Scrabble™ tiles would be a good start, and also a good way to demonstrate how concise Haskell code can be.

## The Problem

The problem at hand is a good one for learning, particularly because it involves a problem that nearly everyone has faced while playing Scrabble™ and can easily be reasoned about in your head.

Given a set of tiles, find all combinations of valid Scrabble™ words that can be played

We’ll ignore the possibility of appending tiles to existing words for now and just focus on finding possibilities from a dictionary. I used this Scrabble™ dictionary CSV from here. My first thought for how to get the job done was to make a list of possible letter combinations from the set we have, then, find the words that are common to both our list, and the dictionary. Pretty simple in our heads, but a bit of a messy process in languages like Javascript:

This code isn’t the most easily readable, and if you copy it into a file to run with node, you’ll be waiting for quite some time before it finishes. What’s more, is that this isn’t even all the word combinations that are possible - it leaves out all the combinations that don’t use all of the available letters. While it’s very possible that there’s a better algorithm for finding permutations of a string, it’s likely to be more complex and far less easy to read.

Even after getting this list of possible words, finding the intersection of the list with the Scrabble™ dictionary will be a very expensive process - given 8 letters, there are 13700 possibilities.

Lists are the bread and butter of Haskell. You use them everywhere. As such, the standard library includes lots of functions for working with them, and tasks like what we are dealing with become almost trivial.

This is the entire function for generating a list of possible combinations, given a string. It is written in what is known as point-free notation and with function composition, so if you aren’t familiar with Haskell, this version may make more sense:

First, we get a list of `subsequences` of our letter set because we don’t necessarily have to use all the letters. Then, we `map` the function `permutations` to the list of subsequences we found, and finally, `concat`enate the resulting list of lists together so we end up with a list of strings. This list is pretty big for letter sets of size 7 or 8, so it can take a while to be computed. It takes even more time to find the intersection of our dictionary unless we sort our dictionary and create a binary search tree (something that I may need to do in the future just for fun). However, at this point, I thought of a much simpler way to find the possible words and started from the beginning.

## Take Two

Instead of computing a list of all possible letter combinations, why not just go through the dictionary to see what is possible, and a real word . It’s a fairly obvious thing to do looking back, but when I first was thinking about this, it just never occured to me. So what is required to make it happen?

1. Iterate through the dictionary
2. Check if each dictionary word can be made using our letters
3. Throw away the words we can’t make

Simple right? Now before you look below here at the Haskell code, just imagine what this would look like written in Javascript, or Python, or Ruby. More than 30 lines, right? Here’s the complete Haskell code, inluding reading and parsing the Scrabble™ dictionary csv, and adding the possible scores for the returned words:

Let’s walk through the code line by line.

These are pretty self explanatory. We need some of the functions that are specific to lists in `Data.List`, the `fromJust` function exposed by `Data.Maybe`, and `Data.Map` for a map - namespaced as `M` to avoid naming collisions1.

Here is the meat of the code, we create the functions that will give us a list of all possible words. First, we’ll look at `possibleWord`. This is the check that takes a valid Scrabble™ word, and a list of our letters (`xs`), then checks if the first letter is in the Scrabble™ word2. If it is, it removes that letter from the scrabble word and repeats the process using our remaining letters that haven’t been used, and the new word (less the character we just removed). Stepwise, it looks like this:

This function is then applied to the list of possible Scrabble™ words in `possibilities`, using `filter`. This works the same as `Array.prototype.filter` in Javascript, and I’m sure most otherlanguates behave in a similar way. What makes this code nicer (in my opinion) is the use of pattern matching and not having to write for loops and explicitly declare temporary variables.

We calculate `score` for a word by folding over a word with a lambda expression that will sum the tile values, and apply `score` using `map` to all the possible words we’ve found above. On line 6, `fromJust` is the function we need to use from `Data.Maybe` and all it does is extract the value from the `Maybe Int` type returned by `M.lookup t tiles`, throwing an error if the specified tile can’t be found. When all is said and done, `scores` will be used to create a list of tuples, containing a word and its score.

Finally, we compose all of our functions together in the `main` function and output what we need. I haven’t gone to great lengths to make the output very pretty, but it gets the job done. We first read the file of possible words into a string (it contains a word on every line and nothing else), read in our tiles, then wire our functions together. It helps sometimes to read a long composition in reverse

• take the string of possible words, and split it into lines
• get everything except the last element of each line (we need to ignore the `\\n`)
• apply the possibilities filter to our list of possible words
• calculate the scores for our list of valid words
• sort by scores (the scond value of the tuple)
• output the results
• profit!

This likely isn’t the most efficient way to get the task done, but it was a great way to get a grasp on Haskells most commonly used features: pattern matching, composition (`.`), and `map` and `foldr`. I wouldn’t suggest using this in your next game of Scrabble™ though. It will run more than fast enough to work in your turn, but nobody likes a cheater.

Code can be found here.

1. Haskell has a set of default functions loaded as `Prelude`, some of which have names that will conflict with packages loaded in. We can avoid this by making an imported module `qualified`, or specifying which functions to include or exclude using syntax like `import Data.List (nub, sort)` to include `nub` and `sort`, or `import Data.List hiding (nub, sort)` to load everything except `nub` and `sort`

2. Conveniently, `Strings` and `[Char]`’s are treated the same in Haskell.