7

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?

  • 4
    In "big" Haskell programs it's common to see [a] used as one would use IEnumerable/Iterator and use more efficient, specialized structures like Vector's for "small list like things" for efficiency purposes which mitigates a lot of the common issues IMHO – jozefg Apr 27 '16 at 7:55
5

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).

3

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.

-1

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.

  • 2
    Even foldr can bite you if you fold using a function that needs both arguments before it can evaluate though, right? foldr (+) 0 [1..] for example. It will hang, but foldr (&&) True (False:[True,True...]) will halt (right?). Do you simply need to be aware which functions are lazy in their second argument? – sara Apr 27 '16 at 9:28
  • 4
    Things like length are fairly easy to call and will evaluate the list fully. – mb14 Apr 27 '16 at 9:51
  • @mb14: I think it's imprecise to talk about "evaluating the list fully" in this context. The problem with a function like length, specifically, is that it gets "stuck" on an infinite list—if you pattern match against length [1..] the program can never figure out which alternative of the pattern match applies, and thus can never make progress. This is different from, say, traverse print [1..], which doesn't terminate but does progress—it will keep on printing consecutive numbers forever, without hanging. – sacundim May 10 '16 at 22:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.