[Haskell-cafe] List algorithm
haskell at list.mightyreason.com
haskell at list.mightyreason.com
Tue May 22 08:52:57 EDT 2007
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]]
More information about the Haskell-Cafe
mailing list