[Haskell-ELTE] alapveto memoisation Haskellben

[Divianszky Peter]

Sziasztok!

Az alabbi modul roviden bevezet a Haskell memoisation-be, abba a fajtaba, 
amit alapbol tud a Haskell: a *nem ad-hoc polimorf* konstansokat 
megjegyzi.
Azok az esetek az erdekesek, amikor ezek a konstansok lokalisak.

Udv,
Peti

----------------------------------------
-------------- Zero memoisation

choose :: Int -> Int -> Integer
choose n m = pascalTriangle !! n !! min m (n-m)    where

     pascalTriangle :: [[Integer]]
     pascalTriangle = iterate next [1]

{-
(choose 1500 500, choose 1500 500)
    -- computes 1500+1500 Pascal triangle lines
-}

-------------- Total memoisation

chooseMemo :: Int -> Int -> Integer
chooseMemo n m = pascalTriangle !! n !! min m (n-m)

pascalTriangle :: [[Integer]]
pascalTriangle = iterate next [1]

{-
(chooseMemo 1500 500, chooseMemo 1500 500)
    -- computes 1500+0 Pascal triangle lines (if chooseMemo was not called 
yet)
-}

-------------- 1000 line memoisation

chooseMemo1000 :: Int -> Int -> Integer
chooseMemo1000 n m = pascalTriangle !! n !! min m (n-m)    where

     pascalTriangle :: [[Integer]]
     pascalTriangle = continue next (take 1000 pascalTriangle')

-- private for chooseMemo1000
pascalTriangle' :: [[Integer]]
pascalTriangle' = iterate next [1]

{-
(chooseMemo1000 1500 500, chooseMemo1000 1500 500)
    -- computes 1000+500 + 0+500 Pascal triangle lines (if chooseMemo1000 
was not called yet)
-}

-------------- Adjustable memoisation

chooseMemoN :: Int -> (Int -> Int -> Integer)
chooseMemoN i = choose  where

     choose :: Int -> Int -> Integer
     choose n m = pascalTriangle !! n !! min m (n-m)   where

         pascalTriangle :: [[Integer]]
         pascalTriangle = continue next (take i pascalTriangle')

     pascalTriangle' :: [[Integer]]
     pascalTriangle' = iterate next [1]

{-
let f = chooseMemoN 1000 in (f 1500 500, f 1500 500)
    -- computes 1000+ 500+500 Pascal triangle lines

(chooseMemoN 1000 1500 500, chooseMemoN 2000 1500 500)
    -- computes 1000+500 + 1500+0 Pascal triangle lines
-}


-------------- Adjustable memoisation with sharing

chooseMemoMemoN :: Int -> (Int -> Int -> Integer)
chooseMemoMemoN i = choose  where

     choose :: Int -> Int -> Integer
     choose n m = pascalTriangle !! n !! min m (n-m)   where

         pascalTriangle :: [[Integer]]
         pascalTriangle = continue next (take i pascalTriangle'')

pascalTriangle'' :: [[Integer]]
pascalTriangle'' = iterate next [1]

{-
let f = chooseMemoMemoN 1000 in (f 1500 500, f 1500 500)
    -- computes 1000+ 500+500 Pascal triangle lines (if chooseMemoMemoN was 
not called yet)

(chooseMemoMemoN 1000 1500 500, chooseMemoMemoN 2000 1500 500)
    -- computes 1000+500 + 500+0 Pascal triangle lines (if chooseMemoMemoN 
was not called yet)

(chooseMemoMemoN 2000 1500 500, chooseMemoMemoN 1000 1500 500)
    -- computes 1500+0 + 0+500 Pascal triangle lines (if chooseMemoMemoN 
was not called yet)
-}

--------------- Alternate solution for chooseMemoMemoN

chooseMemoMemoN' :: Int -> (Int -> Int -> Integer)
chooseMemoMemoN' i = choose  where

     choose :: Int -> Int -> Integer
     choose n m = pascalTriangleMemoN i !! n !! min m (n-m)    where

pascalTriangleMemoN :: Int -> [[Integer]]
pascalTriangleMemoN = iterateMemoN next [1]


--------------- Helper functions

next :: [Integer] -> [Integer]
next l = [1] ++ zipWith (+) l (tail l) ++ [1]

-- | Continue iteration
continue :: (a -> a) -> [a] -> [a]
continue f [x]    = iterate f x
continue f (x:xs) = x: continue f xs

-- | Same as iterate but memoise first n value
iterateMemoN :: (a -> a) -> a -> (Int -> [a])
iterateMemoN f x = \n -> continue f (take n xs)  where

     xs = iterate f x