Difference between revisions of "Mutable List Assignment"

From CSE425S Wiki
Jump to navigation Jump to search
 
(18 intermediate revisions by the same user not shown)
Line 1: Line 1:
 +
=Background=
 +
==SML==
 +
===ref===
 +
{{:SML_Mutable_Ref}}
 +
 
=Code to Implement=
 
=Code to Implement=
−
==create_mutable_list_from_immutable_list==
+
==types==
−
  fun create_mutable_list_from_immutable_list(xs) : 'a mutable_list =  
+
===mutable_list===
−
     raise NotYetImplemented
+
<nowiki>(* TODO: replace unit with the datatype/type synonym(s) you decide upon *)
−
==create_empty_mutable_list==
+
type 'a mutable_list = unit</nowiki>
−
  fun create_empty_mutable_list() : 'a mutable_list =  
+
 
−
     raise NotYetImplemented
+
NOTE: type synonyms do NOT support self-reference.
 +
 
 +
===parrot===
 +
<nowiki>datatype parrot = PARTY | SHUFFLE | PORTAL_BLUE_LEFT | PORTAL_ORANGE_RIGHT</nowiki>
 +
 
 +
==functions==
 +
<nowiki>val construct_empty = fn : unit -> 'a mutable_list
 +
val length = fn : 'a mutable_list -> int
 +
val clear = fn : 'a mutable_list -> unit
 +
val add_to_front = fn : 'a mutable_list * 'a -> unit
 +
val add_to_back = fn : 'a mutable_list * 'a -> unit
 +
