How to return a list of lists as single lists?

Question

I keep running into this weird roadblock when trying to use list comprehensions when trying to call on helper functions, and I'm unsure if I'm using the wrong tool for the job or I'm just missing a bit of syntax. My latest example:

    partition :: Int -> [[Int]]
    partition n = [pH n x []|x<-[n-1, n-2..1]]
        where
            pH :: Int -> Int -> [Int] -> [Int]
            pH _ 0 xs = []
            pH n x xs
                | sum xs == n = xs
                | x+sum xs == n = x:xs
                | otherwise = [x:pH n z xs|z<-[n-x,n-x-1..1]]

This won't work because pH is supposed to return a list and the last line returns a list of lists. What I really want to do is to recursively make several calls on the pH function over a parametrized variable.

So, am I just missing a simple tool, or is my whole logic flawed here?

Answer 1

You can enumerate over the recursive part as well:

partition :: Int -> [[Int]]
partition n = [ts | x <- [n - 1, n - 2 .. 1], ts <- pH n x []]
  where
    pH :: Int -> Int -> [Int] -> [[Int]]
    pH _ 0 xs = []
    pH n x xs
      | sum xs == n = [xs]
      | x + sum xs == n = [x : xs]
      | otherwise = [ ts | z <- [n - x, n - x - 1 .. 1], ts <- pH n z (z:xs)]

But this gets stuck in an infinite loop, and probably also branches too much.

I think what we can do is try to generate solutions the other way around. We can each time determine what the sum of the remaining elements should be, and thus generate a list with that:

partition :: Int -> [[Int]]
partition 0 = [[]]
partition n | n < 0 = []
partition n = [(x : xs) | x <- [n, n - 1 .. 1], xs <- partition (n - x)]

This can be boosted significantly with a memoize pattern.