Skip to content

Instantly share code, notes, and snippets.

@wyager

wyager/dp.hs

Created May 18, 2019
Embed
What would you like to do?
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.