Operating on infinite lists | Hacker News Reader

Operating on infinite lists

notes.jordanscales.com

33 pointsazhenley8 comments

Very much inspired by lazy functional programming :)

Because of the inherent laziness in the language, Haskell's list type works like this. Except better: if you walk over a list, examining its values, you have to call those functions; but Haskell then stores (memoises) those results, so that the second time you walk over the list, the functions don't need to be called again since that initial part is already evaluated. This is what functional programming people refer to when they say call-by-need.

This is particularly helpful if the computation to produce the list is expensive. For example, (weird example, sorry) a list of every 1000th prime number. That gets moderately more expensive as you look at bigger and bigger numbers, so it would be good not to do that many times if you can help it.

summoning a lisp from the aether never gets old

I would have just used a generator function or a recursive objective. You're allowed to define objects with more than 1 statement.

Very nice approach...

So it's a stream, not a list, because those have a length.

An infinite list has a length, it just happens to be (countable) infinite.

Of course, as JS doesn't do (guaranteed) tail call optimisation, even finite lists will have "no length" ;)

(and first rewriting `length` to be tail recursive (or using a loop with mutation):

    function length(l) {
      function go(l, acc) {
        if (l == null) {
          return acc;
        } else {
          return go(l.rest, acc + 1);
        }
      }
      return go(l, 0);
    }

What length does a cyclical list have?

  (define l '(1 2 3))
  (set-cdr! (cddr l) l)

ℵ₀

Reply on news.ycombinator.com