CODEWITHSUNDEEP
haskelldynamic-programming
Dulguun Otgon
Dulguun Otgon

Reputation: 1949

Memoizing `map f` calls

I understand how this memoization works

fib :: Int -> Int
fib = (map fib' [0..] !!)                 
     where fib' 1 = 1                                                        
           fib' 2 = 1                                                        
           fib' n = fib (n-2) + fib (n-1)

But how can I memoize this function which uses above function.

fibsFor :: [Int] -> [Int]
fibsFor xs = map fib xs

How to make each call for fib use a same cache?

Upvotes: 1

Views: 52

Answers (1)

Tom Ellis
Tom Ellis

Reputation: 9414

It is using the same "cache". Notice fib is never computed twice for the same argument.

import Debug.Trace

fib :: Int -> Int
fib = (map (fib' . (\i -> trace ("fib called on " ++ show i) i)) [0..] !!)
     where fib' 1 = 1
           fib' 2 = 1
           fib' n = fib (n-2) + fib (n-1)

fibsFor :: [Int] -> [Int]
fibsFor xs = map fib xs


*Main> fibsFor [5, 10, 20]
[fib called on 5
fib called on 3
fib called on 1
fib called on 2
fib called on 4
5,fib called on 10
fib called on 8
fib called on 6
fib called on 7
fib called on 9
55,fib called on 20
fib called on 18
fib called on 16
fib called on 14
fib called on 12
fib called on 11
fib called on 13
fib called on 15
fib called on 17
fib called on 19
6765]

Upvotes: 2

Related Questions