I wrote a solution for a very simple practice problem:
Calculate the number of grains of wheat on a chessboard given that the number on each square doubles. Write code that shows how many grains are on a given square, and the total number of grains on the chessboard.
The function must return a Maybe Integer
and return Nothing
if the input is less than 1 or greater than 64.
square :: Integer -> Maybe Integer
square n = if (n < 1 || n > 64) then Nothing else Just (2^(pred n))
total :: Integer
total = sum (fmap sum (map square [1..64]))
I tried to apply fmap sum
to some test output of map square
(list of Maybe Integer
) in GHCI and was surprised to discover it returns the list of integers (sans Just
) rather than their sum. So in the solution above I apply sum
a second time to actually get the sum.
I would like to understand conceptually why this is the case: in other words why is sum
behaving like a converter for Maybe Ints to Ints in this context instead of adding things?
I've solved some similar exercises relying on helper functions to avoid complications of doing computation on Maybe
values, and perhaps in this case I should just calculate the value of total
without utilizing square
, i.e.:
total = sum [2^n | n <- [0..63]]
However since I'd already written a useful function my first instinct was to reuse it, which led to some unforeseen behavior.
CodePudding user response:
Let's look at the type of sum
:
sum :: (Foldable t, Num a) => t a -> a
Often, for a beginner, this is simplified by assuming that t ~ []
, so that we instead use sum
as
sum :: Num a => [a] -> a
If we try to use sum
at this type in your example, we will get a type error, because you have a list of Maybe numbers, not a list of numbers. Instead you write fmap sum [Just 1]
, specializing sum
and fmap
to:
sum :: Maybe Integer -> Integer
fmap :: (Maybe Integer -> Integer) -> [Maybe Integer] -> [Integer]
So the question isn't really "why isn't sum
adding things", so much as "how can sum
have a meaningful definition when given a single Maybe Integer?"
One way to answer that question, if you're not familiar with how to interpret sum
as working on Foldable
or how Maybe
is foldable, is to just try implementing it yourself. There's really only one reasonable implementation:
sum :: Maybe Integer -> Integer
sum Nothing = 0
sum (Just x) = x
Right? Someone asked you "what's the total of the numbers in here", and then gave you either zero or one number. Pretty easy to add up. That's exactly how sum
works for Maybe, except that it goes through Foldable instead of being specialized to Maybe.
After this, of course it's easy: you've turned your [Maybe Integer]
into an [Integer]
, and of course sum
ming that gets you the sum of the non-Nothing
entries.
CodePudding user response:
Let's look at an example.
map square [0..2] = [Nothing, Just 1, Just 2]
fmap sum (map square [0..2]) = [sum Nothing, sum (Just 1), sum (Just 2)]
Since Maybe
is a Foldable
container, it makes sense to calculate the sum of its elements:
sum Nothing = 0
sum (Just a) = a
So
fmap sum (map square [0..2]) = [0, 1, 2]
Now I don't know what you were actually hoping to do with the Maybe
s, but this is why you got what you got.
CodePudding user response:
One thing worth internalising; when you map a function over a list1, the result is always going to be a list with the same number of elements. The function will be applied to each element of the list individually; it cannot combine them into a single summary value. That's just not what fmap
does.
So with that principle in mind, we know that fmap sum squares
(where squares = map square [1..64]
) cannot possibly result in the sum of squares
. It's going to be [ sum (square 1), sum (square 2), ... , sum (square 64) ]
. We will then need to apply sum
again to that whole list, if we want to actually add them up.
That just leaves an explanation for what sum (square 1)
etc is actually doing (i.e. what sum
does when applied to Maybe
values). The proper type for sum
is sum :: (Foldable t, Num a) => t a -> a
. Foldable
is basically the type-class of structures that you can scan for 0 or more elements in order (essentially: those you can convert to a list). All sum
does is add up the elements that are there, however many there are (and use 0
as a "starting value" in case there are no elements). Maybe
has a Foldable
instance; it always has 0 or 1 elements, and sum
can add those up just as well as it can add up lists that happen to have only 0 or 1 elements.
Of course the effect of summing zero-or-one numbers is just that the result is 0 if there were zero inputs and equal the input number if there was one.
never actually gets called for this "sum", which makes it feel a little pointless. But sum
didn't know that; it works for any Foldable
, regardless of how many elements they contain. And Maybe
didn't know that it would end up being used to "sum without actually adding"; it just implemented Foldable
so that any other function that wants to scan a variable number of elements out of a structure can scan Maybe
s.
If you think it's silly, just don't use sum
for that job; use fromMaybe 0
instead.
1 You can generalise this to other functors beyond lists; when you fmap
a function over a data structure, the result will have exactly the same structure as the input. Only the "leaf nodes" will be different.