Is it possible to design a type-safe linked list p

问题:

I'm wondering if it is possible to design, for example, a type-safe singly linked list structure such that it is impossible to ask for the next node from the tail node.

At the same time, the client would need to be able to traverse (recursively or otherwise) through the list via node.getChild() but be prevented at compile time (at least with human-written explicit type checking) from going past the tail.

I'm wondering:

1. Is there a name for this type of problem?
2. Is there an object oriented or other approach that would help to avoid explicit run-time type checking?

The implementation language isn't important, but here's a Java example of what I'm thinking of.

Edit after Joop's answer:

public class TestHiddenInterfaces {
   interface Node { HasNoChildNode getTail(); }
   interface HasNoChildNode extends Node {};
   interface HasChildNode extends Node { Node getChild(); }
   class HasNoChild implements HasNoChildNode {
      @Override public HasNoChildNode getTail() { return this; }
   }
   class HasChild implements HasChildNode {
      final Node child;
      @Override
      public Node getChild() { return child; }
      HasChild(Node child) {
         this.child = child;
      }
      @Override public HasNoChildNode getTail() {
         if(child instanceof HasChild) return ((HasChild) child).getTail();
         else if(child instanceof HasNoChild) return (HasNoChildNode) child;
         else throw new RuntimeException("Unknown type");
      }
   }

   @Test
   public void test() {
      HasNoChild tail = new HasNoChild();
      assertEquals(tail, tail.getTail());
      HasChild level1 = new HasChild(tail);
      assertEquals(tail, level1.getTail());
      HasChild level2 = new HasChild(level1);
      assertEquals(tail, level2.getTail());
   }
}

回答1:

In Scala one uses "case types" for such typing. In Java, or UML diagrams, one often sees that a distinction is made between branch and leaf. And that can reduce half the memory of unused leaf children.

The types coexist like enum values.

So one might use the following:

/**
 * Base of all nodes. For the remaining types I have dropped the type parameter T.
 */
public interface Node<T> {
    void setValue(T value);
    T getValue();
}

public interface HasParent extends Node {
    void setParent(HasChildren node);
    HasChildren getParent();
}

public interface HasChildren extends Node {
    void setChildren(HasParent... children);
    HasPOarent[] getChildren();
}

public final class RootBranch implements HasChildren {
    ...
}

public final class SubBranch implements HasChildren, HasParent {
    ...
}

public final class Leaf implements HasParent {
    ...
}

public final class RootLeaf implements Node {
    ...
}

The usage would either use overloading, or distinguishing cases:

void f(Node node) {
    if (node instanceof HasParent) {
         HasParent nodeHavingParent = (HasParent) node;
         ...
    }
}

Personally I think this is overdone in Java, but in Scala for instance, where the type declaration is the constructor, this would make sense: SubBranche(parent, child1, child2).

回答2:

The only way that such a hierarchy could exist is if each level implemented a different interface (where I'm using interface in a wider sense than a specific language term).

The root node cannot implement getParent - that's the only way you'll achieve a compilation error that I can think of. So, the "interface" of the root node doesn't include getParent.

The first children can implement getParent - but in order to be compile safe, they have to return a type that is, at compile time, known to be the root node (i.e. a type that doesn't implement getParent).

At the next level, the implementation of getParent must return a type that implements a getParent that returns a root node that doesn't have getParent.

In short, even if you did choose to produce such an implementation, it would be very brittle, because you'd need to write different code to deal with each level of the hierarchy.

---

There are certain problems where a runtime check is right, and this would be one of those times. If every problem could be solved at compile time, then every compiled program would just be a set of results (and possibly a massive switch statement to pick which result you want to output)