{- CSci 555, Fall 2010 Exam #2, 15 November 2010 Program Comments Revised 28 November Revised to be Haskell 2010 module: 28 Sep 2014 H. C. Cunningham 123456789012345678901234567890123456789012345678901234567890123456789012 -} module Exam02_555 where {- #1. Show the list yielded by each of the following Haskell list expressions. If the list is finite, display it using fully specified list bracket notation, e.g., expression [1..5]} yields [1,2,3,4,5]}. If the list is infinite, display the list using the ellipsis "..." appropriately. Assume that data type Color has been defined as follows. -} data Color = Red | Orange | Yellow | Green | Blue | Violet | Grayscale Int deriving Show p1a = [4..9] -- [4,5,6,7,8,9] p1b = [9..4] -- [] -- Item below omitted from exam p1b2 = [1,4..11] -- [1,4,7,10] p1c = [9,6..1] -- [9,6,3] p1d = [ 2*i | i <- [1..10], odd i ] -- [2,6,10,14,18] p1e = take 5 [ n*n | n <- [2..], even n ] -- [4,16,36,64,100] p1f = [ j | i <- [1,-1,2,-2], j <- [1..i] ] -- [1,1,2] p1g = [ (x,y) | x <- [1..3], y <- [Blue,Red] ] -- [(1,Blue),(1,Red),(2,Blue),(2,Red),(3,Blue),(3,Red)] -- Item below omitted from exam p1g2 = [ [ y | y <- [1..x] ] | x <- [2,4] ] -- [[1,2],[1,2,3,4]] p1h = [ ys | (y:ys) <- ["Can", "you", "think", "recursively?"] ] -- ["an","ou","hink","ecursively?"] p1i = [ Grayscale x | x <- [1..] ] -- [Grayscale 1,Grayscale 2,Grayscale 3,Grayscale 4,Grayscale 5,Grayscale 6,... p1j = let iterate f x = x : iterate f (f x) sh [] = [] sh (x:xs) = xs in takeWhile (/=[]) (iterate sh "ABCD") -- ["ABCD","BCD","CD","D"] {- #2. Remove the list comprehensions from the following expressions. That is, translate the list comprehensions into expressions using one or more of the functions filter, map, foldr, ++, fst, snd, zip, etc. Functions fst and snd are prelude functions that extract the first and second components, respectively, from two-component tuples. Function zip returns a list of pairs of the corresponding elements of its two input lists. -} p2ac p xs = [x | x <- xs, p x] p2af p xs = filter p xs p2bc f g xs = [f (g x) | x <- xs] p2bf f g xs = map (f . g) xs p2cc xss = [x | xs <- xss, x <- xs] p2cf xss = foldr (++) [] xss p2dc p xs = [ i | (i,x) <- zip [1..] xs, p x] p2df p xs = map fst (filter (p . snd) (zip [1..] xs)) {- #3. Consider the following definition for a factorial function fact, which uses an accumulating parameter. Note the pattern match and the use of the strict function. -} fact :: Int -> Int -> Int fact f 0 = f -- fact f n = (strict fact (f*n)) (n-1) fact f n = fact (f*n) (n-1) -- Textual answers not give here {- #4. Proofs related to functional composition not given here. -} {- $5. Textual answers not given here -} {- #6 Suppose we have the following Haskell definitions. What would be displayed on the screen when g is evaluated? -} x = 1:y y = map f x f = (*2) g = take 10 x p6 = g -- [1,2,4,8,16,32,64,128,256,512] {- #7. An S-expression (i.e., symbolic expression as in the language Lisp) consists of a number, a symbol, or a sequence of S-expressions. If we use matched pairs of parentheses to denote sequences, then the S-expression (3 (4 x) y) consists of a sequence of three elements. The elements, in order, are the number 3, the sequence (4 x), and the symbol y. The sequence (4 x) itself consists of the number 4 and the symbol x. (Note: The notation in this paragraph is not intended to be Haskell.) An empty sequence of S-expressions is called a nil. An S-expression that is a number, a symbol, or a nil is said to be an atom. Non-nil sequences are not atoms. Now consider how to represent these S-expressions in Haskell. Let an object of type Sexpr represent an S-expression: -} data Sexpr = Num Int | Sym String | Seq [Sexpr] deriving Show {- The constructor Num i denotes a number with value i. The constructor Sym s denotes a symbol with value s. The constructor Seq xs denotes the sequence of S-expressions given in the Haskell list xs. If xs is [], then the sequence is a nil. Thus the S-expression (3 (4 x) y) is represented in Haskell as (Seq [Num 3, Seq [Num 4, Sym "x"], Sym "y"]). SELECT FIVE of the following functions and show Haskell definitions and type signatures. You may use functions defined earlier in the list to define later ones. -} {- 7(a), Function isNil takes an S-expression and returns True if the Sexpr is a nil and False otherwise. -} isNil :: Sexpr -> Bool isNil (Seq []) = True isNil _ = False p7a1 = isNil (Seq []) -- True p7a2 = isNil (Num 3) -- False p7a3 = isNil (Sym "Hi") -- False p7a4 = isNil (Seq [Seq []]) -- False {- OMITTED FROM EXAM Function isAtom takes an S-expression and returns True if the Sexpr is an atom and False otherwise. -} isAtom :: Sexpr -> Bool isAtom (Seq (x:xs)) = False isAtom _ = True p7x1 = isAtom (Seq []) -- True p7x2 = isAtom (Num 3) -- True p7x3 = isAtom (Sym "Hi") -- True p7x4 = isAtom (Seq [Seq []]) -- False {- 7(b). Function cons takes an S-expression x and a sequence y and returns the sequence in which x has been inserted in front of the elements of y. For example, cons (Num 1) (Seq [Num 2]) returns (Seq [Num 1, Num 2]). -} cons :: Sexpr -> Sexpr -> Sexpr cons x (Seq ys) = Seq (x:ys) p7b = cons (Num 1) (Seq [Num 2]) -- Seq [Num 1,Num 2] {- 7(c). Function car takes a non-nil sequence and returns the first S-expression in the sequence. For example, car (Seq [Num 1,Num 2]) returns (Num 1). -} car :: Sexpr -> Sexpr car (Seq (x:_)) = x p7c = car (Seq [Num 1,Num 2]) -- Num 1 {- 7(d). Function cdr takes a non-nil sequence and returns the sequence remaining after removing the first element. For example, cdr (Seq [Num 1, Num 2]) returns (Seq [Num 2]). -} cdr :: Sexpr -> Sexpr cdr (Seq (_:xs)) = Seq xs p7d = cdr (Seq [Num 1, Num 2]) -- Seq [Num 2] {- 7(e). Function equals takes two S-expressions and returns True if they are exactly the same and returns False otherwise. -} equals :: Sexpr -> Sexpr -> Bool equals (Num x) (Num y) = (x == y) equals (Sym x) (Sym y) = (x == y) equals (Seq []) (Seq []) = True equals (Seq (x:xs)) (Seq (y:ys)) = equals x y && equals (Seq xs) (Seq ys) equals _ _ = False p7e1 = equals (Seq []) (Num 3) -- False p7e2 = equals (Seq [Num 1, Seq [Num 2]]) (Seq [Num 1, Seq [Num 2]]) -- True {- 7(f). Function append takes an S-expression x and an S-expression y and returns the sequence in which the elements of y are appended after the elements of x. For example, append (Seq [Num 1,Num 2]) (Seq [Num 3]) returns (Seq [Num 1,Num 2,Num 3]). -} append :: Sexpr -> Sexpr -> Sexpr append (Seq xs) (Seq ys) = Seq (xs++ys) append x (Seq ys) = Seq (x:ys) -- cons append (Seq xs) y = Seq (xs ++ [y]) append x y = Seq [x,y] p7f = append (Seq [Num 1,Num 2]) (Seq [Num 3]) -- Seq [Num 1,Num 2,Num 3] {- 7(g) Function rev takes an S-expression (e.g., a sequence) and returns the S-expression with the elements in reverse order. For example, rev (Seq [Num 1, Seq [Num 0, Num 3], Num 2]) returns (Seq [Num 2, Seq [Num 0, Num 3], Num 1]). -} rev:: Sexpr -> Sexpr rev (Seq xs) = Seq (reverse xs) rev x = x p7g = rev (Seq [Num 1, Seq [Num 0, Num 3], Num 2]) -- Seq [Num 2,Seq [Num 0,Num 3],Num 1] {- Problem #5 CHANGED ON EXAM Suppose we have the following Haskell definition for generalized (i.e., multiway) trees. Each node has a value and zero or more subtrees. -} data Gtree a = Node a [Gtree a] deriving Show test1 = Node 9 [Node 7[], Node 6 [Node 4 [], Node 3 []], Node 1 []] {- 5(a). Function sumGT sums the values in a generalized tree of numbers. -} sumGt :: Num a => Gtree a -> a sumGt (Node n []) = n sumGt (Node n gs) = n + sum (map sumGt gs) p5a = sumGt test1 -- 30 {- 5(b). Function heightGt determines the height of a generalized tree. (Assume a tree that only has a root is of height one.) -} heightGt :: Gtree a -> Int heightGt (Node _ []) = 1 heightGt (Node _ gs) = 1 + maximum (map heightGt gs) p5b = heightGt test1 -- 3 {- 5(c). Function mapGt takes a function and a generalized tree and returns a tree of the same structure in which the function has been applied to every value. -} mapGt :: (a -> b) -> Gtree a -> Gtree b mapGt f (Node v gs) = Node (f v) (map (mapGt f) gs) p5c = mapGt (*3) test1 -- Node 27 [Node 21 [],Node 18 [Node 12 [],Node 9 []],Node 3 []]