[Haskell-cafe] List algorithm

[Matthew Brecknell]

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.