Difference between revisions of "SML Practice Problems C"

From CSE425S Wiki
Jump to navigation Jump to search
Line 7: Line 7:
 
==compose_opt==
 
==compose_opt==
 
Write a function <code>compose_opt : (’b -> ’c option) -> (’a -> ’b option) -> ’a -> ’c option</code> that composes two functions with "optional" values. If either function returns <code>NONE</code>, then the result is <code>NONE</code>.
 
Write a function <code>compose_opt : (’b -> ’c option) -> (’a -> ’b option) -> ’a -> ’c option</code> that composes two functions with "optional" values. If either function returns <code>NONE</code>, then the result is <code>NONE</code>.
 
 
==do_until==
 
==do_until==
 
Write a function <code>do_until : (’a -> ’a) -> (’a -> bool) -> ’a -> ’a</code>. <code>do_until f p x</code> will apply <code>f to x</code> and <code>f</code> again to that result and so on until <code>p x</code> is false. Example: <code>do_until (fn x => x div 2) (fn x => x mod 2 <> 1)</code> will evaluate to a function of type <code>int->int</code> that divides its argument by <code>2</code> until it reaches an odd number. In effect, it will remove all factors of <code>2</code> its argument.
 
Write a function <code>do_until : (’a -> ’a) -> (’a -> bool) -> ’a -> ’a</code>. <code>do_until f p x</code> will apply <code>f to x</code> and <code>f</code> again to that result and so on until <code>p x</code> is false. Example: <code>do_until (fn x => x div 2) (fn x => x mod 2 <> 1)</code> will evaluate to a function of type <code>int->int</code> that divides its argument by <code>2</code> until it reaches an odd number. In effect, it will remove all factors of <code>2</code> its argument.
 
==factorial==
 
==factorial==
 
Use <code>do_until</code> to implement <code>factorial</code>.
 
Use <code>do_until</code> to implement <code>factorial</code>.
 
 
==fixed_point==
 
==fixed_point==
Use \verb|do_until|do_until to write a function \verb|fixed_point: (''a -> ''a) -> ''a -> ''a|fixed_point: (’’a -> ’’a) -> ’’a -> ’’a that given a function \verb|f|f and an initial value \verb|x|x applies \verb|f|f to \verb|x|x until \verb|f x = x|f x = x. (Notice the use of '' to indicate equality types.)
+
Use <code>do_until</code> to write a function <code>fixed_point: (''a -> ''a) -> ''a -> ''a</code> that given a function <code>f</code> and an initial value <code>x</code> applies <code>f</code> to <code>x</code> until <code>f x = x</code>. (Notice the use of '' to indicate equality types.)
 
==map2==
 
==map2==
Write a function \verb|map2 : ('a -> 'b) -> 'a * 'a -> 'b * 'b|map2 : (’a -> ’b) -> ’a * ’a -> ’b * ’b that given a function that takes \verb|'a|’a values to \verb|'b|’b values and a pair of \verb|'a|’a values returns the corresponding pair of \verb|'b|’b values.
+
Write a function <code>map2 : (’a -> ’b) -> ’a * ’a -> ’b * ’b</code> that given a function that takes <code>’a</code> values to <code>’b</code> values and a pair of <code>’a</code> values returns the corresponding pair of <code>’b</code> values.
 
==app_all==
 
==app_all==
 
Write a function \verb|app_all : ('b -> 'c list) -> ('a -> 'b list) -> 'a -> 'c list|app_all : (’b -> ’c list) -> (’a -> ’b list) -> ’a -> ’c list, so that: \verb|app_all f g x|app_all f g x will apply \verb|f|f to every element of the list \verb|g x|g x and concatenate the results into a single list. For example, for \verb|fun f n = [n, 2 * n, 3 * n]|fun f n = [n, 2 * n, 3 * n], we have \verb|app_all f f 1 = [1, 2, 3, 2, 4, 6, 3, 6, 9]|app_all f f 1 = [1, 2, 3, 2, 4, 6, 3, 6, 9].
 
Write a function \verb|app_all : ('b -> 'c list) -> ('a -> 'b list) -> 'a -> 'c list|app_all : (’b -> ’c list) -> (’a -> ’b list) -> ’a -> ’c list, so that: \verb|app_all f g x|app_all f g x will apply \verb|f|f to every element of the list \verb|g x|g x and concatenate the results into a single list. For example, for \verb|fun f n = [n, 2 * n, 3 * n]|fun f n = [n, 2 * n, 3 * n], we have \verb|app_all f f 1 = [1, 2, 3, 2, 4, 6, 3, 6, 9]|app_all f f 1 = [1, 2, 3, 2, 4, 6, 3, 6, 9].

