3 ms·
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 abo
by wyager 10y ago
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.
- eru 10y 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_it 10y agoTo 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; }