haskell - Adding a memoization with fix? -

haskell - Adding a memoization with fix? -

trying solve task calculating count of combinations (with repetition) meet predicate, equality of elements sum given number:

countchange :: integer -> [integer] -> integer countchange n xs = fromintegral . length $ filter ((== n) . sum) $ concatmap (comb xs) [1..n] comb _ 0 = [[]] comb xs k = [y:ys | l@(y:xs') <- tails xs, ys <- comb l (k-1)]

above naive approach has important performance issue recursive phone call of comb recalculating k-1 combinations repeatedly.

i'd add together memoization of results utilize of to the lowest degree fixed point, ie. data.function.fix . i've added declaration self-recursive function, loosing ideas how implement memoize function:

countchange :: integer -> [integer] -> integer countchange n xs = fromintegral . length $ filter ((== n) . sum) $ concatmap (fix (memoize . comb) xs) [1..n] comb _ _ 0 = [[]] comb xs f k = [y:ys | l@(y:xs') <- tails xs, ys <- f (fix (memoize . comb) l (k-1))] memoize f = undefined -- ??

can set advice how solve implementation or thought quite wrong ?

when trying create memoization automatic recursion, have in recursive combinator because each recursive phone call has share "memory" (ie store memoized values).

for exemple, fibonacci sequence should write

fibo' _ 0 = 1 fibo' _ 1 = 1 fibo' _ n = (f (n-1)) + (f (n-2)) fibo = memoizingfix fibo'

where memoizingfix depends on function want memoize. general way keeping data.map in state monad may want utilize more efficient info structures less general (for illustration mutable array).

one lastly thing, when implementing memoizefix combinator, maintain in mind whether want store values 1 phone call or in current recursion. (ie : if run fibo hugevalue fibo (hugevalue + 1) sec phone call long first or immediate ?)

(note : voluntarily didn't give memoizefix combinator seems 're willing understood things , find yourself, sense free inquire - or google it, it's everywhere on net - if need.)

haskell memoization