List PrefixList ContainmentMysteryfoldrshorterstripEmptymergeData TypesFunction CompositionReduce520—Spring 2005—20CSc 520Principles of ProgrammingLanguages20: Haskell — ExercisesChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2005 Christian Collberg[1]520—Spring 2005—20List PrefixWrite a recursive function begin xs ys that returnstrue if xs is a prefix of ys. Both lists are lists of integers.Include the type signature.> begin [] []True> begin [1] []False> begin [1,2] [1,2,3,4]True> begin [1,2] [1,1,2,3,4]False> begin [1,2,3,4] [1,2][2]520—Spring 2005—20List ContainmentWrite a recursive function subsequence xs ys thatreturns true if xs occurs anywhere within ys. Both listsare lists of integers. Include the type signature.Hint: reuse begin from the previous exercise.> subsequence [] []True> subsequence [1] []False> subsequence [1] [0,1,0]True> subsequence [1,2,3] [0,1,0,1,2,3,5]True[3]520—Spring 2005—20MysteryConsider the following function:mystery :: [a] -> [[a]]mystery [] = [[]]mystery (x:xs) = sets ++ (map (x:) sets)where sets = mystery xsWhat would mystery [1,2] return? mystery[1,2,3]?What does the funtion compute?[4]520—Spring 2005—20foldrExplain what the following expressions involving foldrdo:1.foldr (:) [] xs2. foldr (:) xs ys3. foldr ( y ys -> ys ++ [y]) [] xs[5]520—Spring 2005—20shorterDefine a function shorter xs ys that returns theshorter of two lists.> shorter [1,2] [1][1]> shorter [1,2] [1,2,3][1,2][6]520—Spring 2005—20stripEmptyWrite function stripEmpty xs that removes all emptystrings from xs, a list of strings.> stripEmpty ["", "Hello", "", "", "World!"]["Hello","World!"]> stripEmpty [""][]> stripeEmpty [][][7]520—Spring 2005—20mergeWrite function merge xs ys that takes two orderedlists xs and ys and returns an ordered list containingthe elements from xs and ys, without duplicates> merge [1,2] [3,4][1,2,3,4]> merge [1,2,3] [3,4][1,2,3,4]> merge [1,2] [1,2,4][1,2,4][8]520—Spring 2005—20Data TypesConsider the following type:data Shape = Circle Float |Rectangle Float FloatDefine a function shapeLength that computes thelength of the perimeter of a shape.Add an extra constructor to Shape for triangles.Define a function which decides whether a shape isregular: a circle is regular, a square is a regularrectangular, and being equilateral makes a triangleregular.[9]520—Spring 2005—20Function CompositionRewrite the expressionmap f (map g xs)so that only a single call to map is used[10]520—Spring 2005—20ReduceLet the Haskell function reduce be defined byreduce f [] v = vreduce f (x:xs) v = f x (reduce f xs v)Reconstruct the Haskell functions length, append, filter,and map using reduce. More precisely, complete thefollowing schemata (in the simplest possible way):mylength xs = reduce ___ xs ___myappend xs ys = reduce ___ xs ___myfilter p xs = reduce ___ xs ___mymap f xs = reduce ___ xs
View Full Document
Unlocking...