Lists

Lists

اسلاید 1: Lecture 8 Lists1Lists

اسلاید 2: Lecture 8 Lists2[1,2,h,hhh] not an acceptable listMain> [1, 2, h, hhh]ERROR - Type error in list*** Expression : [1,h,hhh]*** Term : hhh*** Type : String*** Does not match : Char [109,26,5,8,19] a list of Ints [Int] [(‘a’,97),(‘r’,114),(‘m’,109)]a list of pairs [(Char,Int)] [Mon,Tue,Wed,Thur,Fri,Sat,Sun] a list of Strings [String] [“abc”,”John”,”computers”] a list of Strings [String] [[1,22],[10,14,16,56],[10]] a list of lists of Ints [[Int]]A list is a very useful structure. A list is a collection of items of thesame type. [‘a’,’b’,’c’,’d’] a list of characters [Char]There is a special list called the empty list or a list with no elementswhich is represented as [ ]

اسلاید 3: Lecture 8 Lists3[1,3,5,7,9,11,13,15,17,19]Prelude> take 10 [a,b..]abcdefghijPrelude> take 10 [a,c..]acegikmoqsPrelude> take 10 [0,2..][0,2,4,6,8,10,12,14,16,18]Prelude> [1,5..10][1,5,9]Prelude> [1,3..12][1,3,5,7,9,11]Some ExamplesPrelude> take 10 [1,3..]

اسلاید 4: Lecture 8 Lists4(head : tail) “read as head cons tail” [2,4,8,19,55,99,1,981]A list can either be the empty list [ ]or it may consist of a head (the first element) and a tail (the rest)head = 2tail = [4,8,19,55,99,1,981]There are two built-in functions that return the head and tail of a listPrelude> head [1,2,3,4]1Prelude> tail [1,2,3,4][2,3,4]

اسلاید 5: Lecture 8 Lists511: 21 : 31 : 14 :[ ] (known as the cons notation)The list [11, 21, 31,14] in bracket notation, can be written as:An Example:addList :: [Int] -> IntaddList [ ] = 0addList (x:xs) = x + addList xsThe brackets [ ] and the cons operator : are examples of constructors. These are the the constructors for lists.

اسلاید 6: Lecture 8 Lists6if boolean-expression then expression-1 elseexpression-2if a > b then a else bmaxi a b = if a >b then a else bMain> maxi 2 33Main> maxi 4 24if then else

اسلاید 7: Lecture 8 Lists7Main> remove 2 [3,4,5,2,7][3,4,5,7]remove element [ ] = [ ]remove element list = if element = = head list then tail list else (head list ):(remove element (tail list))Main> remove 2 [3,4,5,2,7,2,2][3,4,5,7,2,2]remove element [ ] = [ ]remove element list = if element = = head list then remove element (tail list) else (head list):(remove element (tail list))Main> remove 2 [2,3,2,4][3,4]Main> remove 4 [4,3,5,4,4,4,4][3,5]Function to remove an element from a list: remove element list

اسلاید 8: Lecture 8 Lists8More pattern matching remove element [ ] = [ ]remove element (first:rest) = if element = = first then remove element rest else first:(remove element rest)Main> remove 3 [4,5,3,7][4,5,7]Main> remove a [a,b,c]bcMain> remove Joe [Jack,Andy][Jack,Andy]

اسلاید 9: Lecture 8 Lists9Other Example functions on lists--length of a listlengthList [ ] = 0 lengthList (x:xs) = 1 + lengthList xs Main> lengthList [10,21,3,14,54]5--take two lists and make a list of pairsMain> myZip [11,21] [34,46,65][(11,34),(21,46)]myZip xs [ ] = [ ] myZip [ ] ys = [ ] myZip (x:xs) (y:ys) = (x,y) : myZip xs ys Main> myZip [1,2,3] [Mary,John,George][(1,Mary),(2,John),(3,George)]

اسلاید 10: Lecture 8 Lists10lengthList [ ] = 0 lengthList (x:xs) = 1 + lengthList xs lengthList [10,21,3,14,54] = 1 + lengthList [21,3,14,54] = 1 + (1 + lengthList [3,14,54]) = 1 + (1 + (1 + lengthList [14,54] ))= 1 + (1 + (1 + (1 + lengthList [54] )))= 1 + (1 + (1 + ( 1+ (1 + lengthList [])))) = 1 + (1 + (1 + (1 + (1 + 0)))) = 5 A trace of lengthList

اسلاید 11: Lecture 8 Lists11product [ ] = 0product [a]=aproduct (a:x) = a * product xsum [ ] = 0sum (a:x) = a + sum xreverse [ ] = [ ]reverse (a:x) = reverse x ++ [a]head (x:_)  = xtail (_:xs) = xs  Other examples of functions using pattern matching

اسلاید 12: Lecture 8 Lists12member :: Int-> [Int] -> Boolmember e [ ] = Falsemember e (x:xs) | e= =x = True |otherwise = member e xsMain> member 3 [4,2,5,6]FalseMain> member a [b,a,g]ERROR - Type error in application*** Expression : member a [b,a,g]*** Term : [b,a,g]*** Type : [Char]*** Does not match : [Int]Main> member 3 [1,2,3,4]True

اسلاید 13: Lecture 8 Lists13member e [ ] = Falsemember e (x:xs) | e= =x = True |otherwise = member e xsMain> member a [a,b‘,’c’]TrueMain> member mike [joe,peter,andrew]FalseMain> member 1 [1,2,4,6]TrueHugs guesses the type when you don’t declare it