22 May
2007
22 May
'07
2:21 a.m.
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.