SML Practice Problems B

credit: Pavel Lepin and Charilaos Skiadas

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 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_natfor 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