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