[Haskell] Can anyone help me with partition numbers?

[Tomasz Zielonka]

On Thu, Nov 24, 2005 at 05:52:23PM +0100, Jan van Eijck wrote:
> Like so: 
> 
> generatePs :: (Int,[Int]) -> [[Int]] 
> generatePs (n,[])       = [take n (repeat 1)]
> generatePs (n,(x:xs))   = 
>       (take n (repeat 1) ++ (x:xs)) : generatePs (pack (x-1) ((n+x),xs))
>   where 
>   pack :: Int -> (Int,[Int]) ->(Int,[Int])
>   pack 1 (m,xs) = (m,xs)
>   pack k (m,xs) = if k > m  then pack (k-1) (m,xs) 
>                   else           pack k     (m-k,k:xs)
> 
> parts :: Int -> [[Int]] 
> parts n | n < 1     = error "part: argument <= 0"
>         | n == 1    = [[1]]
>         | otherwise = generatePs (0,[n])

How about a shorter version?

    part :: Integer -> [[Integer]]
    part = gen 1
      where
        gen m 0 = [[]]
        gen m n = [ x:xs | x <- [m..n], xs <- gen x (n - x) ]

Best regards
Tomasz