How do you avoid recalculations with pure functions in Haskell?

Xyne · 2009-12-21 19:40:03

Let's say that I have a pure function, f, which thus gives the same result for the same input in all cases. Let's also say that the function takes a while to compute the result (e.g. a list of binomial coefficients for some large number n).

Is there a way to get (GHC) Haskell to cache previously computed values of that function for different inputs so that subsequent calls with the same input will not require recalculation?

For example, in Python or Perl I could create a hash/dictionary and have a function check if a value already exists for the given input. If it does, that value would be returned without further calculation. If not, it would be calculated, stored in the dictionary for future calls, and then returned.

I am also very new to Haskell (read: noob) and functional programming so maybe the very question itself shows that I'm not thinking about this the right way.

Thanks in advance.

Cyrusm · 2009-12-21 20:10:44

I'm pretty new to haskell myself, but I would think the best way to go about things is create a list of 2 element tuples
say [(input,output),(input,output),...]. since we know that a given input will always output the same value (yay haskell) I would
design the algorithm such that it takes the input, searches the list for an output corresponding to that input, and if it does not exist in the list, calculate the output and append the resulting tuple to the list. I imagine this will increase the overall efficiency of the program, but will cost you efficiency in calculating never before calculated values.
this is of course assuming that the algorithm to search the list has less time complexity than the actual calculation algorithm.

there may be a better data structure in haskell for this, but I'm pretty sure this should work.

Last edited by Cyrusm (2009-12-21 20:15:41)

tavianator · 2009-12-21 20:19:28

http://www.haskell.org/haskellwiki/Memoization gives a few ideas. I'm pretty new with Haskell myself, so no guarantees.

jac · 2009-12-21 21:32:52

I'm just learning haskell too, and was looking for something exactly like this. That link tavianator gave gives a wonderful example, I'm glad the fibonacci sequence is one such thing that can benefit so easily. Thank you tavianator!

Xyne · 2009-12-21 22:24:07

@Cyrusm
The cost of calculating the value when first needed is unavoidable so that's a non-issue. As for a better data structure, I remember reading about hash/dictionary implementations in Haskell and I think the recommendation was to use binary trees as they allow more efficient lookups. *edit* as compared to lists of 2-tuples

I'll keep the idea in mind but ideally I would want to avoid passing around and updating data structures. I suspect that such a solution would be considered "unfunctional" by experienced functional programmers and I'm trying to mold my mind into that paradigm. Still, if it proves to be the most efficient solution then of course I will use it.

Thanks.

@tavianator
That link has given me some ideas. Thanks.

Last edited by Xyne (2009-12-22 01:23:52)

SoleSoul · 2009-12-21 22:43:06

Another Haskell learner here.
Here is the standard Haskell hash table: http://learnyouahaskell.com/modules#data-map
At least I think it is.

tavianator · 2009-12-21 23:53:55

jac: You're welcome. But fibonacci is a contrived example, as there's an algorithm which is just as fast but has bounded memory use. Simply calculate from the bottom up, rather than the top down. Wikipedia says it best.

On the other hand, memoization with a good data structure (i.e. a hash table, not a binary tree) can have better amortized performance because calculating a Fibonacci number which has been previously calculated is an O(1) operation. So calculating the first n Fibonacci numbers is O(n) with memoization, and O(n^2) with the bottom-up algorithm. Calculating n random Fibonacci numbers is still O(n^2) with memoization though.

Last edited by tavianator (2009-12-22 00:27:28)

Arch Linux

#1 2009-12-21 19:40:03

How do you avoid recalculations with pure functions in Haskell?

#2 2009-12-21 20:10:44

Re: How do you avoid recalculations with pure functions in Haskell?

#3 2009-12-21 20:19:28

Re: How do you avoid recalculations with pure functions in Haskell?

#4 2009-12-21 21:32:52

Re: How do you avoid recalculations with pure functions in Haskell?

#5 2009-12-21 22:24:07

Re: How do you avoid recalculations with pure functions in Haskell?

#6 2009-12-21 22:43:06

Re: How do you avoid recalculations with pure functions in Haskell?

#7 2009-12-21 23:53:55

Re: How do you avoid recalculations with pure functions in Haskell?

Board footer