Haskell Data Structure

Question

I am trying to build a data-structure in Haskell which functions can use to avoid re-computing values. For example, say I had the function:

f :: Int -> Int -> Int
f 1 1 == 1
f m n
    | abs m > n = 0
    | OTHERWISE if value of f m n has already been computed by another recursive branch, return that value and add it to the "database"
    | OTHERWISE return f (m-1) (n-1) + f (m - 1) n

I have already looked at memoization, but haven't been able to implement a solution :\

Suggestions? :)

josejuan · Accepted Answer · 2014-05-13 11:27:18Z

5

A great explanation is here.

I love memoize package :)

Example (solving the "A frog is jumping up the staircase..." problem):

import Data.Function.Memoize 

ladder :: Integer -> Integer -> Integer 
ladder n k = g n 
  where g = memoize f 
        f 0 = 1 
        f x = sum [g (x - y) | y <- [1..if x < k then x else k]]

answered May 13, 2014 at 11:27

josejuan

9,60628 silver badges33 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Dario Over a year ago

Hi @josesuan, thanks, unfortunately this is my problem, I had come across similar examples, but struggling to understand how it actually works. (In particular, the last line)

Collectives™ on Stack Overflow

Haskell Data Structure

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related