• Choose a category
• All
• Classic-Fiction

By Root 476 0

and an old lady comes up to you and says, “Excuse me, what’s the first natural number such that the sum of its digits equals 40?”

Well, what now, hotshot? Let’s use some Has-kell magic to find such a number. For instance, if we sum the digits of the number 123, we get 6, because 1 + 2 + 3 equals 6. So, what is the first number that has such a property that its digits add up to 40?

First, let’s make a function that takes a number and tells us the sum of its digits. We’re going to use a cool trick here. First, we’ll convert our number to a string by using the show function. Once we have a string, we’ll turn each character in that string into a number and then just sum that list of numbers. To turn a character into a number, we’ll use a handy function from Data.Char called digitToInt. It takes a Char and returns an Int:

ghci> digitToInt '2'

2

ghci> digitToInt 'F'

15

ghci> digitToInt 'z'

*** Exception: Char.digitToInt: not a digit 'z'

It works on the characters in the range from '0' to '9' and from 'A' to 'F' (they can also be in lowercase).

Here’s our function that takes a number and returns the sum of its digits:

import Data.Char

import Data.List

digitSum :: Int -> Int

digitSum = sum . map digitToInt . show

We convert it to a string, map digitToInt over that string, and then sum the resulting list of numbers.

Now we need to find the first natural number such that when we apply digitSum to it, we get 40 as the result. To do that, we’ll use the find function, which resides in Data.List. It takes a predicate and a list and returns the first element of the list that matches the predicate. However, it has a rather peculiar type declaration:

ghci> :t find

find :: (a -> Bool) -> [a] -> Maybe a

The first parameter is a predicate, and the second parameter is a list—no big deal here. But what about the return value? It says Maybe a. That’s a type you haven’t met before. A value with a type of Maybe a is sort of like a list of type [a]. Whereas a list can have zero, one, or many elements, a Maybe a typed value can have either zero elements or just one element. We use it when we want to represent possible failure. To make a value that holds nothing, we just use Nothing. This is analogous to the empty list. To construct a value that holds something, say the string "hey", we write Just "hey". Here’s a quick demonstration:

ghci> Nothing

Nothing

ghci> Just "hey"

Just "hey"

ghci> Just 3

Just 3

ghci> :t Just "hey"

Just "hey" :: Maybe [Char]

ghci> :t Just True

Just True :: Maybe Bool

As you can see, a value of Just True has a type of Maybe Bool, kind of like how a list that holds Booleans would have a type of [Bool].

If find finds an element that satisfies the predicate, it will return that element wrapped in a Just. If it doesn’t, it will return a Nothing:

ghci> find (> 4) [3,4,5,6,7]

Just 5

ghci> find odd [2,4,6,8,9]

Just 9

ghci> find (=='z') "mjolnir"

Nothing

Now let’s get back to making our function. We have our digitSum function and know how find works, so all that’s left to do is put these two together. Remember that we want to find the first number whose digits add up to 40.

firstTo40 :: Maybe Int

firstTo40 = find (\x -> digitSum x == 40) [1..]

We just take the infinite list [1..], and then find the first number whose digitSum is 40.

ghci> firstTo40

Just 49999

There’s our answer! If we want to make a more general function that is not fixed on 40 but takes our desired sum as the parameter, we can change it like so:

firstTo :: Int -> Maybe Int

firstTo n = find (\x -> digitSum x == n) [1..]

Here’s a quick test:

ghci> firstTo 27

Just 999

ghci> firstTo 1

Just 1

ghci> firstTo 13

Just 49

Mapping Keys to Values

When dealing with data in some sort of collection, we often don’t care if it’s in some kind of order; we just want to be able to access it by a certain key. For example, if we want to know who lives at a certain address, we want to look up the name based on the address. When doing such things, we say that we looked up our desired value (someone’s name) by some sort of key (that