Difference between revisions of "SML Practice Problems B"
Line 54: | Line 54: | ||
<nowiki>datatype nat = ZERO | SUCC of nat</nowiki> | <nowiki>datatype nat = ZERO | SUCC of nat</nowiki> | ||
− | A "natural" number is either zero, or the "successor" of a another integer. So for example the number 1 is just | + | A "natural" number is either zero, or the "successor" of a another integer. So for example the number 1 is just <code>SUCC ZERO</code>, the number 2 is <code>SUCC (SUCC ZERO)</code>, and so on. |
===is_positive=== | ===is_positive=== | ||
Line 63: | Line 63: | ||
===nat_to_int=== | ===nat_to_int=== | ||
− | Write | + | Write <code>nat_to_int : nat -> int</code>, which given a "natural number" returns the corresponding <code>int</code>. For example, <code>nat_to_int (SUCC (SUCC ZERO)) = 2</code>. |
===int_to_nat=== | ===int_to_nat=== | ||
− | Write | + | Write <code>int_to_nat : int -> nat</code> which given an integer returns a "natural number" representation for it, or throws a \verb|Negative|Negative exception if the integer was negative. |
+ | (Do not use <code>nat_to_int<code> or <code>int_to_nat</code>for the following functions -- it makes them too easy.) | ||
===add=== | ===add=== | ||
− | Write | + | Write <code>add : nat * nat -> nat</code> to perform addition. |
===sub=== | ===sub=== | ||
− | Write | + | Write <code>sub : nat * nat -> nat</code> to perform subtraction. (Hint: Use <code>pred</code>.) |
===mult=== | ===mult=== | ||
− | Write | + | Write <code>mult : nat * nat -> nat</code> to perform multiplication. (Hint: Use <code>add</code>.) |
===less_than=== | ===less_than=== | ||
− | Write | + | Write <code>less_than : nat * nat -> bool</code> to return <code>true</code> when the first argument is less than the second. |
==intSet== | ==intSet== |
Revision as of 06:20, 24 September 2020
credit: Pavel Lepin and Charilaos Skiadas
Coursera Week 3 Extra Practice Problems
Contents
Code To Implement
file: | src/main/sml/practice2/practice2.sml | ![]() |
functions: | pass_or_fail has_passed number_passed number_misgraded ... |
Previous Practice Problems With Pattern Matching
Consider any of the extra Practice Problems from Section 1 and redo them using pattern matching.
Student Grades
Use these type definitions:
type student_id = int type grade = int (* must be in 0 to 100 range *) type final_grade = { id : student_id, grade : grade option } datatype pass_fail = pass | fail
Note that the grade might be absent (presumably because the student unregistered from the course).
pass_or_fail
Write a function pass_or_fail
of type {grade : int option, id : 'a} -> pass_fail
that takes a final_grade
(or, as the type indicates, a more general type) and returns pass
if the grade field contains SOME i
for an i≥75 (else fail
).
has_passed
Using pass_or_fail
as a helper function, write a function has_passed
of type {grade : int option, id : 'a} -> bool
that returns true
if and only if the the grade field contains SOME i
for an i≥75.
number_passed
Using has_passed
as a helper function, write a function number_passed
that takes a list of type final_grade
(or a more general type) and returns how many list elements have passing (again, ≥75) grades.
number_misgraded
Write a function number_misgraded
of type (pass_fail * final_grade) list -> int
that indicates how many list elements are "mislabeled" where mislabeling means a pair (pass,x)
where has_passed x
is false or (fail,x)
where has_passed x
is true.
Tree
Use these type definitions:
datatype 'a tree = leaf | node of { value : 'a, left : 'a tree, right : 'a tree } datatype flag = leave_me_alone | prune_me
tree_height
Write a function tree_height
that accepts an 'a tree
and evaluates to a height of this tree. The height of a tree is the length of the longest path to a leaf. Thus the height of a leaf is 0
.
sum_tree
Write a function sum_tree
that takes an int tree
and evaluates to the sum of all values in the nodes.
gardener
Write a function gardener
of type flag tree -> flag tree
such that its structure is identical to the original tree except all nodes of the input containing prune_me
are (along with all their descendants) replaced with a leaf.
List and Option
Re-implement various functions provided in the SML standard libraries for lists and options. See http://sml-family.org/Basis/list.html and http://sml-family.org/Basis/option.html. Good examples include last
, take
, drop
, concat
, getOpt
, and join
.
Natural Numbers
Use this type definition for natural numbers:
datatype nat = ZERO | SUCC of nat
A "natural" number is either zero, or the "successor" of a another integer. So for example the number 1 is just SUCC ZERO
, the number 2 is SUCC (SUCC ZERO)
, and so on.
is_positive
Write is_positive : nat -> bool
, which given a "natural number" returns whether that number is positive (i.e. not zero).
pred
Write pred : nat -> nat
, which given a "natural number" returns its predecessor. Since 0 does not have a predecessor in the natural numbers, throw an exception \verb|Negative|Negative (will need to define it first).
nat_to_int
Write nat_to_int : nat -> int
, which given a "natural number" returns the corresponding int
. For example, nat_to_int (SUCC (SUCC ZERO)) = 2
.
int_to_nat
Write int_to_nat : int -> nat
which given an integer returns a "natural number" representation for it, or throws a \verb|Negative|Negative exception if the integer was negative.
(Do not use nat_to_int
or
int_to_nat
for the following functions -- it makes them too easy.)
add
Write add : nat * nat -> nat
to perform addition.
sub
Write sub : nat * nat -> nat
to perform subtraction. (Hint: Use pred
.)
mult
Write mult : nat * nat -> nat
to perform multiplication. (Hint: Use add
.)
less_than
Write less_than : nat * nat -> bool
to return true
when the first argument is less than the second.
intSet
The remaining problems use this datatype, which represents sets of integers:
datatype intSet =
Elems of int list (*list of integers, possibly with duplicates to be ignored*)
| Range of { from : int, to : int } (* integers from one number to another *)
| Union of intSet * intSet (* union of the two sets *)
| Intersection of intSet * intSet (* intersection of the two sets *)
isEmpty
Write isEmpty : intSet -> bool
that determines if the set is empty or not.
contains
Write contains: intSet * int -> bool
that returns whether the set contains a certain element or not.
toList
Write toList : intSet -> int list
that returns a list with the set's elements, without duplicates.
Test
file:
unit_test_practice2.sml
source folder:
src/test/sml/practice2