Even with cyclic relationships between types, immutability makes cycles within instances difficult (without laziness anyway). A syntax tree would be a good example.
Yes, either is sufficient, I think.
Yes, and the nice thing about doing it with immutability is you can still have recursive types to build linked lists, trees, and/or dags. From there you can build hash-array-mapped-tries, finger-trees, and so on, giving you friendly dict/list or JSON style data structures.
Couldn't you make lazily evaluated code in erlang too, even if it's not lazy by default like Haskell? You'd just need function pointers, right? Or is that not enough?
Haskell can have circular references because its laziness is implemented with thunks, which have a mutable cell in which to store the computed value so that terms don't get evaluated more than once. Here's a Haskell function that makes a circular linked list:
-- circular linked list with one item
repeat x = let xs = x:xs in xs
function repeat(x) {
function xs() {
return [x, xs]; // [first, rest]
}
return xs;
}
For completeness, here's a JavaScript version that uses thunks:
class Thunk {
constructor(f) { this.f = f; }
get() { if (this.f) { this.v = (this.f)(); delete this.f; } return this.v; }
}
function repeat(x) {
let xs = new Thunk(() => {
return [x, xs]; // [first, rest]
});
return xs;
}
Another solution is to make things immutable (like Erlang), or "as-if" immutable (like Koka), which guarantees that data can only point to things that have already been defined, preventing cycles.* Erlang uses this to simplify generational collection - because old data can't point to young data, it doesn't need a card table or anything like that.
I think it's perfectly possible to have a general purpose language without cycles: you can just use integer indices into an array instead of pointers if you want cyclic data structures. This is common in Rust, when people want to avoid the overhead of reference counting, but don't want to use unsafe code.
* A hidden assumption here is that the language is eagerly evaluated. There are languages like Haskell that have immutability and cyclic data structures.