PhyrexTsai

Pattern matching

a. Use pattern-matching with (:) and the wildcard pattern _ to define a function, myButLast, that find the last but one element of a list. For examples;

myButLast :: [a] -> a
myButLast [1,2,3,4]  = 3
myButLast ['a'..'z'] = 'y'

Note: we assume that the input list has at least two elements.

PhyrexTsai

List manipulation

a. Write a function to determine if the elements of a list form a palindrome, palindrome [Int] -> Bool. For example:

palindrome [ 1, 2, 2, 3, 3] = False
palindrome [ 1, 2, 3, 2, 1] = True
palindrome [3] = True
palindrome [] = True

b. A permutation of a list is another list with the same elements, but in a possibly different order. For example, [1,2,1] is a permutation of [2,1,1], but not of [1,2,2]. Write a function

PhyrexTsai

Tail recursion

a. Write a tail-recursive version of the upto function mentioned in the lecture note, call it tailUpto :: Int->Int->[Int]->[Int]. For examples:

tailUpto 3 8 [1,2] = [3,4,5,6,7,8,1,2]
tailUpto 8 3 [1] = [1]

In other words, upto m n = tailUpto m n [].

b. Write a tail-recursive version of the fib function to compute the nth number in the Fibonacci sequence. Specifically, define the tailFib function with two accumulating parameters

PhyrexTsai

List comprehension

a. Using list comprehensions, define a function, countNeg, for counting the number of negative numbers in a list of numbers.

countNeg :: [Int] ->  Int	 
>countNeg [1, -2, 3, -5] = 2

b. Define $x^n$ using a list comprehension. Name the function as raise:

raise :: Int -> Int -> Int 

PhyrexTsai

Higher-order functions and list comprehension

a. Study the code fragment below and identify the operation it provides. Then rewrite it using map and filter, and name it as q1f1a.

q1f1 :: [Int] -> [Int]
q1f1 [] = []
q1f1 (x:xs) | x < 3	= q1f1 xs
            | x > 10	= q1f1 xs
            | otherwise   = x*3 : q1f1 xs

PhyrexTsai

Higher-order function

We use lists to represent sets. Your task is to define a function, subsets, that receives a list as a set and returns the set of all subsets of the input set. For example:

subsets :: [Int] -> [[Int]]
subsets [] =  [ [] ]
>subsets [1,2,3] = [ [], [1], [2], [3],[1,2] [1,3], [2,3], [1,2,3] ] –順序無關 

PhyrexTsai

Fold functions

Use fold-family functions and some auxiliary functions, such as the map, all and any defined in class slides, and your own, to define the following functions. In other words, you cannot use direct recursion to define them.

a. Write a function maxl xs using that generates an error "empty list" if xs==[] and otherwise returns the largest element of xs

maxl :: (Ord a) => [a] -> a
maxl xs = ...
>maxl [1,3,2,5,6,4]
6

PhyrexTsai

Function composition

Use the functions, remdup, elemOcc, and map to define a function, occurrences, that receives a list of characters and returns a list of pairs of an element and the number of its occurrences in the input list. For example:

occurrences [‘a’, ‘c’, ‘d’, ‘a’, ‘c’] = [(‘a’, 2), (‘c’, 2), (‘d’, 1)]
occurrences :: [Char] -> [(Char,Int)]
occurrences xs = zip (??) (??)
remdup :: [Char]->[Char]
remdup [] = []
remdup (x:xs) = x : remdup (…)

PhyrexTsai

Foldr

a. Use foldr to define map f. To avoid confusion, please rename it as myMap.

myMap :: (a->b)->[a]->[b]
myMap f = foldr ...

b. What does the following higher-order function, pipeline, do?

pipeline = map . foldr (.) id

PhyrexTsai

Int expressions

Define the “evaluate (eval)” function for the following data types of Int expressions.

Type Name = String
data Expr =  Var Name | Lit Int  --constant
					  | Expr :+: Expr
		              | Expr :*: Expr
	                  deriving (Eq, Show)