Difference between revisions of "SML Practice Problems B"

From CSE425S Wiki
Jump to navigation Jump to search
 
(9 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|practice2|pass_or_fail<br/>has_passed<br/>number_passed<br/>number_misgraded<br/>...|practice2}}
+
{{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 \verb|has_passed|has_passed as a helper function, write a function \verb|number_passed|number_passed that takes a list of type \verb|final_grade|final_grade (or a more general type) and returns how many list elements have passing (again, \geq 75≥75) grades.
+
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 \verb|number_misgraded|number_misgraded of type \verb|(pass_fail * final_grade) list -> int|(pass_fail * final_grade) list -> int that indicates how many list elements are "mislabeled" where mislabeling means a pair \verb|(pass,x)|(pass,x) where \verb|has_passed x|has_passed x is \verb|false|false or \verb|(fail,x)|(fail,x) where \verb|has_passed x|has_passed x is \verb|true|true.
+
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==
 
==Tree==
Line 47: Line 59:
  
 
==List and Option==
 
==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 <code>last</code>, <code>take</code>, <code>drop</code>, <code>concat</code>, <code>getOpt</code>, and <code>join</code>.
+
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==
 
==Natural Numbers==
Line 54: Line 66:
 
  <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 \verb|SUCC ZERO|SUCC ZERO, the number 2 is \verb|SUCC (SUCC ZERO)|SUCC (SUCC ZERO), and so on.
+
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 \verb|is_positive : nat -> bool|is_positive : nat -> bool, which given a "natural number" returns whether that number is positive (i.e. not zero).
+
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 \verb|pred : nat -> nat|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).
+
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 \verb|nat_to_int : nat -> int|nat_to_int : nat -> int, which given a "natural number" returns the corresponding \verb|int|int. For example, \verb|nat_to_int (SUCC (SUCC ZERO)) = 2|nat_to_int (SUCC (SUCC ZERO)) = 2. (Do not use this function for problems 13-16 -- it makes them too easy.)
+
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 \verb|int_to_nat : int -> nat|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. (Again, do not use this function in the next few problems.)
+
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 \verb|add : nat * nat -> nat|add : nat * nat -> nat to perform addition.
+
Write <code>add : nat * nat -> nat</code> to perform addition.
  
 
===sub===
 
===sub===
Write \verb|sub : nat * nat -> nat|sub : nat * nat -> nat to perform subtraction. (Hint: Use \verb|pred|pred.)
+
Write <code>sub : nat * nat -> nat</code> to perform subtraction. (Hint: Use <code>pred</code>.)
  
 
===mult===
 
===mult===
Write \verb|mult : nat * nat -> nat|mult : nat * nat -> nat to perform multiplication. (Hint: Use \verb|add|add.)
+
Write <code>mult : nat * nat -> nat</code> to perform multiplication. (Hint: Use <code>add</code>.)
  
 
===less_than===
 
===less_than===
Write \verb|less_than : nat * nat -> bool|less_than : nat * nat -> bool to return \verb|true|true when the first argument is less than the second.
+
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|practice2|practice2}}
+
{{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

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:

and then move on to these practice problems if you want more.

Code To Implement

file: src/main/sml/practice_b/practice_b.sml Smlnj-logo.png
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