Difference between revisions of "Pattern Matching Assignment"
Line 71: | Line 71: | ||
<nowiki>datatype pattern = Wildcard | <nowiki>datatype pattern = Wildcard | ||
− | + | | Variable of string | |
− | + | | UnitP | |
− | + | | ConstP of int | |
− | + | | TupleP of pattern list | |
− | + | | ConstructorP of string * pattern | |
datatype valu = Const of int | datatype valu = Const of int | ||
| Unit | | Unit | ||
Line 83: | Line 83: | ||
Given valu v and pattern p, either p matches v or not. If it does, the match produces a list of string * valu pairs; order in the list does not matter. The rules for matching should be unsurprising: | Given valu v and pattern p, either p matches v or not. If it does, the match produces a list of string * valu pairs; order in the list does not matter. The rules for matching should be unsurprising: | ||
− | * Wildcard matches everything and produces the empty list of bindings. | + | * <code>Wildcard</code> matches everything and produces the empty list of bindings. |
− | * Variable s matches any value v and produces the one-element list holding (s,v). | + | * <code>Variable s</code> matches any value v and produces the one-element list holding (s,v). |
− | * UnitP matches only Unit and produces the empty list of bindings. | + | * <code>UnitP</code> matches only <code>Unit</code> and produces the empty list of bindings. |
− | * ConstP 17 matches only Const 17 and produces the empty list of bindings (and similarly for other integers). | + | * <code>ConstP 17</code> matches only <code>Const 17</code> and produces the empty list of bindings (and similarly for other integers). |
− | * TupleP ps matches a value of the form Tuple vs if ps and vs have the same length and for all i, the ith element of ps matches the ith element of vs. The list of bindings produced is all the lists from the nested pattern matches appended together. | + | * <code>TupleP ps</code> matches a value of the form <code>Tuple vs</code> if ps and vs have the same length and for all i, the ith element of ps matches the ith element of vs. The list of bindings produced is all the lists from the nested pattern matches appended together. |
− | * ConstructorP(s1,p) matches Constructor(s2,v) if s1 and s2 are the same string (you can compare them with =) and p matches v. The list of bindings produced is the list from the nested pattern match. We call the strings s1 and s2 the constructor name. | + | * <code>ConstructorP(s1,p)</code> matches <code>Constructor(s2,v)</code> if s1 and s2 are the same string (you can compare them with =) and p matches v. The list of bindings produced is the list from the nested pattern match. We call the strings s1 and s2 the constructor name. |
* Nothing else matches. | * Nothing else matches. | ||
− | ===9) === | + | ===9) count_wildcards, count_wild_and_variable_lengths, and count_some_var=== |
− | + | (This problem uses the pattern datatype but is not really about pattern-matching.) A function <code>g</code> has been provided to you. | |
+ | ====9a) count_wildcards==== | ||
+ | Use g to define a function <code>count_wildcards</code> that takes a pattern and returns how many <code>Wildcard</code> | ||
+ | patterns it contains. | ||
+ | ====9b) count_wild_and_variable_lengths==== | ||
+ | Use g to define a function <code>count_wild_and_variable_lengths</code> that takes a pattern and returns | ||
+ | the number of <code>Wildcard</code> patterns it contains plus the sum of the string lengths of all the variables | ||
+ | in the variable patterns it contains. (Use [https://smlfamily.github.io/Basis/string.html#SIG:STRING.size:VAL String.size]. We care only about variable names; the | ||
+ | constructor names are not relevant.) | ||
+ | ====9c) count_some_var==== | ||
+ | Use g to define a function <code>count_some_var</code> that takes a string and a pattern (as a pair) and | ||
+ | returns the number of times the string appears as a variable in the pattern. We care only about | ||
+ | variable names; the constructor names are not relevant. | ||
===10) === | ===10) === | ||
Revision as of 03:39, 8 October 2020
Contents
Hints and Gotchas
Instructions
All credit for this assignment goes to Prof. Grossman and his team at UW. UW or Coursera
Code To Implement
You will define several SML functions. Many will be very short because they will use other higher-order functions. You may use functions in ML’s library; the problems point you toward the useful functions and often require that you use them. The sample solution is about 120 lines, including the provided code, but not including the challenge problem. This assignment is probably more difficult than Homework 2 even though (perhaps because) many of the problems have 1-line answers.
String Functions
1) only_captials
Write a function only_capitals
that takes a string list
and returns a string list
that has only
the strings in the argument that start with an uppercase letter. Assume all strings have at least 1
character. Use List.filter, Char.isUpper, and String.sub to make a 1-2 line solution.
2) longest_string1
Write a function longest_string1
that takes a string list
and returns the longest string
in the
list. If the list is empty, return "". In the case of a tie, return the string closest to the beginning of the
list. Use foldl, String.size, and no recursion (other than the implementation of foldl is recursive).
3) longest_string2
Write a function longest_string2
that is exactly like longest_string1
except in the case of ties
it returns the string closest to the end of the list. Your solution should be almost an exact copy of
longest_string1. Still use foldl and String.size.
4) longest_string_helper, longest_string3, and longest_string4
Write functions longest_string_helper
, longest_string3
, and longest_string4
such that:
longest_string3
has the same behavior aslongest_string1
andlongest_string4
has the same behavior aslongest_string2
.longest_string_helper
has type(int * int -> bool) -> string list -> string
(notice the currying). This function will look a lot likelongest_string1
andlongest_string2
but is more general because it takes a function as an argument.- If
longest_string_helper
is passed a function that behaves like > (so it returns true exactly when its first argument is strictly greater than its second), then the function returned has the same behavior aslongest_string1
. longest_string3
andlongest_string4
are defined with val-bindings and partial applications oflongest_string_helper
.
5) longest_capitalized
Write a function longest_capitalized
that takes a string list
and returns the longest string in
the list that begins with an uppercase letter, or "" if there are no such strings. Assume all strings
have at least 1 character. Use a val-binding and the ML library’s o operator for composing functions.
Resolve ties like in problem 2.
6) rev_string
Write a function rev_string
that takes a string
and returns the string
that is the same characters in
reverse order. Use ML’s o operator, the library function rev for reversing lists, and two library functions
in the String module. (Browse the module documentation to find the most useful functions.)
Utilities For Pattern Matching
The next two problems involve writing functions over lists that will be useful in later problems.
7) first_answer
Write a function first_answer
of type (’a -> ’b option) -> ’a list -> ’b
(notice the 2 arguments are curried). The first argument should be applied to elements of the second argument in order
until the first time it returns SOME v
for some v and then v is the result of the call to first_answer
.
If the first argument returns NONE
for all list elements, then first_answer
should raise the exception
NoAnswer
. Hints: Sample solution is 5 lines and does nothing fancy.
8) all_answers
Write a function all_answers
of type (’a -> ’b list option) -> ’a list -> ’b list option
(notice the 2 arguments are curried). The first argument should be applied to elements of the second
argument. If it returns NONE
for any element, then the result for all_answers
is NONE
. Else the
calls to the first argument will have produced SOME lst1, SOME lst2, ... SOME lstn
and the result of
all_answers
is SOME lst
where lst
is lst1, lst2, ..., lstn
appended together (order doesn’t matter).
Hints: The sample solution is 8 lines. It uses a helper function with an accumulator and uses @. Note
all_answers f []
should evaluate to SOME []
.
Pattern Matching
The remaining problems use these type definitions, which are inspired by the type definitions an ML implementation would use to implement pattern matching:
datatype pattern = Wildcard | Variable of string | UnitP | ConstP of int | TupleP of pattern list | ConstructorP of string * pattern datatype valu = Const of int | Unit | Tuple of valu list | Constructor of string * valu
Given valu v and pattern p, either p matches v or not. If it does, the match produces a list of string * valu pairs; order in the list does not matter. The rules for matching should be unsurprising:
Wildcard
matches everything and produces the empty list of bindings.Variable s
matches any value v and produces the one-element list holding (s,v).UnitP
matches onlyUnit
and produces the empty list of bindings.ConstP 17
matches onlyConst 17
and produces the empty list of bindings (and similarly for other integers).TupleP ps
matches a value of the formTuple vs
if ps and vs have the same length and for all i, the ith element of ps matches the ith element of vs. The list of bindings produced is all the lists from the nested pattern matches appended together.ConstructorP(s1,p)
matchesConstructor(s2,v)
if s1 and s2 are the same string (you can compare them with =) and p matches v. The list of bindings produced is the list from the nested pattern match. We call the strings s1 and s2 the constructor name.- Nothing else matches.
9) count_wildcards, count_wild_and_variable_lengths, and count_some_var
(This problem uses the pattern datatype but is not really about pattern-matching.) A function g
has been provided to you.
9a) count_wildcards
Use g to define a function count_wildcards
that takes a pattern and returns how many Wildcard
patterns it contains.
9b) count_wild_and_variable_lengths
Use g to define a function count_wild_and_variable_lengths
that takes a pattern and returns
the number of Wildcard
patterns it contains plus the sum of the string lengths of all the variables
in the variable patterns it contains. (Use String.size. We care only about variable names; the
constructor names are not relevant.)
9c) count_some_var
Use g to define a function count_some_var
that takes a string and a pattern (as a pair) and
returns the number of times the string appears as a variable in the pattern. We care only about
variable names; the constructor names are not relevant.
10)
11)
12)
Challenge Problem
13) typecheck_patterns
Type Summary
val g = fn : (unit -> int) -> (string -> int) -> pattern -> int val only_capitals = fn : string list -> string list val longest_string1 = fn : string list -> string val longest_string2 = fn : string list -> string val longest_string_helper = fn : (int * int -> bool) -> string list -> string val longest_string3 = fn : string list -> string val longest_string4 = fn : string list -> string val longest_capitalized = fn : string list -> string val rev_string = fn : string -> string val first_answer = fn : (’a -> ’b option) -> ’a list -> ’b val all_answers = fn : (’a -> ’b list option) -> ’a list -> ’b list option val count_wildcards = fn : pattern -> int val count_wild_and_variable_lengths = fn : pattern -> int val count_some_var = fn : string * pattern -> int val check_pat = fn : pattern -> bool val match = fn : valu * pattern -> (string * valu) list option val first_match = fn : valu -> pattern list -> (string * valu) list option
val typecheck_patterns = fn : (string * string * typ) list * pattern list -> typ option
Test
file: | unit_test_hw3.sml | |
source folder: | src/test/sml/hw3 |
Test your functions. The unit tests you have been provided are intentionally minimal.
Pledge, Acknowledgments, Citations
file: | lab-3-card-game-date-pledge-acknowledgments-citations.txt |
More info about the Honor Pledge