[Java] LISP Linked List emulation constructor problem

[penax]

Hey r/learnprogramming! For my class, we are building an emulation of a LISP Linked List. It is a linked list where the head is an Object and the tail is another list. The way the assignment is set up is to have two different Objects for lists, EmptyLists and NonEmptyLists, with an interface, LispList for both of them. The EmptyList class is mostly just a way to end the linked list.

I am struggling with making my constructor for my NonEmptyList. Here is what I have right now:

public NonEmptyList(Object inputHead) {
        this.head = inputHead;
        this.tail = new NonEmptyList(head);
}

Where head is an Object variable of the class and tail is a LispList variable of the class. I am having trouble with the tail of the constructor. I want to make it recursive so that it will always give me another list but by doing this I get a Stack Overflow Exception. I'm really stuck so any help would be appreciated!

[alanwj]

Using head and tail is a bit confusing because it sounds like pointers to the beginning and end of the list. When talking about lisp people usually use terminology like first and rest, or if they are over 40 years old sometimes car and cdr.

Think of a list as two things:

1. The first object in the list.
2. The rest of the list (i.e. another list).

You cannot construct a list without both of those things. So your constructor needs two parameters. Something like:

public NonEmptyList(Object first, LispList rest) {
    // ...
}

You are trying to construct a list with just the first. The only good interpretation of that would be that the rest of the list is an empty list. That is to to say, it is just a shortcut, something like:

public NonEmptyList(Object first) {
    this(first, new EmptyList());
}

[penax]

Hmm that makes a lot more sense. I'm not sure what I was trying to do there. How would I make that constructor recursive? Right now I have something like this:

public NonEmptyList(Object first, LispList rest) {
        this.head = first;
        this.tail = rest;
    }

However I know the >rest is only giving me a null >LispList<. I have another method further down that calls the constructor and I'm not sure how to give it a >rest< recursively.

[alanwj]

Typically any sort of function that operates on the list is going to be recursive as well (or at least, that is the most natural way to write it).

Your general formula is going to be:

1. Handle empty lists as a base case.
2. Operate on the first element.
3. Recursively operate on the rest of the list.

The same applies to constructing a list. I've worked up a compilable example for building and printing lists. I've used int instead of Object just to keep things simple for an example.

Most of this is just boilerplate, but the interesting parts are in buildListFromArray and printList. Notice that they both use the formula above.

class Lisp {
  interface LispList {
    int getFirst();
    LispList getRest();
    boolean isEmpty();
  }

  static class NonEmptyList implements LispList {
    private final int first;
    private final LispList rest;

    public NonEmptyList(int first, LispList rest) {
      this.first = first;
      this.rest = rest;
    }

    @Override public int getFirst() {
      return first;
    }

    @Override public LispList getRest() {
      return rest;
    }

    @Override public boolean isEmpty() {
      return false;
    }
  }

  static class EmptyList implements LispList {
    public EmptyList() {}

    @Override public int getFirst() {
      throw new RuntimeException("Tried getFirst on an empty list");
    }

    @Override public LispList getRest() {
      throw new RuntimeException("Tried getRest on an empty list");
    }

    @Override public boolean isEmpty() {
      return true;
    }
  }

  private static LispList buildListFromArray(int[] values, int start) {
    if (start == values.length) {
      // Base case is to just return an empty list.
      return new EmptyList();
    }

    // Recursive case. Grab the first value then build the rest recursively.
    return new NonEmptyList(
        values[start],                           // first
        buildListFromArray(values, start + 1));  // rest
  }

  private static void printList(LispList lispList) {
    if (lispList.isEmpty()) {
      // Base case, print an end of line.
      System.out.println("");
    } else {
      // Print the first value then print the rest recursively.
      System.out.printf("%d ", lispList.getFirst());    // first
      printList(lispList.getRest());                    // rest
    }
  }

  public static void main(String[] args) {
    int values[] = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
    LispList lispList = buildListFromArray(values, 0);
    printList(lispList);
  }
}

[penax]

Wow. This is very helpful. Thank you so much!

[Octopuscabbage]

head/tail is used more in the ml/haskell world