Interesting puzzle in Haskell

Question

Hello studying Haskell I came up at an exercise at the web that it requested to create a list given an integer the way described below:

for example if integer was 3 then a list should be generated that it contains the following:

[[3],[1,2],[2,1],[1,1,1]]

note

3=3
1+2=3
2+1=3
1+1+1=3

if integer was 2 then it would be:

[[2],[1,1]]

I cannot think a way of implementing this, so can you provide me with any hints? I believe that I must use list comprehension but I cannot think anything further than this

Answer 1

Looks a bit like partitioning a list. A bit of googling turns up this

http://www.haskell.org/pipermail/beginners/2011-April/006832.html

partitions [] = [[]]
partitions (x:xs) = [[x]:p | p <- partitions xs]
                 ++ [(x:ys):yss | (ys:yss) <- partitions xs]

which produces something like this

*Main> partitions "abc"
[["a","b","c"],["a","bc"],["ab","c"],["abc"]]

now all you have to do is get the length of the inner lists

map (map length) (partitions "abc")
[[1,1,1],[1,2],[2,1],[3]]

you can also change partitions to give you the result directly

partitions' 0 = [[]]
partitions' n = [1:p | p <- partitions' (n-1)]
             ++ [(1+ys):yss | (ys:yss) <- partitions' (n-1)]

Answer 2

Always start with a type signature:

sums :: Int -> [[Int]]

Now, let's think about the recursion.

1. What is the base case? Can you think of a number for which the answer is trivial?
2. Let's say you've implemented your function and it works for all numbers under 10, so sums 9 for example returns the right answer. How would you implement sums 10?

Don't bother yourself with implementation details (e.g. List comprehension vs. filter and map) until you've answered these questions.

And another tip: Haskell programmers love to show off and create tiny-pointfree functions, but don't let it confuse you. Getting things to work is the important thing. It's better to have a working yet somewhat "ugly" solution than to stare at the screen looking for an elegant one.

Good luck!