Lazy evaluation

Posted on 2015-08-18 20:18:10 +0900 in Functional Programming Haskell CIS194

Lecture Contents

Lazy evaluation is beautiful because it makes infinite data structures possible. But it makes reasoning about the programme harder, especially when mixed with side effects.

import Data.Array

knapsack01 :: [Double]   -- values 
           -> [Integer]  -- nonnegative weights
           -> Integer    -- knapsack size
           -> Double     -- max possible value
knapsack01 vs ws maxW = m!(numItems-1, maxW)
  where numItems = length vs
        m = array ((-1,0), (numItems-1, maxW)) $
              [((-1,w), 0) | w <- [0 .. maxW]] ++
              [((i,0), 0) | i <- [0 .. numItems-1]] ++
              [((i,w), best) 
                  | i <- [0 .. numItems-1]
                  , w <- [1 .. maxW]
                  , let best
                          | ws!!i > w  = m!(i-1, w)
                          | otherwise = max (m!(i-1, w)) 
                                            (m!(i-1, w - ws!!i) + vs!!i)
              ]

example = knapsack01 [3,4,5,8,10] [2,3,4,5,9] 20

The functional dynamic programming implementation is kind of tricky in my view.

Monolithic Arrays is used to memorized the overlapped subprobramme.

Home Work

Exercise 1

fib :: Integer -> Integer
fib n
  | n == 0 = 0
  | n == 1 = 1
  | otherwise = fib (n - 1) + fib (n - 2)

fibs1 :: [Integer]
fibs1 = map fib [0..]

Exercise 2

fibs2 :: [Integer]
fibs2 = 0 : 1 : zipWith (+) fibs2 (tail fibs2)

Exercise 3

cons is mentioned in the lecture, but use record syntax makes it much more cleaner.

data Stream a = Stream { streamToList :: [a] }

instance (Show a) => Show (Stream a) where
  show =  show . take 20 . streamToList

Exercise 4

streamRepeat :: a -> Stream a
streamRepeat = Stream . repeat

streamMap :: (a -> b) -> Stream a -> Stream b
streamMap f = Stream . map f . streamToList

streamFromSeed :: (a -> a) -> a -> Stream a
streamFromSeed f = Stream . iterate f

Exercise 5

Explanation

nats :: Stream Integer
nats = Stream [0..]

interleaveStreams :: Stream a -> Stream a -> Stream a
interleaveStreams (Stream (x:xs)) s =
  Stream $ x : streamToList (interleaveStreams s (Stream xs))


ruler :: Stream Integer
ruler = foldr1 interleaveStreams (map streamRepeat [0..])

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------

« Folds and monoids | More polymorphism and type classes »