Subtly Different Linked Lists

If you don't know what a linked list is, then you probably shouldn't be reading this. However, the idea is very simple: a linked list is a list constructed from smaller lists of length two. So a list of length 3 would be constructed as (A, B, C) = (A, (B, (C, Nothing))), where Nothing would indicate that we have reached the end of the list. Most programming languages have some kind of linked list datatype. C++ has the list<T> type in STL, Lisp has the 'list type, Haskell has the [T] type, and RDF has the rdf:List type. We will not consider sequences here, so C types will be left for a future article.

Without any type restrictions, such a pair need not be required to make a list. For example, we could make the structure ((A, B), C), but we could not interpret it as a list. This is exactly how the Common Lisp cl:cons constructor works. The Common Lisp HyperSpec calls anything constructed with cl:cons a list. The special case where the second element of cl:cons is either another cl:cons or a cl:nil is called a proper list. This restriction makes a subtype which can always be interpreted as a list. This subtype corresponds to the lists found in scripting languages such as Perl, Python, and Ruby. RDF lists can also be described as proper lists, since an RDFS-interpretation requires that the range of rdf:rest is rdf:List, so any attempt to make an improper list with rdf:rest will result in an inconsistent RDF graph.

With the restriction that the second part of a pair is a list, we obtain so-called heterogeneous lists, because the members of the list (encoded as the first part of each pair) can be of any type. If we also enforce the restriction that each member of the list is of the same type, then we obtain what is called homogeneous lists for obvious reasons. This subtype is what is found in more strict languages, such as list<T> in C++ and [T] in Haskell. This is an overview of the different kinds of lists we have talked about:

• Improper list (a, (b, c))
• Proper list (a, (b, (c, ())))
• Heterogeneous list [1, "message"]
• Homogeneous list [1, 2, 3]

While we have talked about lists before, restricting RDF's heterogeneous lists to obtain homogeneous lists. However, in this article we are going to consider generalizing RDF's proper lists to obtain improper lists as well. In order to do this, we will make a distinction between cl:Cons the Class and cl:cons the constructor. First we need rdf:List rdf:subClassOf cl:Cons so that they can work together, and then cl:Cons will represent both improper lists and proper lists, and rdf:List will represent proper lists only. To represent an improper list, would would have to be an instance of cl:Cons but not rdf:List. For a heterogeneous list, one would have to be missing the ex:listType property, and for a homogeneous list, one would require the presence of the ex:listType property. This covers all the different list types discussed above.