9

In Haskell, it is possible to define infinite lists like so:

[1.. ]

If found many articles which describe how to implement infinite lists and I understood how this works. However, I cant think of any reason to use the concept of infinite datastructures.

Can someone give me an example of a problem, which can be solved easier (or maybe only) with an infinite list in Haskell?

Jon Purdy
  • 53,300
  • 8
  • 96
  • 166
Moritz Schmidt
  • 2,635
  • 3
  • 27
  • 51
  • 7
    I’m sure there are many good answers, but just to get you started, infinite data structures allow often for simpler definitions. Consider `enumerate`, which puts each element of a list into a tuple with its index. This can be defined recursively with a helper function that takes an index, or more simply as `zipWith [0..]`. Due to the nature of zips, writing `[0..]` is much easier and more general than `[0.. length list - 1]`. – cole Jun 12 '20 at 17:47
  • 6
    It just means you don't have to pass a stop condition through the data-generating functions but can apply it in the end. A classic example is `take 50 fibonacci` where `fibonacci` is defined in terms of itself. – Bergi Jun 12 '20 at 17:48
  • First, lets elide the distinction between "things that are mathematically infinite" like the integers and "things that are effectively infinite as far as my program is concerned" like a stream of user-generated I/O events. It's not too hard to see the advantage of a generic interface for manipulating both. You may not encounter the first too much but the latter is quite common. – Jared Smith Jun 12 '20 at 18:15
  • Infinite data structures are not used that much frequently, in my experience. Sometimes they are convenient, though. E.g., if we are writing a language interpreter, ``head [var | var <- infiniteListOfVarNames , not (var `freeIn` expression)]`` is a short code to generate a fresh name, which does not occur free in `expression`. It is not efficient, but simple to write and understand. There are similar cases where one needs to find the "first" value among infinitely many ones satisfying a certain condition, and filtering an infinite list is very natural. Infinite trees are not as useful, IMO. – chi Jun 12 '20 at 18:16
  • See also [Non-Trivial Lazy Evaluation](https://stackoverflow.com/q/7868507/791604). – Daniel Wagner Jun 12 '20 at 20:01
  • 1
    @cole I was going to give the `zip [0..]` example too, but frankly it's a bit shallow seeing as not only e.g. Python's `enumerate` does that job just as well, it's even done in Haskell: when working with `Data.Vector`, you'd use `indexed` instead of a zip. – leftaroundabout Jun 12 '20 at 23:48

2 Answers2

10

The basic advantage of lists in Haskell is that they’re a control structure that looks like a data structure. You can write code that operates incrementally on streams of data, but it looks like simple operations on lists. This is in contrast to other languages that require the use of an explicitly incremental structure, like iterators (Python’s itertools), coroutines (C# IEnumerable), or ranges (D).

For example, a sort function can be written in such a way that it sorts as few elements as possible before it starts to produce results. While sorting the entire list takes O(n log n) / linearithmic time in the length of the list, minimum xs = head (sort xs) only takes O(n) / linear time, because head will only examine the first constructor of the list, like x : _, and leave the tail as an unevaluated thunk that represents the remainder of the sorting operation.

This means that performance is compositional: for example, if you have a long chain of operations on a stream of data, like sum . map (* 2) . filter (< 5), it looks like it would first filter all the elements, then map a function over them, then take the sum, producing a full intermediate list at every step. But what happens is that each element is only processed one at a time: given [1, 2, 6], this basically proceeds as follows, with all the steps happening incrementally:

  • total = 0
  • 1 < 5 is true
  • 1 * 2 == 2
  • total = 0 + 2 = 2
  • 2 < 5 is true
  • 2 * 2 == 4
  • total = 2 + 4 = 6
  • 6 < 5 is false
  • result = 6

This is exactly how you would write a fast loop in an imperative language (pseudocode):

total = 0;
for x in xs {
  if (x < 5) {
    total = total + x * 2;
  }
}

This means that performance is compositional: because of laziness, this code has constant memory usage during the processing of the list. And there is nothing special inside map or filter that makes this happen: they can be entirely independent.

For another example, and in the standard library computes the logical AND of a list, e.g. and [a, b, c] == a && b && c, and it’s implemented simply as a fold: and = foldr (&&) True. The moment it reaches a False element in the input, it stops evaluation, simply because && is lazy in its right argument. Laziness gives you composition!

For a great paper on all this, read the famous Why Functional Programming Matters by John Hughes, which goes over the advantages of lazy functional programming (in Miranda, a forebear of Haskell) far better than I could.

Jon Purdy
  • 53,300
  • 8
  • 96
  • 166
  • Regarding your definition of `minimum`, doesn't that rely on an implementation of `sort` that guarantees the smallest element will be identified in linear time (e.g., insertion sort)? – chepner Jun 12 '20 at 18:24
  • @chepner: It does—I tried to make mention of the fact that `sort` *is* written to be a good producer for lazy consumers; that is, lazy functions automatically compose well, but not all functions are automatically sufficiently lazy. – Jon Purdy Jun 12 '20 at 18:32
  • I don't think that `sort` provides that guarantee. It's certainly optimized for partially sorted lists, but I think it still takes O(n lg n) time for a list like `[5, 6, 4, 7, 3, 8, 2, 9, 1]`. – chepner Jun 12 '20 at 18:49
  • 1
    @chepner I thought the standard `sort` is a kind of merge-sort, which due to laziness behaves more like heap-sort. If so, it should guarantee O(n) time for generating the first element. – chi Jun 12 '20 at 18:56
  • If I understand correctly, there's an O(n)-time pass to break the list into already-sorted subsequences, followed by O(k) merges to merge all the sublists back into a single list, with the final step being to return the resulting singleton item. That is, `[5, 6, 4, 7, 3, 8, 2, 9, 1] -> [[5, 6], [4, 7], [3, 8], [2, 9], [1]] -> [[4,5,6,7],[2,3,8,9],[1]] -> [[2,3,4,5,6,7,8,9],[1]] -> [[1,2,3,4,5,6,7,8,9]] -> [1,2,3,4,5,6,7,8,9]`. You can't extract the head until you've gone through all the merge steps in the middle. – chepner Jun 12 '20 at 19:13
  • The (simplified) definition is something like `sort = mergeAll . sequences`, with `mergeAll xs = mergeAll (mergePairs xs)`. (https://hackage.haskell.org/package/base-4.14.0.0/docs/src/Data.OldList.html#sort) – chepner Jun 12 '20 at 19:15
  • I think you can only start returning items early if you use selection sort (or a variant thereof), but using that in the definition of `minimum` is cheating a little since selection sort works by first looking for the minimum item in the list. – chepner Jun 12 '20 at 19:30
  • @chepner: I’m not sure I grok it fully, but it looks like it depends on the content of the list how long the initial segment is that must be forced before returning a result, but on average it will be less than the length of the list. So still O(n log n), just smaller by some constant factor. Maybe a bad example then… – Jon Purdy Jun 12 '20 at 19:33
  • 3
    @chepner You can extract the head before you've gone through all the merge steps in the middle, because you actually only need the head of each merge. So you get, roughly: n comparisons to split into sequences; n/2 comparisons to get the heads of first level of merge; n/4 comparisons to get the heads of second level; n/8 comparisons for next level; etc. This is n+n/2+n/4+n/8+... = 2*n ∈ O(n) total comparisons to get the head of the top level list. – Daniel Wagner Jun 12 '20 at 19:58
  • @DanielWagner OK, yeah, that's the part I (repeatedly and constantly) miss. – chepner Jun 12 '20 at 20:02
  • 1
    This is a great answer about laziness, but it doesn't seem to mention any infinite data structures at all. – luqui Jun 13 '20 at 03:03
3

  • Annotating a list with its indices temporarily uses an infinite list of indices: 

    zip [0..] ['a','b','c','d'] = [(0,'a'), (1,'b'), (2,'c'), (3,'d')]

  • Memoizing functions while maintaining purity (in this case this transformation causes an exponential speed increase, because the memo table is used recursively):

    fib = (memo !!)
    where
    memo = map fib' [0..]  -- cache of *all* fibonacci numbers (evaluated on demand) 
    fib' 0 = 0
    fib' 1 = 1
    fib' n = fib (n-1) + fib (n-2)

  • Purely mocking programs with side-effects (free monads)

    data IO a = Return a
          | GetChar (Char -> IO a)
          | PutChar Char (IO a)

    Potentially non-terminating programs are represented with infinite IO strucutres; e.g. forever (putChar 'y') = PutChar 'y' (PutChar 'y' (PutChar 'y' ...))

  • Tries: if you define a type approximately like the following:

    data Trie a = Trie a (Trie a) (Trie a)

    it can represent an infinite collection of as indexed by the naturals. Note that there is no base case for the recursion, so every Trie is infinite. But the element at index n can be accessed in log(n) time. Which means you can do something like this (using some functions in the inttrie library):

    findIndices :: [Integer] -> Trie [Integer]
findIndices = foldr (\(i,x) -> modify x (i:)) (pure []) . zip [0..]

    this builds an efficient "reverse lookup table" which given any value in the list can tell you at which indices it occurs, and it both caches results and streams information as soon as it's available:

    -- N.B. findIndices [0, 0,1, 0,1,2, 0,1,2,3, 0,1,2,3,4...]
> table = findIndices (concat [ [0..n] | n <- [0..] ])
> table `apply` 0
[0,1,3,6,10,15,21,28,36,45,55,66,78,91,...

    all from a one-line infinite fold.

I'm sure there are more examples, there are so many cool things you can do.

luqui
  • 59,485
  • 12
  • 145
  • 204