What is error of unresolved flex record in SML?

Question

I am new to SML, and have asked people about the error that I got. But, I can't find where the problem is.

The error message is received is:

stdIn:10.1-16.48 Error: unresolved flex record (need to know the names       
of ALL  the fields in this context)
type: {1:''Y, 2:''X; ''Z}

I have two functions. The first function is reverse, which is to reverse a list and return it. For example, reversing [1,2,3,4] to [4,3,2,1]. This function has absolutely no problems.

fun reverse(L) =
   if L = nil then nil
   else reverse(tl(L)) @ [hd(L)];

The next function is getDirectNode, which takes 3 parameters, starting node, list of tuples containing edges, and an empty list. For example, I have a node, 1, for the first argument. I have a list of tuples containing all edges. [(1,2),(1,3),(2,3),(2,4)], for the second argument. Lastly, the third argument will be an empty list.

In the getDirectNodes function, it will find the tuples that has 1 as its first number. In this case, it will get (1,2) and (1,3). Then, it will put 2 and 3 into the empty list and return it. So, the function will return the [2,3].

Here is my function:

  fun getDirectNodes(startNode,Tuples,list) =
     if Tuples = [] 
        then list
     else if #1(hd(Tuples)) = startNode
        then getDirectNodes(startNode,tl(Tuples),reverse(#2(hd(Tuples)) :: list))
     else
        getDirectNodes(startNode, tl(Tuples),list)

What can be possibly causing the error?

Simon Shine Simon Shine · Accepted Answer · 2019-02-28T08:34:07

The error you get is caused by the SML compiler not being able to infer what type of tuple you have. #1 and #2 are not functions but macros that work on tuples of arbitrary type, as long as they have two elements. So a quick way to overcome this problem is to add type annotation,

fun getDirectNodes(startNode, Tuples : (int * int) list, list) = ...

But since you posted so much of your solution, I'd like to give some general feedback on it:

reverse

Your implementation of reverse does a few things wrong:

When you write if L = [] ..., you force L to be an equality type, ''a. This may seem odd, since you're just testing that L is empty, but before L = [] can be a valid expression, its elements must also be comparable for equality. You can solve this via pattern matching or by using the function List.null (which uses pattern matching) to avoid the equality type restriction.
It uses hd and tl instead of pattern matching; these functions are partial, which means they can crash at run-time when not used properly. You can avoid them by using pattern matching on the empty and the non-empty list.

It uses @ recursively which is very inefficient: Your algorithm is O(n²) because the left-hand side of @ takes linear time to resolve for each recursive call, i.e. geometric complexity:

   reverse [1,2,3,4]
~> reverse [2,3,4] @ [1]
~> reverse [3,4] @ [2] @ [1]
~> reverse [4] @ [3] @ [2] @ [1]
~> reverse [] @ [4] @ [3] @ [2] @ [1]

At this point reverse has used O(n) stack space.

~> [] @ [4] @ [3] @ [2] @ [1]
~> [4] @ [3] @ [2] @ [1]       (* 1 recursive call in @ *)
~> [4,3] @ [2] @ [1]           (* 2 recursive calls in @ *)
~> [4,3,2] @ [1]               (* 3 recursive calls in @ *)
~> [4,3,2,1]                   (* 4 recursive calls in @ *)

And at this point reverse has used O(n + (n-1) + ... + 1) = O(n²) recursive calls.

There's actually a built-in function called rev.

It is implemented like this:

fun rev xs =
  let fun rev_helper []      xs_bw = xs_bw
        | rev_helper (x::xs) xs_bw = rev_helper xs (x::xs_bw)
  in rev_helper xs [] end

and calling it looks like:

   rev [1,2,3,4]
~> rev_helper [1,2,3,4] []
~> rev_helper [2,3,4] [1]   (* 1 recursive call *)
~> rev_helper [3,4] [2,1]   (* 1 recursive call *)
~> rev_helper [4] [3,2,1]   (* 1 recursive call *)
~> rev_helper [] [4,3,2,1]  (* 1 recursive call *)
~> [4,3,2,1]

which uses heap memory instead of stack memory, and O(n) recursive calls.

getDirectNodes

Here is a non-exhaustive list of comments:

The same thing wrt. equality types applies here wrt. Tuples = [].
Having list as an accumulated result is neat! I might have called it something more descriptive, just as I would call Tuples something like edges to describe its content rather than its type.
While using an accumulated result like list is neat, it means that your function takes as input an empty list. What if the caller feeds it a non-empty list? Exposing this extra argument leaves room for errors, so hide it in an inner function, like I did with rev_helper.
Use pattern matching instead of hd and tl.
Your use of reverse seems meaningful: You've experienced that list ends up in reverse. But instead of calling reverse on list on every recursive call, do it once at the very end (when Tuples is empty).

Given this advice, here is a variation of your code:

fun getDirectNodes (startNode, []) = []
  | getDirectNodes (startNode, (x, endNode) :: edges) =
    if x = startNode
    then endNode :: getDirectNodes (startNode, edges)
    else getDirectNodes (startNode, edges)

And a variation that uses an inner tail-recursive function and a single rev at the end:

fun getDirectNodes (startNode, edges) =
    let fun helper ([], endNodes) = endNodes
          | helper ((x, endNode) :: edges, endNodes) =
            if x = startNode
            then helper (edges, endNode :: endNodes)
            else helper (edges, endNodes)
    in rev (helper (edges, [])) end

Here is how I would make it using higher-order functions:

fun getDirectNodes (startNode, edges) =
    List.map #2 (List.filter (fn (x, _) => x = startNode) edges)

The reason I don't get a warning wrt. my use of #2 here, in spite of not having any type annotations, is because I'm pattern matching on the elements of edges in the code fn (x, _) => .... This constrains edges to a list of 2-tuples.

Running this:

- getDirectNodes (1, [(1,2),(1,3),(2,3),(2,4)]);
> val it = [2, 3] : int list

What is error of unresolved flex record in SML?

1 Answers

reverse

getDirectNodes