Mark.Carroll@Aetion.com (Mark T.B. Carroll) writes:

alg n m = case signum m of -1 -> [] 0 -> [[]] 1 -> [ x : xs | x <- [1..n], xs <- alg n (m - x) ]

FWIW it's faster if you do some memoising: algMemo n m = lookupMemo m where memo = [[]] : map helper [1..m] lookupMemo m = if m < 0 then [] else memo !! m helper m' = [ x : xs | x <- [1..n], xs <- lookupMemo (m' - x) ] -- Mark

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.

Thank you for your responses. My algorithm that needs the described function performs so horribily bad that I understand now the need for CNF :-) The idea was to write a CYK-style parser for an arbitrary context-free grammar without transformation to CNF. To compute derivations for a span of length i I wanted to iterate over all productions p, counting the number n of Nonterminals at the right-hand side of p, computing all lists with n numbers whose sum is i and split the span accordingly. It works, however, the strings have to be very, very short *g* Ciao and Thx, Steffen 2007/5/22, Jules Bean :

Matthew Brecknell wrote:

...

This seems to work, but presumably only because it's a boxed array, and the construction makes no circular references.

Yes, AIUI the boxed arrays are strict in indices but lazy in values. Therefore they can be used for this kind of memoization trick as long as you're access the elements in 'some sensible order' (that is the calculation dependencies are well-ordered). _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Dipl.-Inform. Steffen Mazanek Institut für Softwaretechnologie Fakultät Informatik Universität der Bundeswehr München 85577 Neubiberg Tel: +49 (0)89 6004-2505 Fax: +49 (0)89 6004-4447 E-Mail: steffen.mazanek@unibw.de

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