3

I'm trying to solve #15 from Project Euler, this is my first solution import Data.List

type Location = (Int,Int)

boardX = 20
boardY = 20

stepBack :: Location -> [Location]
stepBack (x,y) = [(x-1,y), (x,y-1)]

legalStep :: Location -> Bool
legalStep (x,y) = x >= 0 && y >= 0

iteractStep :: Int -> [[Location]]
iteractStep 0 = [[(boardX, boardY)]]
iteractStep n = [x:y|y <- iteractStep (n-1), x<- stepBack (head y),       legalStep x]

main :: IO ()
main = putStrLn $ show $ length $ iteractStep (boardX + boardY)

this is very slow, i find there are so many sub-problem re-computed, i try to memorize sub-problem answer, then i found this example:

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

i try it in ghci, i found it actually memorize sub-problem result, i can't understand how this code can memorize result, it looks like 

map fib [0 ..]

is global, but i think it is method scope (only exists at every method call), why it can memorize result?

wei li
  • 104
  • 6
  • 2
    Possible duplicate of [Memoization in Haskell?](http://stackoverflow.com/questions/3208258/memoization-in-haskell) – Marko Gresak Feb 08 '17 at 02:20

1 Answers1

2

The memoized_fib works because it initially just creates a thunk out of map fib [0..] (this is laziness, call-by-need). On subsequent calls more and more fib values in the list are calculated and at the same time each call looks up a fib value by indexing into the list (!!).

Without the list each call to fib would have made another two calls to fib which again would make two calls, etc. In algorithmic terms this changes fib from O(n^2) to O(n).

Without having looked at the Project Euler problem I suggest you try with another data structure first. In your case you should probably try with vector or perhaps array. Those are both much faster than list which you are currently using and which is actually a linked list.

You might also gain a little bit from changing your board representation to board :: [Int]. We intuitively think of a board as having two dimensions, but it's quite easy to implement as a list rather than list of lists. (This I remember from a chapter in PAIP)

For other problems keep containers and unordered-containers in mind.

Mikkel
  • 762
  • 5
  • 17
  • got it, memoized_fib just like fibs = 1:1: zipWith (+) fibs (tail fibs), final result is a list. i have another problem, i only use fmap and head operation on list, why vector fast than list? – wei li Feb 08 '17 at 04:09
  • For `head` I don't think it makes a large, if any difference. AFAIK a vector keeps elements next to each other in memory where a linked list has pointers between elements, so any traversal e.g. `fmap` should be much faster on a `vector`. – Mikkel Feb 08 '17 at 04:39
  • Just came across a good explanation of the difference in efficiency between lists and vectors at [School of Haskell](https://www.schoolofhaskell.com/user/commercial/content/vector#efficiency) – Mikkel Apr 11 '17 at 07:04