This homework is due by the start of class on Wednesday Jan 19.
As a reminder of some of the notions we already defined for strings:
letter =def {
λ empty! false;
λ ys ^ xs if ys ≠ empty and xs ≠ empty! false;
λ xs. true
}
short(xs) =def letter(xs) or xs = empty
length =def {
λ empty. 0;
λ ys ^ xs if letter(ys). 1 + length(xs)
}
startsWith (hs, ps) =def dissect hs {
λ ys ^ xs if ys = ps! true;
λ xs. false
}Problem 1. Define endsWith (hs, ps), which returns true iff ps is (bound to or assigned) some string which is the suffix of hs (what hs is bound to or assigned).
Problem 2. Define anyWhere (hs, ps), which returns true iff ps is some string which occurs at the start of hs, or in the middle, or at the end. Explain what decision you made about whether to count the empty string or "dog" as occurring anywhere inside the string "dog".
Problem 3. Here is a defintion of a function that takes a string and a number as argument, and gives a string as a result.
take (hs, n) =def dissect hs {
λ xs if n = 0! empty;
λ empty. empty;
λ ys ^ xs if letter(ys). ys ^ take(xs, n-1)
}take("abc", 2)?take(empty, 2)?take("abc", 5)?take("abc", 0)?Problem 4. Define a function drop (hs, n) which works similarly to take, except where take would keep the first n characters and discard the rest, drop discards the first n characters and keeps the rest. Explain what decision you made about what results for drop(empty, 2) and drop("abc", 5) to have.
Problem 5. Consider the following definitions.
oneVowel =def {
λ "a"! true;
λ "e"! true;
λ "i"! true;
λ "o"! true;
λ "u"! true;
λ xs. false
}
vowels =def {
λ empty! true;
λ ys ^ xs if oneVowel(ys)! vowels(xs);
λ xs. false
}oneVowel("ea")?oneVowel(empty)?vowels("ea")?vowels("eat")?Problem 6. Consider the following definition:
takeWhile1 (hs, q) =def dissect hs {
λ ys ^ xs if letter(ys) and q(ys)! ys ^ takeWhile1 (xs, q);
λ xs. empty
}Something new is going on here. The argument q is not a string or a number but instead a predicate, like for example letter or oneVowel or vowels.
takeWhile1("dog", oneVowel)?takeWhile1("eat", oneVowel)?Problem 7. Define a function dropWhile1 (hs, q) which works similarly to takeWhile1, except where takeWhile1 keeps the longest prefix of hs whose elements satisfy q and discards the rest, dropWhile1 discards the prefix and keeps the rest. Explain what decision you made about what results for dropWhile1(empty, oneVowel) and dropWhile1("ea", oneVowel) to have.
Problem 8. This will be harder than other problems. Don’t worry if it’s too hard. I want you to try it, but will take its difficulty into account when grading. Consider the definition:
takeWhile2 (hs, q) =def dissect hs {
λ ys ^ xs if ys ≠ empty and q(ys)! ys ^ takeWhile2 (xs, (λ zs. q (ys^ zs)));
λ xs. empty
}At the end of the first clause of that definition, we call takeWhile2 again recursively with the argument xs and the argument (λ zs. q (ys ^ zs)). What does the second expression mean? This defines a function that takes some argument, assigns the variable zs to that argument, and then returns the result of applying whatever function q was to the result of concatenating ys to zs. So if ys is "abc", then this is a function that is applied to "def", will have the same result that q ("abcdef") has. What that is will depend on what function q is.
takeWhile2("dog", oneVowel)?takeWhile2("eat", oneVowel)?takeWhile2("eat", vowels)?takeWhile2("eat", letter)?takeWhile2(hs, q) always satisfy the predicate q? If so, explain why. If not, when will this fail?Problem 9. For this problem, you don’t need to apply or construct a definition. Instead you need to give an argument. See our argument that factorial(n) is always > 0 for a model. Consider all the strings that have "a" as a suffix. Prove that any such string has a length > 0.
Problem 10. We say that the reverse of a string "abc" is "cba". We can define that notion like this:
reverse =def {
λ xs if short(xs). xs;
λ ys ^ xs if letter(xs). xs ^ reverse(ys)
}reverse(empty)?reverse("a")?reverse("abba")?reverse could end up matching the same argument. I didn’t give the clauses different priorities. Why wasn’t that necessary?Problem 11. As in Problem 9, here again you need to give an argument, rather than apply or construct a definition. Observe that reverse("abcde") is the same as reverse("de") ^ reverse("abc"), which is "ed" ^ "cba". Prove that in general, reverse(us ^ ws) = reverse(ws) ^ reverse(us).
Problem 12. Sometimes we might want to talk about strings that encode structures (for example, sequences) of other strings. Let’s adopt the following conventions. We’ll use the colon (:) as a marker between elements of our sequence. Then we’ll encode the empty sequence as ":". We’ll encode the sequence which contains the string "abc" as ":abc:". We’ll encode the sequence which contains the string "abc" followed by the string "def" as ":abc:def:". We’ll encode the sequence which contains the string "abc" followed by the empty string as ":abc::". In every case, our sequence is a string that starts and ends with a colon. (If it’s the empty sequence, this is the same colon.) And whatever comes between two colons is another element in the sequence. No element of the sequence can itself contain a colon.
We’re not introducing any new formalism. ":abc::" is still just a string consisting of the letter (atomic string) ":" concatenated to "a" and then to "b" and so on. But we’re interpeting this string as standing for the sequence of two strings, "abc" followed by empty.
We can define functions to work on strings interpreted in this way. Consider the following function:
headOf =def {
λ ":" ^ ys ^ xs if not anyWhere(ys, ":") and startsWith(xs, ":") and endsWith(xs, ":")! ys;
λ xs. ":"
}headOf(":abc::")?headOf("::abc:")?headOf(":")?headOf applied to a string that doesn’t encode a sequence according to our conventions, like empty or ":abc" or "abc:"?Problem 13. Define a function tailOf, which works similarly to headOf, except where headOf keeps the first element of the encoded sequence (if any), and discards the rest, tailOf discards the first and keeps the rest. Explain what decision you made about what results for tailOf(":") to have.
Problem 14. Consider this definition. To keep things simple, we allow ourselves to assume that its arguments hs are restricted to sequences encoded in the way described in Problem 12. The argument q is a predicate on strings.
anyOf (hs, q) =def dissect hs {
λ ":"! false;
λ ":" ^ ys ^ xs if not anyWhere(ys, ":") and startsWith(xs, ":") and q(ys)! true;
λ ":" ^ ys ^ xs if not anyWhere(ys, ":") and startsWith(xs, ":"). anyOf(xs, q)
}anyOf(":a:b:c:", oneVowel)?anyOf(":b:", oneVowel)?anyOf(":", oneVowel)?