Difference between revisions of "Concat Length List Assignment"

From CSE425S Wiki
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...")
 
 
(One intermediate revision by the same user not shown)
Line 13: Line 13:
  
 
==functions==
 
==functions==
<nowiki>structure ConcatLengthList : sig
+
<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</nowiki>
+
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===
    fun concat(a_cll : 'a cllist, b_cll : 'a cllist) : 'a cllist=
+
<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===
    fun to_list(cll : 'a cllist) : 'a 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

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.

SML Error Messages