Execution part of an infinite list in Haskell?

Question

I'm a little confused about how exactly Haskell execution works on infinite lists. for example, consider below sum function :

sum (takeWhile (<10000) (filter odd (map (^2) [1..])))

here the code for finding Sum of all odd squares that are smaller than 10000 and I know how these takewhile, filter, map functions work. my doubt is, here the map function is taking one element from the infinite list and squaring it and returning the list of squared elements to the filter function right? in that case it would run infinitely for squaring that infinite list of elements isn't it? or is it taking just one element squaring it and then returning to the filter?

Answer 1

Haskell is as lazy as it can possibly be. It doesn't calculate any value that you don't ask it for, and if you do let nums = filter odd (map (^2) [1..]) you haven't forced it to calculate anything yet. For now it knows that nums is of type Num a => [a] (because of the types of the operations you've described) but it doesn't know anything else about it (and that's fine!)

Even when you run takeWhile (<10000) you're not forcing any numbers. Now ghc knows that takeWhile (<10000) nums has type (Ord a, Num a) => [a] (you've introduced the additional typeclass when you compared by (<)) but that's all it knows.

Even once you call sum, ghc doesn't have to do anything. sum expects a Num a => [a] (technically a (Num a, Foldable t) => t a but let's pretend those are the same thing for right now) and you've given it one. Until you actually ask for the result of that operation, ghc doesn't do anything. You can test this by doing let foobar = sum [1..] in your interpreter. As long as you don't ever ask for the result of foobar, Haskell is fine with that expression.

However, if you ever ask for that result, you've forced the whole line to compute. sum needs its list, so it asks takeWhile (<10000) for it. takeWhile needs its list, so it asks filter odd for it. filter needs its list so it asks map (^2) for it, but filter doesn't need the whole list at a time, so map still works as lazily as possible and gives each number one at a time.

Once takeWhile has found a number (>=10000), it doesn't need anymore and happily hands off to sum, which produces your result and ghc goes back to being lazy, not producing any more results of nums unless you need them.

Answer 2

takeWhile (<10000) puts a limit on how many elements to process for the sum. Haskell is lazy-evaluated and will only do as much work as needed. For this reason it's a common pattern to create an infinite list and limit it with a take operation. This means that only elements from a list that are used are generated and processed. Once takeWhiles condition is false, no other elements from the list are used, so they aren't generated.

Answer 3

You can imagine a dialogue between functions.

GHCi asks sum to give a result. sum wakes up and asks takeWhile to give at least one element. Wakes up takeWhile and asks filter to give at least one element. Wakes up filter and asks map to give at least one element. Wakes up map and asks [1..] to give at least one element.

[1..] gives 1. map applies (^2) and gives (1^2). filter checks odd (1^2) and gives 1. takeWhile checks (1 < 10000) and gives 1. sum adds 1 to accumulator and continue asks takeWhile to give at least one element. And so on, until the takeWhile check is successful. Then sum returns the accumulator to GHCi.