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
%Define
Here, s is defined even when ly - lx is
negative, but the drop expression will not be evaluated
then because its value is not used.