Difference between revisions of "SML Practice Problems C"
(7 intermediate revisions by the same user not shown) | |||
Line 2: | Line 2: | ||
[https://www.coursera.org/learn/programming-languages/supplement/cVK0L/extra-practice-problems Coursera Week 3 Extra Practice Problems] | [https://www.coursera.org/learn/programming-languages/supplement/cVK0L/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 and then move on to these practice problems if you want more. | ||
+ | |||
=Code To Implement= | =Code To Implement= | ||
− | {{SMLToImplement| | + | {{SMLToImplement|practice_c|compose_opt<br>do_until<br/>factorial<br/>fixed_point<br/>map2<br/>app_all<br/>partition<br/>unfold<br/>map<br/>filter<br/>foldl<br/>map_tree<br/>fold_tree<br/>filter_tree|practice_c}} |
==compose_opt== | ==compose_opt== | ||
Line 12: | Line 17: | ||
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 <code>do_until</code> to write a function < | + | Use <code>do_until</code> to write a function <nowiki>fixed_point: (''a -> ''a) -> ''a -> ''a</nowiki> 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 <nowiki>''</nowiki> to indicate equality types.) |
+ | |||
==map2== | ==map2== | ||
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. | 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 | + | Write a function <code>app_all : (’b -> ’c list) -> (’a -> ’b list) -> ’a -> ’c list</code>, so that: <code>app_all f g x</code> will apply <code>f</code> to every element of the list <code>g x</code> and concatenate the results into a single list. For example, for <code>fun f n = [n, 2 * n, 3 * n]</code>, we have <code>app_all f f 1 = [1, 2, 3, 2, 4, 6, 3, 6, 9]</code>. |
==foldr== | ==foldr== | ||
− | Implement | + | Implement <code>[https://smlfamily.github.io/Basis/list.html#SIG:LIST.foldr:VAL List.foldr]</code> |
+ | |||
==partition== | ==partition== | ||
− | Write a function | + | Write a function <code>partition : (’a -> bool) -> ’a list -> ’a list * ’a list</code> 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== | ==unfold== | ||
− | Write a function | + | Write a function <code>unfold : (’a -> (’b * ’a) option) -> ’a -> ’b list</code> that produces a list of <code>’b</code> values given a "seed" of type <code>’a</code> and a function that given a seed produces <code>SOME</code> of a pair of a <code>’b</code> value and a new seed, or <code>NONE</code> if it is done seeding. For example, here is an elaborate way to count down from 5: <code>unfold (fn n => if n = 0 then NONE else SOME(n, n-1)) 5 = [5, 4, 3, 2, 1]</code>. |
==factorial== | ==factorial== | ||
− | Use | + | Use <code>unfold</code> and <code>foldl</code> to implement <code>factorial</code>. |
==map== | ==map== | ||
− | Implement | + | Implement <code>map</code> using <code>List.foldr</code>. |
==filter== | ==filter== | ||
− | Implement | + | Implement <code>filter</code> using <code>List.foldr</code>. |
==foldl== | ==foldl== | ||
− | Implement | + | Implement <code>foldl</code> using <code>foldr</code> on functions. (This is challenging.) |
==map_tree, fold_tree, filter_tree== | ==map_tree, fold_tree, filter_tree== | ||
− | Define a (polymorphic) type for binary trees where data is at internal nodes but not at leaves. Define | + | Define a (polymorphic) type for binary trees where data is at internal nodes but not at leaves. Define <code>map</code> and <code>fold</code> functions over such trees. You can define <code>filter</code> 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= | =Test= | ||
− | {{SMLUnitTest| | + | {{SMLUnitTest|practice_c|practice_c}} |
Latest revision as of 09:03, 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 and then move on to these practice problems if you want more.
Code To Implement
file: | src/main/sml/practice_c/practice_c.sml | |
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 app_all : (’b -> ’c list) -> (’a -> ’b list) -> ’a -> ’c list
, so that: app_all f g x
will apply f
to every element of the list g x
and concatenate the results into a single list. For example, for fun f n = [n, 2 * n, 3 * n]
, we have app_all f f 1 = [1, 2, 3, 2, 4, 6, 3, 6, 9]
.
foldr
Implement List.foldr
partition
Write a function 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 unfold : (’a -> (’b * ’a) option) -> ’a -> ’b list
that produces a list of ’b
values given a "seed" of type ’a
and a function that given a seed produces SOME
of a pair of a ’b
value and a new seed, or NONE
if it is done seeding. For example, here is an elaborate way to count down from 5: unfold (fn n => if n = 0 then NONE else SOME(n, n-1)) 5 = [5, 4, 3, 2, 1]
.
factorial
Use unfold
and foldl
to implement factorial
.
map
Implement map
using List.foldr
.
filter
Implement filter
using List.foldr
.
foldl
Implement foldl
using 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 map
and fold
functions over such trees. You can define 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_practice_c.sml | |
source folder: | src/test/sml/practice_c |