Difference between revisions of "Concat Length List Assignment"
Jump to navigation
Jump to search
(Created page with "=Motivation= We will gain experience designing an abstract data type. Specifically, we will create a list-like structure that supports querying the length on O(1) time and co...") |
(→cons) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 13: | Line 13: | ||
==functions== | ==functions== | ||
| − | + | <syntaxhighlight lang="sml"> | |
| + | structure ConcatLengthList : sig | ||
type 'a cllist = unit | type 'a cllist = unit | ||
val from_list : 'a list -> 'a cllist | val from_list : 'a list -> 'a cllist | ||
| Line 21: | Line 22: | ||
val foldl : ('a * 'b -> 'b) * 'b * 'a cllist -> 'b | val foldl : ('a * 'b -> 'b) * 'b * 'a cllist -> 'b | ||
val to_list : 'a cllist -> 'a list | val to_list : 'a cllist -> 'a list | ||
| − | end</ | + | end |
| + | </syntaxhighlight> | ||
===from_list=== | ===from_list=== | ||
| + | <syntaxhighlight lang="sml"> | ||
fun from_list(xs : 'a list) : 'a cllist = | fun from_list(xs : 'a list) : 'a cllist = | ||
raise Fail "NotYetImplemented" | raise Fail "NotYetImplemented" | ||
| + | </syntaxhighlight> | ||
===length=== | ===length=== | ||
| + | <syntaxhighlight lang="sml"> | ||
fun length(cll : 'a cllist) : int = | fun length(cll : 'a cllist) : int = | ||
raise Fail "NotYetImplemented" | raise Fail "NotYetImplemented" | ||
| + | </syntaxhighlight> | ||
| Line 36: | Line 42: | ||
===cons=== | ===cons=== | ||
| + | <syntaxhighlight lang="sml"> | ||
fun cons(x : 'a, cll : 'a cllist) : 'a cllist = | fun cons(x : 'a, cll : 'a cllist) : 'a cllist = | ||
raise Fail "NotYetImplemented" | raise Fail "NotYetImplemented" | ||
| + | </syntaxhighlight> | ||
| − | + | Analogous to [https://smlfamily.github.io/Basis/list.html#SIG:LIST.:::TY List.::]. | |
===concat=== | ===concat=== | ||
| − | + | <syntaxhighlight lang="sml"> | |
| + | fun concat(a_cll : 'a cllist, b_cll : 'a cllist) : 'a cllist= | ||
raise Fail "NotYetImplemented" | raise Fail "NotYetImplemented" | ||
| − | + | </syntaxhighlight> | |
Analogous to [https://smlfamily.github.io/Basis/list.html#SIG:LIST.@:VAL List.@]. | Analogous to [https://smlfamily.github.io/Basis/list.html#SIG:LIST.@:VAL List.@]. | ||
===foldl=== | ===foldl=== | ||
| + | <syntaxhighlight lang="sml"> | ||
fun foldl(f : ('a * 'b) -> 'b, init : 'b, cll : 'a cllist) : 'b = | fun foldl(f : ('a * 'b) -> 'b, init : 'b, cll : 'a cllist) : 'b = | ||
raise Fail "NotYetImplemented" | raise Fail "NotYetImplemented" | ||
| + | </syntaxhighlight> | ||
| Line 55: | Line 66: | ||
===to_list=== | ===to_list=== | ||
| − | + | <syntaxhighlight lang="sml"> | |
| + | fun to_list(cll : 'a cllist) : 'a list = | ||
raise Fail "NotYetImplemented" | raise Fail "NotYetImplemented" | ||
| + | </syntaxhighlight> | ||
| + | |||
=Testing= | =Testing= | ||
{{SMLUnitTesting|run_concat_length_list_testing|warmup_concat_length_list}} | {{SMLUnitTesting|run_concat_length_list_testing|warmup_concat_length_list}} | ||
Latest revision as of 18:43, 7 July 2023
Contents
Motivation
We will gain experience designing an abstract data type.
Specifically, we will create a list-like structure that supports querying the length on O(1) time and concatenating two lists in O(1) time.
Code to Implement
types
cllist
(* TODO: replace unit with the datatype/type synonym(s) you decide upon *) type 'a cllist = unit
NOTE: type synonyms do NOT support self-reference.
functions
structure ConcatLengthList : sig
type 'a cllist = unit
val from_list : 'a list -> 'a cllist
val length : 'a cllist -> int
val cons : 'a * 'a cllist -> 'a cllist
val concat : 'a cllist * 'a cllist -> 'a cllist
val foldl : ('a * 'b -> 'b) * 'b * 'a cllist -> 'b
val to_list : 'a cllist -> 'a list
end
from_list
fun from_list(xs : 'a list) : 'a cllist =
raise Fail "NotYetImplemented"
length
fun length(cll : 'a cllist) : int =
raise Fail "NotYetImplemented"
Functionally analogous to List.length, but with O(1) performance.
cons
fun cons(x : 'a, cll : 'a cllist) : 'a cllist =
raise Fail "NotYetImplemented"
Analogous to List.::.
concat
fun concat(a_cll : 'a cllist, b_cll : 'a cllist) : 'a cllist=
raise Fail "NotYetImplemented"
Analogous to List.@.
foldl
fun foldl(f : ('a * 'b) -> 'b, init : 'b, cll : 'a cllist) : 'b =
raise Fail "NotYetImplemented"
Analogous to List.foldl.
to_list
fun to_list(cll : 'a cllist) : 'a list =
raise Fail "NotYetImplemented"
Testing
| source folder: | src/test/sml/warmup_concat_length_list |
| how to run with CM.make verbosity off: | sml -Ccm.verbose=false run_concat_length_list_testing.sml |
| how to run with CM.make verbosity on: | sml run_concat_length_list_testing.sml |
note: ensure that you have removed all printing to receive credit for any assignment.
