by Nicolas Wu

Posted on 19 August 2010

This week, our Project Euler puzzle is:

Discover the largest product of five consecutive digits in the 1000-digit number.

The number we’ve been given is 1000 digits long, so rather than writing this number as an `Integer`

, it’s easier to express it as a string first (since the formatting looks better for this post), and to convert it to something more sensible afterwards.

To do that, we’ll be making use of an external module, called `Data.Char`

, which exports a function, `digitToInt`

, that converts between values of type `Char`

and `Int`

. Module imports in Haskell must come before function definitions, so we’ll put the import line right here:

```
> import Data.Char (digitToInt)
> import Data.List (tails)
```

Written as a string, the 1000 digit number we’ve been given is:

```
> num :: String
> num =
> "73167176531330624919225119674426574742355349194934\
> \96983520312774506326239578318016984801869478851843\
> \85861560789112949495459501737958331952853208805511\
> \12540698747158523863050715693290963295227443043557\
> \66896648950445244523161731856403098711121722383113\
> \62229893423380308135336276614282806444486645238749\
> \30358907296290491560440772390713810515859307960866\
> \70172427121883998797908792274921901699720888093776\
> \65727333001053367881220235421809751254540594752243\
> \52584907711670556013604839586446706324415722155397\
> \53697817977846174064955149290862569321978468622482\
> \83972241375657056057490261407972968652414535100474\
> \82166370484403199890008895243450658541227588666881\
> \16427171479924442928230863465674813919123162824586\
> \17866458359124566529476545682848912883142607690042\
> \24219022671055626321111109370544217506941658960408\
> \07198403850962455444362981230987879927244284909188\
> \84580156166097919133875499200524063689912560717606\
> \05886116467109405077541002256983155200055935729725\
> \71636269561882670428252483600823257530420752963450"
```

It really makes more sense to turn this little beast into a list of `Int`

, rather than in its current form. We’ll do this by mapping the `digitToInt`

function of `Data.Char`

onto our list `num`

:

```
> nums :: [Int]
> nums = map digitToInt num
```

Now that we have our list of integers, we can think about how we can find the product of all the sequences of consecutive digits that are 5 long.

We’ll start by first extracting all the lists that are 5 digits long. To do this, we’ll define the function `nibble`

, which takes a number `n`

, and a list `xs`

, and returns the first subsequence of `xs`

of length `n`

, paired up with the result of removing the first value in `xs`

.

```
> nibble :: Int -> [a] -> Maybe ([a], [a])
> nibble n xs
> | length xs < n = Nothing
> | otherwise = Just $ (take n xs, tail xs)
```

Since not every list `xs`

has a length greater or equal to `n`

, we use a `Maybe`

type in conjunction with our returned pair of lists.

Values of type `Maybe`

have the following defintion:

`data Maybe a = Nothing | Just a`

In other words, something of type `Maybe`

is either `Nothing`

, which contains no data, or `Just a`

which contains a value of type `a`

. In our case, the function returns `Nothing`

when no list of length `n`

can be extracted from `xs`

, and otherwise returns the first list of length `n`

, along with the nibbled rest of `xs`

.

We can use `nibble`

to define a function that produces all the subsets of `xs`

that have length `n`

. Basically, all we need is a case analysis on the result of nibbling `xs`

. If no nibble can be taken, then we simply return the empty list. However, if a nibble can be taken, then we prepend the list `ys`

of length `n`

to the front of the result of nibbling `zs`

:

```
> nibbles :: Int -> [a] -> [[a]]
> nibbles n xs = case nibble n xs of
> Nothing -> []
> Just (ys, zs) -> ys : nibbles n zs
```

The solution for our problem then becomes relatively simple. First we produce all the lists of length 5, and apply the `product`

function to each of those by using a `map`

. We get our final result by applying the `maximum`

function.

`> euler8 = maximum . map product . nibbles 5 $ nums`

Another way of obtaining the solution is to use the `tails`

function, which returns all the suffixes of a list. The `tails`

function is part of the `Data.List`

module, which we imported at the beginning of this post. As an example of its use, let’s see what tails returns for the list `[1..4]`

:

```
Prelude Data.List> tails [1..4]
[[1,2,3,4],[2,3,4],[3,4],[4],[]]
```

By using this function, we can build a different version of `nibbles'`

, where we take `n`

elements from each of the sublists of the result of tails. Since the last `n-1`

elements of the list returned will have lengths shorter than `n`

, so we reverse the list and drop those elements:

```
> nibbles' :: Int -> [a] -> [[a]]
> nibbles' n xs = drop n . reverse . map (take n) . tails $ xs
```

This function returns the reversed output of `nibbles`

, which isn’t a problem in our case, since `maximum`

is associative:

`> euler8' = maximum . map product . nibbles' 5 $ nums`

This week we’ve seen two rather different approaches to solving our problem, one using `Maybe`

types, and another using `tails`

.

`Maybe`

types capture the notion of a failed computation or an invalid result.- Function composition can give us very succinct definitions (like in our
`nibbles'`

definition).