Write an equational definition of a function suffix so that suffix(x,y) is true just when list x is a suffix of list y. (List x is a suffix of list y if there exists a list z such that z ++ x = y.) For example, suffix([4,6], [1,2,4,6]) is true, but suffix([5,6], [1,5,2,6]) is false. The empty list is a suffix of every list, and every list is a suffix of itself.
Keep it simple. Here are two approaches.
List x is a suffix of list y if the reversal of x is a prefix of the reversal of y. So a definition of suffix is
suffix(x,y) = prefix(reverse x, reverse y)
prefix([], y) = true
prefix(a::r, b::t) = a == b and prefix(b,t)
prefix(a::r, []) = false
To determine whether list x is a suffix of list y, get the suffix s of y whose length is the same as the length of x. Then just check whether s = x.
suffix(x,y) = (ly >= lx) and ((drop (ly - lx) y) == x) |
lx = length x
ly = length y
We wrote the definition of drop in class.
drop 0 y = y
drop n [] = []
drop (n+1) (h::t) = drop n t
What is the value of each of the following Cinnameg expressions?
Function select is written so that (select p x) returns a the first member m of list x such that p(m) is true. Notice that p is a predicate, a function that produces a boolean result. (For the purposes of this question, it will not matter what select does when there is no such m.) Predicate odd? returns true on an odd number and false on an even number.
What is the value of Cinnameg expression map(select odd?)[[2,3,4,5],[1,2,3,4],[2,4,6,7,8]]? (Answer: [3,1,7])
Given definition
f x y = (x+1)::y.
You are given the following function definition.
f x y z = y x (x::z)
By choosing among the operations foldLtoR, foldRtoL and map write a definition for each of the following that does not use recursion or loops.
Write a function called doubleAll that takes a list x of numbers as its parameter and produces a list of the doubles numbers in list x as its result. For example, doubleAll([5,2,19,3]) = [10,4,38,6].
double x = 2*x
doubleAll = map double
Write a function called maxlist(m,L) that computes the largest value in list m::L. That is, it computes the maximum of m and the largest value in list L. Assume that function max is available where max(x,y) is the larger of x and y.
maxlist(m,L) = foldLtoR(m,max) L(foldRtoL works as well. The direction does not matter.)
What is the value of Scheme expression (car (cdr (cons 'horse (cons 'zebra ()))))?
Answer: zebra. Be sure to pay attention to the difference between zebra and (zebra). For example, expression (cdr (cons 'horse (cons 'zebra ()))) yields (zebra).
Write a Scheme function called prefix so that (prefix x y) returns true if list x is a prefix of list y. Be careful to use Scheme syntax correctly.
(define (prefix x y)
(cond
((null? x) #t)
((null? y) #f)
((eq (car x) (car y)) (prefix (cdr x) (cdr y)))
(else #f)
)
)
Write a Scheme function called descending so that (descending L) is true for a list of numbers L if L is in descending order. (The Scheme function < does a less-than test, and > does a greater-than test.) List (a b c d) is in descending order if a > b > c > d. The empty list is in descending order by definition, as is a singleton list.
(define (descending L)
(cond
((null? L) #t)
((null? (cdr L)) #t)
((> (car L) (cadr L)) (descending (cdr L)))
(else #f)
)
)