This exercise shouldn't have been that challenging, but it stumped me. Here's my woeful journey with the path through it so that I can review my approach when I get stuck on the next exercise.
Found in the Purescript Book, exercise 2:
(Medium) Write a function
possibleSumswhich usesfoldMto determine all possible totals that could be made using a set of coins. The coins will be specified as an array which contains the value of each coin. Your function should have the following result:possibleSums [] [0] possibleSums [1, 2, 10] [0,1,2,3,10,11,12,13]Hint: This function can be written as a one-liner using
foldM. You might want to use thenubandsortfunctions to remove duplicates and sort the result respectively.
I wrestled with the intent of the solution. At first I thought: how are the coins selected? Did you toss the 3 coins 1, 2, and 10 and only select the ones that turned up heads? I mean, I knew that foldM would select them but I didn't understand how.
So I made my first mistake: attempting to code a problem not really understanding how foldM should be used.
First try that compiled:
> :paste
… possibleSums :: Array Int -> Array Int
… possibleSums xs = foldM (\x y -> [ x + y ]) 0 xs
…
> possibleSums [1, 2, 10]
[13]
>
The answer, 13, was missing all the other terms.
And here's where I simply couldn't figure out how to proceed for the longest time. I searched the Internet for examples of foldM using Data.Array; surprisingly didn't find any.
Even asked for help, but it was fairly late in the day and didn't get any immediate answers (fortunately). I needed to think out of the box, but couldn't figure out how.
As is usual, I woke up in the middle of the night and had the thought: let's get foldM to simply go through all the combinations it was supposed to be able to do; maybe then I could adjust the code to get the right answer. And let's do this in repl where I can get quick results and escape having type signatures (though I knew I could write PureScript coded without them).
Hence:
> :clear
Compiling Solutions
Compiling Test.Main
> foldM (\x y -> [x, y]) 0 [1, 2, 10]
Error found:
in module $PSCI
at :1:1 - 1:6 (line 1, column 1 - line 1, column 6)
Unknown value foldM
Import missing foldM and try again:
> import Data.Array
> foldM (\x y -> [x, y]) 0 [1, 2, 10]
[0,10,2,10,1,10,2,10]
>
Well, lookee there!
I betcha I can get the answer by putting x + y in one of the two positions in the array being returned by the anonymous function.
Let's see, the accumulator value, 0, is the only 0 in the returned array; that's in the left position.
I therefore need to perform the sum in the right position. Here goes:
> foldM (\x y -> [x, x + y]) 0 [1, 2, 10]
Error found:
in module $PSCI
at :1:22 - 1:23 (line 1, column 22 - line 1, column 23)
Unknown operator (+)
Aww, don't forget Prelude
> import Prelude
> foldM (\x y -> [x, x + y]) 0 [1, 2, 10]
[0,10,2,12,1,11,3,13]
>
That looks like what I'm looking for!
Clean the result up using nub and sort as recommended by the exercise. First edit the solution in my solutions file:
possibleSums :: Array Int -> Array Int
possibleSums xs = nub $ sort $ foldM (\acc i -> [ acc, acc + i ]) 0 xs(Notice that I took extra-care to rename everything as best I could.)
And in repl:
> import Solutions
> possibleSums [1, 2, 10]
[0,1,2,3,10,11,12,13]
>
And exercise accomplished.
When stuck, make the function, in this case foldM, do the most basic think you can think of. That will be likely to give you the information you're missing to solve the problem.