Revision as of 02:03, 6 October 2020

credit: Pavel Lepin and Charilaos Skiadas

Coursera Week 3 Extra Practice Problems

Code To Implement

file: src/main/sml/practice3/practice3.sml Smlnj-logo.png
functions: compose_opt
do_until
factorial
fixed_point
map2
app_all
partition
unfold
map
filter
foldl
map_tree
fold_tree
filter_tree

compose_opt

Write a function compose_opt : (’b -> ’c option) -> (’a -> ’b option) -> ’a -> ’c option that composes two functions with "optional" values. If either function returns NONE, then the result is NONE.

do_until

Write a function do_until : (’a -> ’a) -> (’a -> bool) -> ’a -> ’a. do_until f p x will apply f to x and f again to that result and so on until p x is false. Example: do_until (fn x => x div 2) (fn x => x mod 2 <> 1) will evaluate to a function of type int->int that divides its argument by 2 until it reaches an odd number. In effect, it will remove all factors of 2 its argument.

factorial

Use do_until to implement factorial.

fixed_point

Use do_until to write a function fixed_point: (a -> a) -> a -> a that given a function f and an initial value x applies f to x until f x = x. (Notice the use of to indicate equality types.)

map2

Write a function map2 : (’a -> ’b) -> ’a * ’a -> ’b * ’b that given a function that takes ’a values to ’b values and a pair of ’a values returns the corresponding pair of ’b values.

app_all

Write a function \verb|app_all : ('b -> 'c list) -> ('a -> 'b list) -> 'a -> 'c list|app_all : (’b -> ’c list) -> (’a -> ’b list) -> ’a -> ’c list, so that: \verb|app_all f g x|app_all f g x will apply \verb|f|f to every element of the list \verb|g x|g x and concatenate the results into a single list. For example, for \verb|fun f n = [n, 2 * n, 3 * n]|fun f n = [n, 2 * n, 3 * n], we have \verb|app_all f f 1 = [1, 2, 3, 2, 4, 6, 3, 6, 9]|app_all f f 1 = [1, 2, 3, 2, 4, 6, 3, 6, 9].

foldr

Implement \verb|List.foldr|List.foldr (see http://sml-family.org/Basis/list.html#SIG:LIST.foldr:VAL).

partition

Write a function \verb|partition : ('a -> bool) -> 'a list -> 'a list * 'a list|partition : (’a -> bool) -> ’a list -> ’a list * ’a list where the first part of the result contains the second argument elements for which the first element evaluates to true and the second part of the result contains the other second argument elements. Traverse the second argument only once.

unfold

Write a function \verb|unfold : ('a -> ('b * 'a) option) -> 'a -> 'b list|unfold : (’a -> (’b * ’a) option) -> ’a -> ’b list that produces a list of \verb|'b|’b values given a "seed" of type \verb|'a|’a and a function that given a seed produces \verb|SOME|SOME of a pair of a \verb|'b|’b value and a new seed, or \verb|NONE|NONE if it is done seeding. For example, here is an elaborate way to count down from 5: \verb|unfold (fn n => if n = 0 then NONE else SOME(n, n-1)) 5 = [5, 4, 3, 2, 1]|unfold (fn n => if n = 0 then NONE else SOME(n, n-1)) 5 = [5, 4, 3, 2, 1].

factorial

Use \verb|unfold|unfold and $\verb|foldl|$$ to implement factorial.

map

Implement \verb|map|map using \verb|List.foldr|List.foldr.

filter

Implement \verb|filter|filter using \verb|List.foldr|List.foldr.

foldl

Implement \verb|foldl|foldl using \verb|foldr|foldr on functions. (This is challenging.)

map_tree, fold_tree, filter_tree

Define a (polymorphic) type for binary trees where data is at internal nodes but not at leaves. Define \verb|map|map and \verb|fold|fold functions over such trees. You can define \verb|filter|filter as well where we interpret a "false" as meaning the entire subtree rooted at the node with data that produced false should be replaced with a leaf.

Test

file: unit_test_practice3.sml
source folder: src/test/sml/practice3