dp.hs

module Main where
import Data.Map.Strict as Map
import Data.Vector as Vec


-- The recursive step

rec :: (Int -> [[Int]]) -> Int -> [[Int]]
rec rec n = do
    this <- [1..n]
    other <- rec (n - this)
    return $ (this : other)

-- Non-dynamic

sumsTo1 :: Int -> [[Int]]
sumsTo1 0 = [[]]
sumsTo1 n = rec sumsTo1 n

-- Dynamic (corecursive)

sumsTo2 :: Int -> [[Int]]
sumsTo2 n = lookup Map.! n
    where
    lookup = go 1 (Map.singleton 0 [[]])
    go m acc | m > n = acc
             | otherwise = go (m + 1) (Map.insert m (rec (acc Map.!) m) acc)

-- Dynamic (lazy)

sumsTo3 :: Int -> [[Int]]
sumsTo3 n = lookup Vec.! n
    where
    lookup = generate (n + 1) $ \m -> 
        if m == 0 
        then [[]] 
        else rec (lookup Vec.!) m

main = do
    let a = sumsTo1 10
        b = sumsTo2 10
        c = sumsTo3 10
    print (a == b && b == c)
    print a