Haskell Store Data As Algorithm progresses

Question

Say I had a Haskell algorithm which, through recursion, progressed through a Cartesian plane where each x/y coordinate had a specific value.

Position (0,0) is known, each other can be calculated by progressing back to the origin.

For example, to look at (0,3) I need to look at (-1,2), (0,2) and (1,2), which have to look in turn at (-2,1),(-1,1),(0,1) and (-1,1),(0,1),(1,1) and (0,1),(1,1),(2,1) respectively.

In order to avoid for (-1,1) and (0,1) to be calculated twice, is there any way I can create a data structure so that the algorithm can first look to see if a certain position ahs been calculated already and, if not, only then proceeds to calculating it?

Thanks :)

instead of creating explicitly a data structure, try using memoization (googlable and many questions here on SO about it). — m09
– m09, Commented May 8, 2014 at 14:21
Memoization sounds right here, in particular take a look at memo-tries on Hackage. — cdk
– cdk, Commented May 8, 2014 at 14:58

jberryman · Accepted Answer · 2014-05-08 18:18:13Z

It sounds like memoization as m09 and cdk suggest might be what you're looking for. But if you want an algorithm that returns an array of positions, then simple boxed arrays (meaning they hold lazy values) and some knot tying can give you a nice declarative solution (sorry for the ugly code)

import Data.Array

-- for positive u
plane :: Int -> Array (Int,Int) Int
plane u = let knownOrigin = ((0,0) , 0)
              l = negate u
              otherCoords = [ (x,y) | let cs = [l .. u] 
                                    , x <- cs , y <- cs
                                    , (x,y) /= (0,0) 
                                    ]
              a = array ((l,l),(u,u)) $
                    knownOrigin : map solution otherCoords

              -- example recursive thing, referenceing lazy values in 'a':
              solution c@(x,y) = let x' | x <0 = x+1
                                        | x >0 = x-1
                                        | x==0 = 0
                                     y' | y <0 = y+1 
                                        | y >0 = y-1
                                        | y==0 = 0
                                  in (c , a ! (x',y') + 1)
           in a

You could also use a Map or vector, or any other lazy structure that works best for your problem.

Collectives™ on Stack Overflow

Haskell Store Data As Algorithm progresses

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related