Type with reference to itself - SML

Question

I am new to SML and this style of programming, and I am having some issues. I have an assignment to do in ML, but I'm having some problems modeling the data. I solved the same problem in C, but I'm having problems doing so in SML/NJ. Here is what I want.

I have a struct in C which is like the following:

struct myStr {
    int someData;
    myOtherStruct someOtherData;
    struct myStr * next;
    struct myStr * prev;
}

The basic problem is that I sorted an array of pointers to struct myStr (or struct myStr, it does not matter) based on someOtherData, then I updated some values to the next struct myStr and reordered the next struct myStr into the array so it is sorted and then I looped until the end.

I get pretty good complexity on this with C because sorting takes O(nlogn) and reordering takes: O(1) to find the next myStr and O(logn) to reorder this specific element to the array.

I am having problems modeling this into SML.

First of all, I started doing this with lists, but I need to change a value each time. So I started thinking of refs and arrays (I know its not the best thing).

I thought of the following in ML, using types:

type myStr = { 
    someData : int, 
    someOtherData : myOtherType,
    next : myStr ref, 
    prev :  myStr ref
}

But that does not work in ML, thus producing the following error:

stdIn:1.56-1.61 Error: unbound type constructor: myStr                                      
stdIn:1.38-1.43 Error: unbound type constructor: myStr

The basic problem is that I want to access the next element (which is not the next element in array) quickly (like in C). The idea above with the type does not work in SML.

What should I do for the above type to work, or is there any other idea modeling my data properly so I can get what I want?

Thank you.

Can you explain what you mean when you say "does not work"? Do you get an error message? If so, which one? — sepp2k
Added the error above after the type definition in ml. Here it is stdIn:1.56-1.61 Error: unbound type constructor: myStr stdIn:1.38-1.43 Error: unbound type constructor: myStr. But i strongly believe that even if there is a way to define this type its not the best way to do it in this style of programming. — tchar

sepp2k sepp2k · Accepted Answer · 2014-06-09T16:09:05

Apparently type aliases (which you define using the type keyword) can't be recursive in SML. To define a recursive type you'll need to define an algebraic data type using the datatype keyword. That way your code could be made to compile like this:

datatype myStr = MyStr of
  { 
    someData : int, 
    someOtherData : myOtherType,
    next : myStr ref, 
    prev :  myStr ref
  }

That said this definition is still very problematic. Specifically it does not allow for finite (i.e. non-circular list). Also you won't be able to define any non-recursive values of this type (though if you only intend to represent circular lists, it's only natural that the values would need to be recursive).

I assume your C version of this code represents non-circular lists by letting the last node's next pointer (and the first node's prev pointer) be null. The problem with that is that refs in ML can't be null, so you can't use the same system in ML. So if you need non-circular lists, you'll need to add an explicit Empty value that you can use instead of null:

datatype myStr = MyStr of
  { 
    someData : int, 
    someOtherData : myOtherType,
    next : myStr ref, 
    prev :  myStr ref
  }
  | Empty

PS: You said that this is an assignment, but you didn't really say what exactly the assignment is asking you to do. If the assignment is for SML and it is not specifically asking you to use refs/mutation, I'd assume that you're supposed to solve your problem without mutation, so you'd need to think of a different approach.

Type with reference to itself - SML

1 Answers