[cousin_it]

The point of tail recursion is using constant space, not constant stack space (does Haskell even have a stack?) Anyways, the Haskell spec allows foldl' to use linear space just like its lazier counterparts. The fact that it uses constant space is an implementation detail of GHC. Reference: https://github.com/quchen/articles/blob/master/fbut.md#seq-d...

Structural recursion always terminates in SML. Supporting infinite/cyclic values in algebraic data types is a misfeature, and they are trivial to rule out without using a totality checker. Heck, I can implement a guaranteed finite linked list in Java :-)

I think something like MLKit would be a more promising start for implementing a safety critical system. Tail and structural recursion actually work there, and it statically replaces most uses of GC with region inference. Though it's still a very long shot, I'd prefer something more proven.

[wyager]

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]

> 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]

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;
    }

[kazinator]

The point of tail recursion is using constant space for the environment and control flow meta info, not constant space absolutely.

[tome]

> does Haskell even have a stack?

Yes

[wyager]

While this is true, the contents of the STG stack aren't necessarily obviously related to the conceptual "call stack", right?

[tome]

Well it's case that pushes onto the stack rather than (syntactic) function call but if you're willing to be generous with what you consider "call" then, yes, they're related.