DOC PREVIEW
UT CS 345 - Lecture Notes

This preview shows page 1 out of 2 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 = aiibiwhere 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

UT CS 345 - Lecture Notes

Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?