Saturday, December 19, 2015

A whirlwind tour of Haskell, day 2

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: