| CSC 8310 ML Assignment: String Processing David Matuszek, Villanova University, Spring 2001 |
This assignment is to write and test several string processing functions. Almost all of the functions will be higher-level functions.
Important note: This is a significantly revised (and improved!) version of the assignment that I put up on Friday. That version worked with lists of characters rather than strings, which made some functions easier but others very, very difficult. If you have already done the assignment according to the original specifications, that's fine; if not, you will find the following version somewhat easier.
General features of the functions
The following functions are designed to work on strings. In several of the
functions it is more convenient to convert the strings to lists of characters
(with explode), manipulate the lists, and convert the result back
into a string (with implode).
Many of the functions are curried functions, and will work as follows:
string that is a "pattern" and
absorbs (curries) it to form a new function. string that represents the string
to be worked on, applies the pattern to the front of the "subject"
string, and returns a two-tuple as a result. The first element of the tuple
is a bool telling whether the pattern match succeeded; the second
element is the string with the matched part removed.Example: The match function does a simple character-by-character
matching to see whether the characters in the "pattern" are exactly
the same, and in the same order, as the characters at the beginning of the "subject."
So, match "abc" "abcde"; works as
follows:
"abc" is absorbed into the match,
giving a new function (match "abc") that will
match exactly the characters "abc" at the front of
a string."abcde", giving the
result (true, "de").The type of match is string -> string -> bool * string
. Adding parentheses for clarity, this is the same as string -> (string -> (bool * string)).
I will abbreviate this type as chfun, and abbreviate (string -> (bool * string))
as result, but remember that ML does not know about these
abbreviations.
If you need to convert strings to char lists, it's a good idea to use the
let expression:
let val pattern_chars = explode pattern; val subject_chars = explode subject; ... in ... end
Here are the functions you need to write. These are approximately in order of increasing difficulty.
| Name | len |
| Type | int -> string -> bool * string |
| What it does | Takes an integer N and produces a function that matches the first N characters
of the string. |
| Examples |
- len 2 "abcde"; > val it = (true, "cde") : bool * string - len 5 "abcde"; > val it = (true, "") : bool * string - len 7 "abcde"; > val it = (false, "abcde") : bool * string |
| Name | match |
| Type | string -> string -> bool * string |
| What it does | Takes a string and produces a function that tests whether
that string is an initial substring of its parameter. |
| Examples |
- match "abc" "abcde"; > val it = (true, "de") : bool * string - match "abc" "abc"; > val it = (true, "") : bool * string - match "abc" "abacad"; > val it = (false, "abacad") : bool * string - match "abcde" "abc"; > val it = (false, "abc") : bool * string |
| Name | any |
| Type | string -> string -> bool * string |
| What it does | Takes a string S and produces a function that tests whether
its parameter begins with any character that is in S. |
| Examples |
- any "abc" "abcde"; > val it = (true, "bcde") : bool * string - any "abc" "crab"; > val it = (true, "rab") : bool * string - any "abc" "face"; > val it = (false, "face") : bool * string |
| Name | notany |
| Type | string -> string -> bool * string |
| What it does | Takes a string and produces a function that tests whether
its parameter begins with a character that is not in S. |
| Examples |
- notany "abc" "abcde"; > val it = (false, "abcde") : bool * string - notany "abc" "crab"; > val it = (false, "crab") : bool * string - notany "abc" "face"; > val it = (true, "ace") : bool * string - notany "abc" "friend"; > val it = (true, "riend") : bool * string |
| Name | span |
| Type | string -> string -> bool * string |
| What it does | Takes a string S and produces a function that matches as
many characters as possible at the beginning of its parameter that occur
in S. Always succeeds. |
| Examples |
- span "abc" "cabaret"; > val it = (true, "ret") : bool * string - span "abc" "friend"; > val it = (true, "friend") : bool * string - span "abc" "face"; > val it = (true, "face") : bool * string |
| Name | break |
| Type | string -> string -> bool * string |
| What it does | Takes a string S and produces a function that matches as
many characters as possible at the beginning of its parameter that do
not occur in S. Always succeeds. |
| Examples |
- break "abc" "face"; > val it = (true, "ace") : bool * string - break "abc" "cabaret"; > val it = (true, "cabaret") : bool * string - break "abc" "friend"; > val it = (true, "") : bool * string |
| Name | opt |
| Type | ('a -> 'b -> bool * 'b) -> 'a -> 'b -> bool * 'bIf 'a = 'b = string, this can be understood as: |
| What it does | (opt stands for "optional.") Takes a pattern and
produces a new function that attempts the pattern. If it succeeds, the result
is the same as just using the pattern directly; but if the new function
fails, the result of opt is (true, original string).
Always succeeds. |
| Examples |
- opt match "abc" "abcdefg"; > val it = (true, "defg") : bool * string - opt match "abc" "cabaret"; > val it = (true, "cabaret") : bool * string |
| Name | arbno |
| Type | ('a -> 'b -> bool * 'b) -> 'a -> 'b -> bool * 'b(This is like opt.) |
| What it does | (arbno stands for "arbitrary number of.") Takes
a function and applies it as many times as possible, then reports success
regardless of the number of times the function matches. |
| Examples |
- arbno match "abc" "abcabcabcde"; > val it = (true, "de") : bool * string - arbno match "abc" "xyzzy"; > val it = (true, "xyzzy") : bool * string - arbno len 3 "abcdefghij"; > val it = (true, "j") : bool * string - arbno len 4 "abcdefghij"; > val it = (true, "ij") : bool * string |
| Name | alt |
| Type | ('a -> bool * 'a) list -> 'a -> bool * 'a, that is, |
| What it does | (alt stands for "alternatives.") Takes a list of
curried functions (that is, functions that have already absorbed a parameter),
and tries the functions one after the other. The result is the result of
the first function that works. |
| Examples |
- alt [match "ab", match "xyz"] "xyzzy"; > val it = (true, "zy") : bool * string - alt [match "ab", notany "abc", len 5] "baseball"; > val it = (true, "all") : bool * string - alt [len 5, len 4, len 2] "abc"; > val it = (true, "c") : bool * string |
| Name | seq |
| Type | ('a -> bool * 'a) list -> 'a -> bool * 'a(This is like alt.) |
| What it does | (seq stands for "sequence.") Takes a list of curried
functions, applies the functions one after the other, in order, and succeeds
if and only if the complete sequence matches. |
| Examples |
- seq [match "a", arbno match "p", notany "x", match "e"] "apple";
> val it = (true, "") : bool * string
- seq [arbno notany "(", match "(*", arbno notany "*", match "*)"]
|
Turn in: A floppy containing source code and a transcript of test results.
Due dates: Monday, April 30 and Wednesday, May 2.