Difference between revisions of "SML Practice Problems B"
(→intSet) |
|||
(12 intermediate revisions by the same user not shown) | |||
Line 2: | Line 2: | ||
[https://www.coursera.org/learn/programming-languages/supplement/JXL99/extra-practice-problems Coursera Week 3 Extra Practice Problems] | [https://www.coursera.org/learn/programming-languages/supplement/JXL99/extra-practice-problems Coursera Week 3 Extra Practice Problems] | ||
+ | =Warming Up= | ||
+ | Given that warmups are already not strictly required, it seems strange to call these optional warmups. | ||
+ | |||
+ | It is suggested that you complete the curated warmups first: | ||
+ | |||
+ | * [[Sum_Scan_With_Pattern_Matching_Assignment|Sum Scan w/ Pattern Matching]] | ||
+ | * [[Is_Strictly_Ascending_With_Pattern_Matching_Assignment|Is Strictly Ascending w/ Pattern Matching]] | ||
+ | * [[Sum_Distances_To_Origin_Assignment|Sum Distances To Origin]] | ||
+ | * [[Remove_First_Assignment|Remove First]] | ||
+ | |||
+ | and then move on to these practice problems if you want more. | ||
+ | |||
=Code To Implement= | =Code To Implement= | ||
− | {{SMLToImplement| | + | {{SMLToImplement|practice_b|pass_or_fail<br/>has_passed<br/>number_passed<br/>number_misgraded<br/>...|practice_b}} |
==Previous Practice Problems With Pattern Matching== | ==Previous Practice Problems With Pattern Matching== | ||
Line 25: | Line 37: | ||
===number_passed=== | ===number_passed=== | ||
− | Using | + | Using <code>has_passed</code> as a helper function, write a function <code>number_passed</code> that takes a list of type <code>final_grade</code> (or a more general type) and returns how many list elements have passing (again, ≥75) grades. |
===number_misgraded=== | ===number_misgraded=== | ||
− | Write a function | + | Write a function <code>number_misgraded</code> of type <code>(pass_fail * final_grade) list -> int</code> that indicates how many list elements are "mislabeled" where mislabeling means a pair <code>(pass,x)</code> where <code>has_passed x</code> is false or <code>(fail,x)</code> where <code>has_passed x</code> is true. |
− | == | + | ==Tree== |
Use these type definitions: | Use these type definitions: | ||
Line 38: | Line 50: | ||
===tree_height=== | ===tree_height=== | ||
− | Write a function | + | Write a function <code>tree_height</code> that accepts an <code>'a tree</code> 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 <code>0</code>. |
===sum_tree=== | ===sum_tree=== | ||
− | Write a function | + | Write a function <code>sum_tree</code> that takes an <code>int tree</code> and evaluates to the sum of all values in the nodes. |
===gardener=== | ===gardener=== | ||
− | Write a function | + | Write a function <code>gardener</code> of type <code>flag tree -> flag tree</code> such that its structure is identical to the original tree except all nodes of the input containing <code>prune_me</code> 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 | + | Re-implement various functions provided in the SML standard libraries for lists and options. See https://smlfamily.github.io/Basis/list.html andhttps://smlfamily.github.io/Basis/option.html. Good examples include <code>last</code>, <code>take</code>, <code>drop</code>, <code>concat</code>, <code>getOpt</code>, and <code>join</code>. |
− | == | + | ==Natural Numbers== |
Use this type definition for natural numbers: | Use this type definition for natural numbers: | ||
<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=== | ||
− | Write | + | Write <code>is_positive : nat -> bool</code>, which given a "natural number" returns whether that number is positive (i.e. not zero). |
===pred=== | ===pred=== | ||
− | Write | + | Write <code>pred : nat -> nat</code>, which given a "natural number" returns its predecessor. Since 0 does not have a predecessor in the natural numbers, throw an exception <code>Negative</code> (will need to define it first). |
===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 <code>Negative</code> 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== | ||
Line 98: | Line 115: | ||
=Test= | =Test= | ||
− | {{SMLUnitTest| | + | {{SMLUnitTest|practice_b|practice_b}} |
Latest revision as of 09:02, 9 February 2022
credit: Pavel Lepin and Charilaos Skiadas
Coursera Week 3 Extra Practice Problems
Contents
Warming Up
Given that warmups are already not strictly required, it seems strange to call these optional warmups.
It is suggested that you complete the curated warmups first:
- Sum Scan w/ Pattern Matching
- Is Strictly Ascending w/ Pattern Matching
- Sum Distances To Origin
- Remove First
and then move on to these practice problems if you want more.
Code To Implement
file: | src/main/sml/practice_b/practice_b.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 https://smlfamily.github.io/Basis/list.html andhttps://smlfamily.github.io/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 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 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_practice_b.sml | |
source folder: | src/test/sml/practice_b |