##### Day 2: `extra`

, type inference, and type classes

The next puzzle involves computing the area of the faces of a box. The equation to compute the area is provided, so the only slight complication is that the area of the smallest face needs to be added to the final answer.

```
import Data.List.Extra
-- |
-- >>> day2 "2x3x4"
-- 58
-- >>> day2 "1x1x10"
-- 43
day2 = wordsBy (== 'x')
>>> map read
>>> (\[l,w,h] -> [l*w, w*h, h*l])
>>> sort
>>> (\[x,y,z] -> 3*x + 2*y + 2*z)
```

The boxes are described by strings of the form "LxWxH", so I begin by splitting the string into three pieces using `'x'`

as the delimiter. To do this, I use `wordsBy`

, a version of `words`

which splits a string using a custom predicate to specify the delimiter characters instead of using whitespace like `words`

does. The function `words`

is in the standard library, but for some reason `wordsBy`

isn't, it's provided by the `extra`

library.

Next, I convert the resulting list of strings into a list of numbers by parsing each one using `read`

. Notice that `read`

has a rather generic name: why not `parseInt`

like in other languages? Well, it turns out that `read`

is not limited to parsing numbers. It does not look at the string it is parsing to figure out the type of the value it is parsing either. Instead, Haskell uses type inference to figure out that since we're about to multiply the parsed values together, we must want to parse the strings into numbers, and so it uses the version of `read`

which behaves like `parseInt`

. There is one such version of `read`

for each parsable type, and Haskell uses the type of the expression in which `read`

is used to figure out which implementation to use. This mechanism is called *type classes*: there is a type class called `Read`

which defines `read`

and a few other methods related to parsing, and each parsable type defines a `Read`

instance implementing `read`

and the other methods for this particular type.

As an aside, the `Monad`

interface I have briefly mentioned earlier is also a type class, with one instance per EDSL. In the case of `Monad`

, instances need to define two methods: one which constructs a computation that returns immediately without causing any side-effect (the side-effects we've seen so far include things like incrementing a counter and aborting the computation), and one which sequences two computations in such a way that the second computation can make use of the result computed by the first computation.

Anyway, once I have a list of numbers, the rest of the algorithm is straightforward: I compute the areas of the sides, I sort them so that I know which one has the smallest area, and I compute the sum of the areas, adding the smallest area 3 times instead of 2. I don't need to explain lambdas, do I? They're originally from functional languages, but all the mainstream languages have them too nowadays, same thing for higher-order functions like `map`

and `filter`

. I'm glad they did, but they shouldn't stop there: there is still more good stuff to copy :)

The full puzzle requires computing the sum of the answers for all the boxes, which is trivial and thus omitted. Day 2.5 is omitted as well, because my solution is almost the same as for Day 2.

##### Navigation

- About this series
- Previous day: monads, monad transformers, pattern-matching,

composition, laziness, and higher-order functions - Next day: 2D vectors, sets, infinite lists, lenses, and constraints

## No comments:

Post a Comment