(SML) Insert in a trie from reference form to normal?

Question

I created this destructive insertion to tries:

(* ins: char list * (char trie) ref list -> (char trie) ref list *)

 fun ins ([], t) = t@[ref Empty]
 | ins (x::xs, []) = [ref (Node (x, ins (xs, [])))]
 | ins (x::xs, h::tl) =
 case !h of
 Node (c, lis) =>
 if c = x then
 (h := Node (c, ins (xs, lis)); h::tl)
 else
 h::ins (x::xs, tl)
 | Empty => h::ins(x::xs, tl)

And I was trying to make it normal insert without references but I keep getting error.

(* ins: char list * (char trie) list -> (char trie) list *)

fun ins ([], t) = t@Empty
| ins (x::xs, []) = (Node (x, ins (xs, [])))
| ins (x::xs, h::tl) =
case h of
Node (c, lis) =>
if c = x then
(h = Node (c, ins (xs, lis)); h::tl)
else
h::ins (x::xs, tl)
| Empty = h::ins(x::xs, tl)

Answer 1

It would help if you provided the datatype definition that Empty and Node come from and error messages.

This is what I assume the datatype definition is for the first function:

datatype 'a trie = Empty | Node of 'a * 'a trie ref list

For the second:

datatype 'a trie = Empty | Node of 'a * 'a trie list

There are several issues with your second function:

The first clause (ns ([], t) = t@Empty) tries to append t to Empty, where t has type list but Empty has type 'a trie'. You should change that to ns ([], t) = t@[Empty] to match the destructive version, so that it typechecks.

The clauses in case use a "fat arrow" not an equals sign. Replace | Empty = h::ins(x::xs, tl) with this | Empty => h::ins(x::xs, tl).

Finally, this is not valid SML:

if c = x then
(h = Node (c, ins (xs, lis)); h::tl)

The parenthesized expression is a sequence which is only for imperative code. The variable h isn't a reference so you can't assign to it like that. Instead, you should use a let to introduce a local variable.

if c = x then
       (let val h = Node (c, ins (xs, lis)) in  h::tl end)
else

Here's the final function. This compiles but I didn't test it carefully so I don't know if there's another error with it:

fun ins ([], t) = t@[Empty]
  | ins (x::xs, []) = [Node (x, ins (xs, []))]
  | ins (x::xs, h::tl) =
     case h of
        Node (c, lis) =>
            if c = x then
                   (let val h = Node (c, ins (xs, lis)) in  h::tl end)
            else
                h::ins (x::xs, tl)
      | Empty => h::ins(x::xs, tl)

    if c = x then
    (h = Node (c, ins (xs, lis)); h::tl)

    if c = x then
           (let val h = Node (c, ins (xs, lis)) in  h::tl end)
    else