CODEWITHSUNDEEP
functional-programmingsmlsmlnj
URL87
URL87

Reputation: 11022

SML/NJ - linked list which can hold any types

I trying to create a datatype for linked list which can hold all types at same time i.e linked list of void* elements , the designing is to create a Node datatype which hold a record contains Value and Next .

What I did so far is - 

datatype 'a anything = dummy of 'a ; (* suppose to hold any type (i.e void*) *)

datatype linkedList = Node of {Value:dummy, Next:linkedList}; (* Node contain this record *)

As you can see the above trying does not works out , but I believe my idea is clear enough , so what changes are required here to make it work ?

Upvotes: 1

Views: 1415

Answers (2)

Ian Zerny
Ian Zerny

Reputation: 346

FYI, if it is important that the types of your polymorphic list remain open, you can use SML's built-in exception type: exn. The exn type is open and can be extended anywhere in the program.

exception INT of int
exception STR of string
val xs = [STR "A", INT 5, INT 6] : exn list

You can case selectively on particular types as usual:

val inc_ints = List.map (fn INT i => INT (i + 1) | other => other)

And you can later extend the type without mention of its previous definition:

exception BOOL of bool
val ys = [STR "A", INT 5, INT 6, BOOL true] : exn list

Notice that you can put the construction of any exception in there (here the div-by-zero exception):

val zs = Div :: ys : exn list

That said, this (ab)use really has very few good use cases and you are generally better off with a closed sum type as explained by Edwin in the answer above.

Upvotes: 3

Edwin Dalorzo
Edwin Dalorzo

Reputation: 78589

I am not sure if you are being forced to use a record type. Because otherwise I think it is simpler to do:

datatype 'a linkedlist = Empty | Cons of 'a * 'a linkedlist

Then you can use it somewhat like:

val jedis = Cons ("Obi-wan", Cons("Luke", Cons("Yoda", Cons("Anakin", Empty))));

I think the use of the record is a poor choice here. I cannot even think how I could represent an empty list with that approach.

-EDIT-

To answer your comment about supporting multiple types:

datatype polymorphic = N of int | S of string | B of bool
Cons(S("A"), Cons(N(5), Cons(N(6), Cons(B(true), Empty))));

Given the circumstances you may prefer SML lists instead:

S("A")::N(5)::N(6)::B(true)::[];

Which produces the list

[S "A",N 5,N 6,B true]

That is, a list of the same type (i.e. polymorphic), but this type is capable of containing different kinds of things through its multiple constructors.

Upvotes: 4

Related Questions