[Haskell-cafe] List algorithm

[haskell at list.mightyreason.com]

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]]