undefined | Better HN

0 pointswyager9y ago0 comments

Tail recursion can't use constant space if it's strictly generating another data structure of the same size. That doesn't even make sense.

Interesting fact about foldl'. Regardless, in practice it is strict and tail recursive. As I mentioned earlier, this does not mean the same thing as constant space unless the reduction function returns a fixed size result.

Yes, you can guarantee that a linked list in Java is finite because Java does not support codata.

Haskell's tail call recursion is also often optimized to be allocation-free, unless, again, it is generating some data structure.

0 comments

eru9y ago

> Yes, you can guarantee that a linked list in Java is finite because Java does not support codata.

What about another thread running that keeps generating pieces to the end of the linked list? (No problem, with mutation.)

cousin_it9y ago

To prevent these and similar "what abouts", here's an implementation of a guaranteed finite linked list in Java.

    class LinkedList<T> {
      public final T value;
      public final LinkedList<T> next;
      public LinkedList(T value, LinkedList<T> next) {
        this.value = value;
        this.next = next;
      }
    }

Here's how you construct it:

    LinkedList<String> myList =
      new LinkedList("Hello",
        new LinkedList("World", null));

Here's how you iterate over it in constant space:

    while (myList != null) {
      System.out.println(myList.value);
      myList = myList.next;
    }

j / k navigate · click thread line to collapse