datatype for list operation

Question

I have this problem to solve

and I have managed to solve it but without that function execute_ops. This is my solution:

datatype list_op = insert of int*int | delete of int | setsize of int;

exception wrong_case;

fun insert(x,pos,nil) = [x]
  | insert(x,pos,h::t) = if (pos=h) then x::h::t else h::insert(x,pos,t);

fun setsize(0) = nil
  | setsize(1) = [0]
  | setsize(n) = 0 :: setsize(n-1);

fun delete (l,0) = l
  | delete (nil,_) = raise wrong_case
  | delete (h::t,n) = if n = h then h::t else delete(t,n-1);

insert(3, 4, delete(setsize(5), 3));

First I am not sure if my solution is correct because I do not understand what setsize is.

How do I write my code the correct way?

Thank you

Answer 1

So for each of the three operations, you seem to have defined helper functions that perform the logic behind the operations. What remains, besides fixing this logic so it works, is piecing those functions together to form the function execute_ops.

1. You must not name your functions insert, delete and setsize if these values are simultaneously the value constructors of your datatype. Simply, once you define the datatype and then the functions in the same scope, the functions will shadow over the value constructors and render you unable to express values of type list_op.

   The important, and I suspect confusing, point is that insert, delete and setsize are not functions that perform the operation on lists. They are value constructors, much like leaf and node are for making a binary tree:

    datatype tree = leaf | node of tree*int*tree
   

2. Comparing pos=h in insert does not make sense. The element in the list are not the same as their positions. You wish to insert x at position pos, not at the first element that is equal to pos. A value is not necessarily equal to its position in the list in which it occurs.

3. And delete is unfortunately completely nonsensical; what your code is saying is "if the number n is equal to the element in the list, then return the entire list. Else, delete the element and continue deleting elements until this is the case, or the list is empty."

   Raising an exception in delete is also not necessary according to the definition.

4. I am not sure what you mean by not understanding what setsize is. It is supposed to be an operation that sets the size of the list. Repeating the assignment text, if size is less than the current length, delete excessive elements, otherwise extend the end of the list with zeroes.

Here is a template for solving the assignment:

datatype list_op = insert of int*int | delete of int | setsize of int

fun insert_h (0, elem, x::xs) = ...   (* insert elem instead of x *)
  | insert_h (pos, elem, []) = ...    (* list was too short *)
  | insert_h (pos, elem, x::xs) = ... (* not there yet *)

fun setsize_h (0, xs) = ...           (* wonder what list has size 0 *)
  | setsize_h (n, []) = ...           (* extend list n times more *)
  | setsize_h (n, x::xs) = ...        (* not there yet *)

fun delete_h (0, x::xs) = ...         (* delete element at this position *)
  | delete_h (n, []) = ...            (* list was too short *)
  | delete_h (n, x::xs) = ...         (* not there yet *)

fun execute_ops [] xs = ...           (* no more operations to execute *)
  | execute_ops (list_op::list_ops) xs =
    let val new_xs = (case list_op of
                          insert (pos, elem) => insert_h (pos, elem, xs)
                        | delete pos         => delete_h (pos, xs)
                        | setsize size       => setsize_h (size, xs))
    in execute_ops list_ops new_xs
    end

You might wish to test these functions, either in isolation or in combination using execute_ops:

val test_insert_h_1 = insert_h (2, 7, [1,2,3,4]) = [1,2,7,4]
val test_insert_h_2 = insert_h (9, 5, [1,2,3,4]) = [1,2,3,4,5]

val test_setsize_h_1 = setsize_h (2, [5,6,7,8]) = [5,6]
val test_setsize_h_2 = setsize_h (5, [1,2,3]) = [1,2,3,0,0]

val test_delete_h_1 = delete_h (3, [4,5,6,7,8]) = [4,5,6,8]
val test_delete_h_2 = delete_h (9, [1,2,3]) = [1,2,3]

val test_execute_ops_1 =
    execute_ops [insert (0, 5), insert (1, 6), insert (2, 7)] [2,3,5] = [5,6,7]

val test_execute_ops_2 =
    execute_ops [setsize 5, insert (4, 9)] [] = [0,0,0,0,9]

val test_execute_ops_3 =
    execute_ops [setsize 6, insert (1, 5), delete 3] [8,8,8,8,9] = [8,5,8,9,0]