CODEWITHSUNDEEP
smlsmlnj
Rogan Farrira
Rogan Farrira

Reputation: 15

How to solve "unresolved flex record" in else if statement in SML?

I want to find a list of nodes that currently given nodes directly or indirectly connect to. For example, I have a list of nodes:

[1,2]

and a list of tuples, and each of the tuples represents a direct edge:

[(1,5),(2,4),(4,6)]

So, the nodes I am looking for are 

[1,2,5,4,6]

Because, 1 connects to 5, 2 connects to 4. Then, 4 is connected to 6. To achieve this, I need two a queues, and a list. Each time a new node is discovered, we append the new node to the queue and the list. Then, we remove the first node of the queue, and go to next node. If a new node is connected to the current node of the queue. Then, we add new node to both the queue and the list.

We keep doing this until the queue is empty and we return the list.

So now, I have an append function which appends a list to another list:

fun append(xs, ys) = 
   case ys of 
        [] => xs
    | (y::ys') => append(xs @ [y], ys')

Then, I have a function called getIndirectNodes, which intends to return the lists of nodes that the given nodes indirectly connected to, but throws "unresolved flex record". List1 and List2 have the same items supposedly. But, List1 serves the queue, and list2 servers as the list to be returned.

  fun getIndirectNode(listRoleTuples, list1, list2) =
      if list1 = []
          then list2
     else if hd(list1) = #1(hd(listRoleTuples))
        then (
            append(list1,#2(hd(listRoleTuples)) :: []);
            append(list2,#2(hd(listRoleTuples)) :: []);
            getIndirectNode(listRoleTuples,tl(list1),list2)
            )
        else
           getIndirectNode(listRoleTuples,tl(list1),list2)

If I remove the else if statement, it works perfectly fine. But, it's not what I intended to do. The problem is in the else if statement. What can I do to fix it?

Upvotes: 0

Views: 121

Answers (2)

sshine
sshine

Reputation: 16105

It seems that one of your classmates had this exact tuple problem in a very related task.

Make sure you browse the StackOverflow Q&A's before you ask the same question again.

As for getting the indirect nodes, this can be solved by fixed-point iteration.

First you get all the direct nodes, and then you get the direct nodes of the direct nodes.

And you do this recursively until no more new nodes occur this way.

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

fun toSet xs =
    ... sort and remove duplicates ...

fun getReachableNodes (startNodes, edges) =
    let
      fun f startNode = getDirectNodes (startNode, edges)
      val startNodes = toSet startNodes
      val endNodes = toSet (List.concat (List.map f startNodes))
    in
      if startNodes = endNodes
      then endNodes
      else getReachableNodes (startNodes @ endNodes, edges)
    end

This doesn't exactly find indirect end-nodes; it finds all nodes directly or indirectly reachable by startNodes, and it includes startNodes themselves even if they're not directly or indirectly reachable by themselves.

I've tried to make this exercise easier by using sets as a datatype; it would be even neater with an actual, efficient implementation of a set type, e.g. using a balanced binary search tree. It is easier to see if there are no new nodes by adding elements to a set, since if a set already contains an element, it will be equivalent to itself before and after the addition of the element.

And I've tried to use higher-order functions when this makes sense. For example, given a list of things where I want to do the same thing on each element, List.map produces a list of results. But since that thing I want to do, getDirectNodes (startNode, edges) produces a list, then List.map f produces a list of lists. So List.concat collapses that into a single list.

List.concat (List.map f xs)

is a pretty common thing to do.

Upvotes: 0

molbdnilo
molbdnilo

Reputation: 66371

SML needs to know exactly what shape a tuple has in order to deconstruct it.
You could specify the type of the parameter - listRoleTuples : (''a * ''a) list - but using pattern matching is a better idea.

(There are many other problems with that code, but that's the answer to your question.)

Upvotes: 1

Related Questions