Matthew Brecknell wrote:
Mark T.B. Carroll:
algMemo n m = last memo where memo = [[]] : map helper [1 .. m] helper m' = [ x : xs | x <- [1 .. min m' n], xs <- memo !! (m' - x) ]
This made me wonder whether it's safe to access an array while it's still under construction:
import Data.Array.IArray
algArr n m = memo ! m where memo :: Array Int [[Int]] memo = listArray (0,m) $ [[]] : map helper [1..m] helper i = [ x:xs | x <- [1..min i n], xs <- memo ! (i-x) ]
This seems to work, but presumably only because it's a boxed array, and the construction makes no circular references.
However, I'm doubtful that memoisation is really beneficial in this function. I think it only gains a constant-factor speedup, but loses the ability to work in constant space.
If you call this function many times you may want to keep (some of) the memo table between calls: m'store,m'store'temp :: Int m'store = 4 m'store'temp = 10 m'arr :: Array Int [[Int]] m'arr = listArray (0,m'store) $ [[]] : map helper [1..m'store] where helper i = [ x:xs | x <- [1..i], xs <- m'arr ! (i-x) ] alg :: Int -> Int -> [[Int]] alg _n m | m < 0 = error "alg: Cannot total to negative" alg n m = if m > m'store'temp then [ x : xs | x <- [1..min n m], xs <- alg n (m-x) ] else let cached = if m <= m'store then m'arr ! m else m'temp ! m in if n >= m then cached else filter (all (<=n)) cached where bound = (succ m'store, min m m'store'temp) m'temp :: Array Int [[Int]] m'temp = listArray bound (map help (range bound)) help i = [ x : xs | x <- [1..min n i], xs <- alg i (m-i) ] The above uses some space for the global memo table m'arr and for a given call may use additional space for m'temp. For m larger than m'store'temp it will not allocate a memo table will run slower (but without consuming so much space). *Main> alg 6 5 [[1,1,1,1,1],[1,1,1,2],[1,1,2,1],[1,1,3],[1,2,1,1],[1,2,2],[1,3,1],[1,4],[2,1,1,1],[2,1,2],[2,2,1],[2,3],[3,1,1],[3,2],[4,1],[5]]