Concat Length List Assignment

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"


===concat===
<syntaxhighlight lang="sml">
	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