val contains = fn : ('a -> bool) * 'a mutable_list -> bool
 +
val nth = fn : 'a mutable_list * int -> 'a
 +
val construct_from_immutable = fn : 'a list -> 'a mutable_list
 +
val foldl = fn : ('a * 'b -> 'b) * 'b * 'a mutable_list -> 'b
 +
val to_immutable = fn : 'a mutable_list -> 'a list
 +
val map = fn : ('a -> 'b) * 'a mutable_list -> 'b mutable_list
 +
val copy = fn : 'a mutable_list -> 'a mutable_list
 +
val @ = fn : 'a mutable_list * 'a mutable_list -> 'a mutable_list
 +
val reverse = fn : 'a mutable_list -> unit</nowiki>
 +
 
 +
===construct_empty===
 +
fun construct_empty() : 'a mutable_list =
 +
    raise Fail "NotYetImplemented"
 +
 
 +
===length===
 +
fun length(mlist : 'a mutable_list) : int =
 +
    raise Fail "NotYetImplemented"
 +
 
 +
Functionally analogous to [https://smlfamily.github.io/Basis/list.html#SIG:LIST.length:VAL List.length], but with O(1) performance.
 +
 
 +
===clear===
 +
fun clear(mlist : 'a mutable_list) : unit =
 +
    raise Fail "NotYetImplemented"
 +
 
 +
===add_to_front===
 +
fun add_to_front(mlist : 'a mutable_list, value : 'a) : unit =
 +
    raise Fail "NotYetImplemented"
 +
 
 +
Analogous to [https://smlfamily.github.io/Basis/list.html#SIG:LIST.:::TY ::].
 +
 
 +
===add_to_back===
 +
fun add_to_back(mlist : 'a mutable_list, value : 'a) : unit =
 +
    raise Fail "NotYetImplemented"
 +
 
 +
===contains===
 +
fun contains(predicate : ('a -> bool), mlist : 'a mutable_list) : bool =
 +
    raise Fail "NotYetImplemented"
 +
 
 +
===nth===
 +
<nowiki>fun nth(mlist : 'a mutable_list, index : int) : 'a =
 +
    raise Fail "NotYetImplemented"</nowiki>
 +
 
 +
Analogous to [https://smlfamily.github.io/Basis/list.html#SIG:LIST.nth:VAL List.nth].
 +
 
 +
Note: raise [https://smlfamily.github.io/Basis/general.html#SIG:GENERAL.Subscript:EXN:SPEC Subscript] if out of bounds.
 +
 
 +
===construct_from_immutable===
 +
fun construct_from_immutable(values : 'a list) : 'a mutable_list =
 +
    raise Fail "NotYetImplemented"
 +
 
 +
===foldl===
 +
fun foldl(f : ('a * 'b -> 'b), init : 'b, mlist : 'a mutable_list) : 'b =
 +
    raise Fail "NotYetImplemented"
 +
 
 +
Analogous to [https://smlfamily.github.io/Basis/list.html#SIG:LIST.foldl:VAL List.foldl].
 +
 
 +
===to_immutable===
 +
  fun to_immutable(mlist : 'a mutable_list) : 'a list =
 +
    raise Fail "NotYetImplemented"
 +
 
 +
===map===
 +
fun map(f : ('a -> 'b), mlist : 'a mutable_list) : 'b mutable_list =
 +
     raise Fail "NotYetImplemented"
 +
 
 +
Analogous to [https://smlfamily.github.io/Basis/list.html#SIG:LIST.map:VAL List.map].
 +
 
 +
===copy===
 +
  fun copy(mlist : 'a mutable_list) : 'a mutable_list =
 +
     raise Fail "NotYetImplemented"
 +
 
 +
===@===
 +
fun a @ b =
 +
    raise Fail "NotYetImplemented"
 +
 
 +
Analogous to [https://smlfamily.github.io/Basis/list.html#SIG:LIST.@:VAL List.@].
 +
 
 +
Note: does NOT alias.
 +
 
 +
===reverse===
 +
fun reverse(mlist : 'a mutable_list) : unit =
 +
    raise Fail "NotYetImplemented"
 +
 
 +
Analogous to [https://smlfamily.github.io/Basis/list.html#SIG:LIST.rev:VAL List.rev]
  
−
==create_mutable_list_from_other_mutable_list==
+
===remove_arbitrary===
−
fun create_mutable_list_from_other_mutable_list(ml) : 'a mutable_list =  
 
−
    raise NotYetImplemented
 
  
−
==to_immutable==
+
  fun remove_arbitrary(mlist : 'a mutable_list) : 'a option =
−
  fun to_immutable(ml : 'a mutable_list) : 'a list =
+
     raise Fail "NotYetImplemented"
−
     raise NotYetImplemented
 
  
−
==length==
+
pick an arbitrary item in the mutable list and remove it.
−
fun length(ml : 'a mutable_list) : int =
 
−
    raise NotYetImplemented
 
  
−
==insert_at_front==
+
return NONE if the mutable list is of length 0 and SOME of the removed item otherwise.
−
fun insert_at_front(ml : 'a mutable_list, item : 'a) : unit =
 
−
    raise NotYetImplemented
 
  
−
==insert_at_back==
+
analogous to: nothing I can think of right now.
−
fun insert_at_back(ml : 'a mutable_list, item : 'a) : unit =
 
−
    raise NotYetImplemented
 
  
−
==remove_first_match==
+
=Testing=
−
fun remove_first_match(ml : ''a mutable_list, item : ''a) : bool =
+
{{SMLUnitTesting|run_mutable_list_testing|warmup_mutable_list}}
−
    raise NotYetImplemented
 
  
−
==concat==
+
=Parrots=
−
fun concat(a : 'a mutable_list, b : 'a mutable_list) : unit =
+
directory: src/main/sml/warmup_parrots/
−
    raise NotYetImplemented
 
  
−
==reverse==
+
  sml print_slack_parrots.sml
−
  fun reverse(ml : 'a mutable_list) : unit =
 
−
    raise NotYetImplemented
 

Latest revision as of 03:19, 11 October 2022

Background

SML

ref

fun get_value_at_reference(reference : 'a ref) : 'a = 
    !reference

fun set_value_at_reference(reference : 'a ref, next_value : 'a) : 'a = 
    let
        val previous_value = !reference
        val _ = reference := next_value
    in
        previous_value
    end

(* alternate version
fun set_value_at_reference(reference : 'a ref, next_value : 'a) : 'a = 
    let
        val previous_value = !reference
    in
        ( reference := next_value
        ; previous_value )
    end
*)

Code to Implement

types

mutable_list

(* TODO: replace unit with the datatype/type synonym(s) you decide upon *)
type 'a mutable_list = unit

NOTE: type synonyms do NOT support self-reference.

parrot

datatype parrot = PARTY | SHUFFLE | PORTAL_BLUE_LEFT | PORTAL_ORANGE_RIGHT

functions

val construct_empty = fn : unit -> 'a mutable_list
val length = fn : 'a mutable_list -> int
val clear = fn : 'a mutable_list -> unit
val add_to_front = fn : 'a mutable_list * 'a -> unit
val add_to_back = fn : 'a mutable_list * 'a -> unit
val contains = fn : ('a -> bool) * 'a mutable_list -> bool
val nth = fn : 'a mutable_list * int -> 'a
val construct_from_immutable = fn : 'a list -> 'a mutable_list
val foldl = fn : ('a * 'b -> 'b) * 'b * 'a mutable_list -> 'b
val to_immutable = fn : 'a mutable_list -> 'a list
val map = fn : ('a -> 'b) * 'a mutable_list -> 'b mutable_list
val copy = fn : 'a mutable_list -> 'a mutable_list
val @ = fn : 'a mutable_list * 'a mutable_list -> 'a mutable_list
val reverse = fn : 'a mutable_list -> unit

construct_empty

fun construct_empty() : 'a mutable_list = 
   raise Fail "NotYetImplemented"

length

fun length(mlist : 'a mutable_list) : int = 
   raise Fail "NotYetImplemented"

Functionally analogous to List.length, but with O(1) performance.

clear

fun clear(mlist : 'a mutable_list) : unit =
   raise Fail "NotYetImplemented"

add_to_front

fun add_to_front(mlist : 'a mutable_list, value : 'a) : unit =
   raise Fail "NotYetImplemented"

Analogous to ::.

add_to_back

fun add_to_back(mlist : 'a mutable_list, value : 'a) : unit =
   raise Fail "NotYetImplemented"

contains

fun contains(predicate : ('a -> bool), mlist : 'a mutable_list) : bool =
   raise Fail "NotYetImplemented"

nth

fun nth(mlist : 'a mutable_list, index : int) : 'a = 
    raise Fail "NotYetImplemented"

Analogous to List.nth.

Note: raise Subscript if out of bounds.

construct_from_immutable

fun construct_from_immutable(values : 'a list) : 'a mutable_list = 
   raise Fail "NotYetImplemented"

foldl

fun foldl(f : ('a * 'b -> 'b), init : 'b, mlist : 'a mutable_list) : 'b = 
   raise Fail "NotYetImplemented"

Analogous to List.foldl.

to_immutable

fun to_immutable(mlist : 'a mutable_list) : 'a list = 
   raise Fail "NotYetImplemented"

map

fun map(f : ('a -> 'b), mlist : 'a mutable_list) : 'b mutable_list =
   raise Fail "NotYetImplemented"

Analogous to List.map.

copy

fun copy(mlist : 'a mutable_list) : 'a mutable_list =
   raise Fail "NotYetImplemented"

@

fun a @ b = 
   raise Fail "NotYetImplemented"

Analogous to List.@.

Note: does NOT alias.

reverse

fun reverse(mlist : 'a mutable_list) : unit =
   raise Fail "NotYetImplemented"

Analogous to List.rev

remove_arbitrary

fun remove_arbitrary(mlist : 'a mutable_list) : 'a option =
   raise Fail "NotYetImplemented"

pick an arbitrary item in the mutable list and remove it.

return NONE if the mutable list is of length 0 and SOME of the removed item otherwise.

analogous to: nothing I can think of right now.

Testing

source folder: src/test/sml/warmup_mutable_list
how to run with CM.make verbosity off: sml -Ccm.verbose=false run_mutable_list_testing.sml
how to run with CM.make verbosity on: sml run_mutable_list_testing.sml

note: ensure that you have removed all printing to receive credit for any assignment.

SML Error Messages

Parrots

directory: src/main/sml/warmup_parrots/ 

sml print_slack_parrots.sml
Retrieved from "http://classes.engineering.wustl.edu/cse425s/index.php?title=Mutable_List_Assignment&oldid=1824"