Dealing with (the risks of) infinite sequences in Haskell

Question

I'm a couple of weeks into dabbling with haskell and I've made a pretty big dent in Learn You A Haskell. I feel like many of the type classes and common implementations up to applicatives and monads make a lot of sense to me and I understand how they work, but I still lack a lot of practical experience.

One thing that kind of irks me, coming from a mostly imperative/OOP background is the concept of values/functions that evaluate to infinite lists. I can of course see how they can be used to write some definitions very tersely and they are surely useful in loads of cases I can't even imagine. I wonder what the common approach is to mitigating their risks though. If you at any point in your code accidentally evaluate an infinite list "fully", your program will just get stuck. This is possible to do in imperative languages too of course (certain implementations of the IEnumerable/Iterator interfaces from C#/Java for example), but it's my experience that people rarely do this because it's ... well, dangerous.

One of the big advantages of Haskell is the compile time checks you get. Can we do any compile time checks to deal with this risk? Or do we write tests for it? Or are we simply "never stupid enough to do that, and if we do, we notice it after 1 second when running it in the REPL"? Or are there naming conventions?

I realize this is probably a bit subjective, but surely there are common idioms?

Answer 1

This risk of accidentally producing an infinite list is just the same as accidentally having and endless loop. The only difference is that in lazy settings it might not manifest at all (if you don't evaluate the whole structure), and if it does, it'll be at a different place, which might be harder to debug.

One option is to use forcibly finite data structures like Vector or Seq. If you want to use linked lists, you can define one with a strict spine like

data List a = Nil | Cons a !(List a)

While currently Haskell doesn't do that, there is a concept of Total Functional Programming which allows to ensure by syntactical checks that all computations terminate. In particular, it prevents creating of infinite data structures (data), or alternatively allows them but unwrapping one level always finishes (codata).

Answer 2

I think a good rule of thumb here is: stay away from operations that diverge on infinite structures. That doesn't mean never use them, but rather, defer their use as far as possible in your program.

It takes a bit of experience to learn to recognize these operations, but that comes with time. Some examples are length, sum and foldl'; and one useful fact is that often you can avoid divergence by switching from these to operations based on scanl instead. For example, the function to take the sum of all the numbers in a list will diverge for infinite lists:

sum :: Num a => [a] -> a
sum = foldl' (+) 0

-- `sum [1..]` diverges...

But the function to compute the sums of all the prefixes of a list works fine with infinite lists:

sums :: Num a => [a] -> a
sums = scanl' (+) 0

-- `take 10 (sums [1..])` => `[0,1,3,6,10,15,21,28,36,45]`

But as jozefg points out in a comment, another common way to avoid these issues is just to use data types that only support finite collections. Haskell's lists are extensively used, but so are Map, Set, Vector, ByteString and Text, all of which are guaranteed-finite, and each offers some features or tradeoffs different to what lists do. This gets to your latter question:

One of the big advantages of Haskell is the compile time checks you get. Can we do any compile time checks to deal with this risk?

Yes, you can do this by using some other data type that guarantees finiteness. Don't hesitate to try out any of the ones I mentioned earlier.

Answer 3

In a lazy language, it's much harder to evaluate an infinite list fully, unless you are using functions that are explicitly strict (eg seq or functions that are implemented using it, like foldl'). If you stay away from these, then only inputs that are relevant to calculating your output will actually be generated. So as long as you stick to processing potentially infinite lists with foldr, map and take, you will probably never have an issue.