Can lists in Nix be infinite?

[jameshfisher]

The following expression is supposed to define the infinite list of natural numbers and evaluate to the element of that list at index 3, which should be the number 3.

let
  natsFrom = n: [n] ++ natsFrom (n + 1);
  nats = natsFrom 0;
in
  builtins.elemAt nats 3

Instead I get a segmentation fault:

> nix-instantiate --eval foo.nix
[1]    78348 segmentation fault  nix-instantiate --eval foo.nix

I am assuming here that Nix lists are basically just syntactic sugar over sets; i.e. they are implemented under the hood something like this:

let
  natsFrom = n: { hd = n; tl = natsFrom (n + 1); };
  nats = natsFrom 0;
  elemAt = l: i: if i == 0 then l.hd
                           else elemAt l.tl (i - 1);
in
  elemAt nats 3

Is this not the case? Is the segmentation fault a bug? I didn't find the manual very clear on how exactly lists are meant to behave in this situation.

[shlevy]

nix lists are not actually cons/nil linked lists under the hood, but arrays. They are strict in their length and lazy in their values. This is expected behavior.

[jameshfisher]

Ah, okay, that makes sense. As a suggestion: could we mention this in the manual? I would also suggest renaming "lists" in the manual to "arrays"; I think that captures the distinction.

[jameshfisher]

(I'd be happy to help out editing the manual, if you suggest what changes are appropriate and where.)

[infinisil]

Coming back to this, I'm doing some work on lazy attribute names in #4090. Once that is implemented, it will be very easy to also add support for lazy list indexing, allowing you to have infinite lists. In particular @jameshfisher's first example could work with this.