CS 345 slide 81 Spring 20053 February 2005zipA prelude function that’s often used in listcomprehensions iszip :: [a] -> [b] -> [(a,b)]We’ll look at zip’s definition soon; for now, let anexample suffice to show what zip does:Main> zip [0..5] "The Merry Month of September"[(0,'T'),(1,'h'),(2,'e'),(3,' '),(4,'M'),(5,'e')]Example: computing the scalar (dot) product of twovectorsa•b = aiibiwhere the vectors are represented by lists.If we traverse each list with its own generator…> dot as bs = sum [ a*b | a <- as, b <- bs ]then we getdot [1,2,3] [4,5,6] H S sum [1*4,1*5,1*6,2*4,2*5,2*6,3*4,3*5,3*6]whereas what we want issum [1*4, 2*5, 3*6]Using zip enables both lists to be traversed in step,using a single generator:> dot as bs = sum [ a*b | (a,b) <- zip as bs ]Note the pattern (a,b), which names the elements ofeach pair produced by zip.CS 345 slide 82 Spring 20053 February 2005Prelude list-processing functionsIn addition to arithmetic sequences and listcomprehensions, there is a large collection of list-processing functions in the Prelude, including(++) :: [a] -> [a] -> [a]Concatenates two lists."hippo" ++ "drome" H S "hippodrome"concat :: [[a]] -> [a]Concatenates a list of lists into a singlelist.concat ["Cat", "Mouse", "Duck"]H S "CatMouseDuck"length :: [a] -> IntCounts a list’s elements.length ["Cat", "Mouse", "Duck"] H S 3head/last :: [a] -> aReturns a list’s first/last element.head "Duck" H S 'D'last "Duck" H S 'k'tail/init :: [a] -> [a]Returns all of a list except its first/lastelement.tail "Duck" H S "uck"init "Duck" H S "Duc"replicate :: Int -> a -> [a]Makes a list of n copies of an item.replicate 3 "Cat" H S ["Cat", "Cat", "Cat"]CS 345 slide 83 Spring 20053 February 2005take :: Int -> [a] -> [a]take n returns a list’s first n elements.take 3 "Mouse" H S "Mou"drop :: Int -> [a] -> [a]drop n returns all except a list’s first nelements.drop 3 "Mouse" H S "se"splitAt :: Int -> [a] -> ([a],[a])Splits a list at a given position.splitAt 3 "Mouse" H S ("Mou", "se")takeWhile :: (a -> Bool) -> [a] -> [a]Returns elements of a list up to the firstthat fails a given test.takeWhile (<4) [0,2,1,5,3] H S [0,2,1]dropWhile :: (a -> Bool) -> [a] -> [a]Returns elements of a list beginning withthe first that fails a given test.dropWhile (<4) [0,2,1,5,3] H S [5,3]reverse :: [a] -> [a]Reverses the order of a list’s elements.reverse "Mouse" H S "esuoM"null :: [a] -> BoolEmpty-list test. Better than (==[]) and ( ==0).lengthCS 345 slide 84 Spring 20053 February 2005zip :: [a] -> [b] -> [(a,b)]Maps two lists into a list of pairs.zip "Cat" "Mouse" H S [('C','M'), ('a','o'), ('t','u')]unzip :: [(a,b)] -> ([a],[b])Maps a list of pairs into a pair of lists.unzip [('C','M'), ('a','o'), ('t','u')]H S ("Cat", "Mou")and, or :: [Bool] -> BoolReturns a Boolean list’s conjunction/disjunction.and [3 < 0, 0< 3, 3>= 0] H S Falseor [3>0, 0<3, 3>=0] H S Truesum :: Num a => [a] -> aReturns a numeric list’s sum.sum [1..4] H S 10product :: Num a => [a] -> aReturns a numeric list’s product.product [1..4] H S 24map, filter (defined earlier)elem :: Eq a => a -> [a] -> BoolMembership test.3 `elem` [0..5] H S TrueUseful though all these functions are, eventually oneis bound to encounter a list-processing problem forwhich there is no predefined function.This requires the use of …CS 345 slide 85 Spring 20053 February 2005The List Constructor (:)To build a list one element at a time, use the operator(:) :: a -> [a] -> [a]which is pronounced “followed-by” (in Lisp, it’s cons).In an expression, (:) constructs a list from an itemand a list.The left argument of (:) is an item of some type; itsright argument is a list of items of the same type.Some equivalences:[1,2,3] = 1:(2:(3:[ ] ))"123" = '1':('2':('3':[ ] ))[1,2,3] = 1:[2,3]x:xs = [x] ++ xsNote: (:) is right-associative, so1:(2:(3:[ ] )) = 1:2:3:[ ]Given a list xs, creating listsx:xs and y:xs requires nocopying— the tail xs isshared::y:xxsBecause (:) is defined to be non-strict,[n..] = let f k = k : f (k+1) in f nThe list [n..] is infinite, but thanks to nonstrictnessit occupies only finite space; each element isconstructed only on demand.CS 345 slide 86 Spring 20053 February 2005…and the List Selector (:)The same operator is also used in patterns, where itserves as a selector. Examples:> head :: [a] -> a> head (x:_) = x -- matches non-empty lists> last :: [a] -> a> last [x] = x-- matches 1-element lists ONLY> last (_:xs) = last xs> tail :: [a] -> [a]> tail (_:xs) = xs> init :: [a] -> [a]> init [x] = [ ]> init (x:xs) = x : init xs> length :: [a] -> Int> length [ ] = 0> length (x:xs) = 1 + length xs> reverse :: [a] -> [a]> reverse [ ] = [ ]> reverse (x:xs) = reverse xs ++ [x]Names such as x and xs (or b and bs, etc.), are commonlyused in list patterns x:xs (or b:bs) as a reminder that• x (or b, etc.) names the matching list’s firstelement,• xs (or bs, etc.) names its remaining elements.CS 345 slide 87 Spring 20053 February 2005Another example— the list-indexing operator:> (!!) :: [a] -> Int -> a> (x:xs) !! 0 = x> (x:xs) !! n | n >0 = xs !! (n-1)> (_:_) !! _ = error "negative index"> [] !! _ = error "index too large"List indexing is expensive (and used too often bystudents still thinking in Java).Using (:) as both selector and constructor, we candefine zip:> zip :: [a] -> [b] -> [(a,b)]> zip [ ] _ = [ ]> zip _ [] = []> zip (x:xs) (y:ys) = (x,y) : zip xs ys… and concatenation:> (++) :: [a] -> [a] -> [a]> [ ] ++ ys = ys> (x:xs) ++ ys = x : (xs ++ ys)> -- as ++ bs includes bs, which is not copied… and functions such as> take, drop :: Int -> [a] -> [a]> take n _ | n <= 0 = []> take _ [] = []> take n (x:xs) = x : take (n-1) xs> drop n xs | n <= 0 = xs> drop _ [] = []> drop n (_:xs) = drop (n-1) xswhich are used to select parts of lists.CS 345 slide 88 Spring 20053 February 2005The empty-list test:null :: [a] -> Boolnull [] = Truenull _ = FalseExplaining list comprehensions in terms of (:):[ f y | y <- (x:xs) ]H S f x : [ f y | y <- xs ]Note that xs = tail(x:xs)[ f y | y <- [] ]H S [][ f y | y <- (x:xs), g y ]H S if g xthen f x : [ f y | y <- xs, g y ]else [ f y | y <- xs, g y ][ f y | y <- [], g y ]H S
View Full Document