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. Of course, if x is longer than y, then x is obviously not a suffix of y.
suffix(x,y) = length(y) >= length(x) and drop(length(y) - length(x), y) == x
We wrote the definition of drop in class.
drop(0, y) = y drop(?, []) = [] drop(n+1, ?::t) = drop n t
The definition above requires computing length(x) and length(y) twice. You can avoid that by giving names to the two lengths. I will use a bar notation, where definitions after the bar are done first, then the expression is evaluated.
suffix(x,y) = ly >= lx and drop(ly - lx, y) == x | lx = length(x) ly = length(y)In Cinnameg, you would write this as follows.
Define suffix(x,y) = ly >= lx and drop(ly - lx, y) == x | Let lx = length x. Let ly = length y. %Define
Notice that it is important not to compute drop(ly - lx, y) when lx > ly, since you cannot drop a negative number of values from a list. The definition of suffix takes advantage of the nature of the and operator. Expression a and b is equivalent to cond(a, b, false).
Later, we will see lazy evaluation, and a Define statement that avoids evaluating an expression until it the value is used. Using Define, you could write
Define suffix(x,y) = ly >= lx and s == x | Define lx = length x; ly = length y; s = drop(ly - lx, y) %Define %DefineHere, s is defined even when ly - lx is negative, but the drop expression will not be evaluated then because its value is not used.