• Choose a category
• All
• Classic-Fiction

and' :: [Bool] -> Bool

and' xs = foldr (&&) True xs

Knowing how foldr works, we see that the expression and' [True,False,True] will be evaluated like this:

True && (False && (True && True))

The last True represents our starting accumulator, whereas the first three Bool values are from the list [True,False,True]. If we try to evaluate the previous expression, we will get False.

Now what if we try this with an infinite list, say repeat False, which has an infinite number of elements, all of which are False? If we write that out, we get something like this:

False && (False && (False && (False ...

Haskell is lazy, so it will compute only what it really must. And the && function works in such a way that if its first parameter is False, it disregards its second parameter, because the && function returns True only if both of its parameters are True:

(&&) :: Bool -> Bool -> Bool

True && x = x False && _ = False

In the case of the endless list of False values, the second pattern matches, and False is returned without Haskell needing to evaluate the rest of the infinite list:

ghci> and' (repeat False)

False

foldr will work on infinite lists when the binary function that we’re passing to it doesn’t always need to evaluate its second parameter to give us some sort of answer. For instance, && doesn’t care what its second parameter is if its first parameter is False.

Scans

The scanl and scanr functions are like foldl and foldr, except they report all the intermediate accumulator states in the form of a list. The scanl1 and scanr1 functions are analogous to foldl1 and foldr1. Here are some examples of these functions in action:

ghci> scanl (+) 0 [3,5,2,1]

[0,3,8,10,11]

ghci> scanr (+) 0 [3,5,2,1]

[11,8,3,1,0]

ghci> scanl1 (\acc x -> if x > acc then x else acc) [3,4,5,3,7,9,2,1]

[3,4,5,5,7,9,9,9]

ghci> scanl (flip (:)) [] [3,2,1]

[[],[3],[2,3],[1,2,3]]

When using a scanl, the final result will be in the last element of the resulting list. scanr will place the result in the head of the list.

Scans are used to monitor the progress of a function that can be implemented as a fold. As an exercise in using scans, let’s try answering this question: How many elements does it take for the sum of the square roots of all natural numbers to exceed 1,000?

To get the square roots of all natural numbers, we just call map sqrt [1..]. To get the sum, we could use a fold. However, because we’re interested in how the sum progresses, we’ll use a scan instead. Once we’ve done the scan, we can check how many sums are under 1,000.

sqrtSums :: Int

sqrtSums = length (takeWhile (<1000) (scanl1 (+) (map sqrt [1..]))) + 1

We use takeWhile here instead of filter because filter wouldn’t cut off the resulting list once a number that’s equal to or over 1,000 is found; it would keep searching. Even though we know the list is ascending, filter doesn’t, so we use takeWhile to cut off the scan list at the first occurrence of a sum greater than 1,000.

The first sum in the scan list will be 1. The second will be 1 plus the square root of 2. The third will be that plus the square root of 3. If there are x sums under 1,000, then it takes x+1 elements for the sum to exceed 1,000:

ghci> sqrtSums

131

ghci> sum (map sqrt [1..131])

1005.0942035344083

ghci> sum (map sqrt [1..130])

993.6486803921487

And behold, our answer is correct! If we sum the first 130 square roots, the result is just below 1,000, but if we add another one to that, we go over our threshold.

Function Application with $

Now we’ll look at the $ function, also called the function application operator. First, let’s see how it’s defined:

($) :: (a -> b) -> a -> b

f $ x = f x

What the heck? What is this useless function? It’s just function application! Well, that’s almost true, but not quite. Whereas normal function application (putting a space between two things) has a really high precedence, the $ function has the lowest precedence. Function application with a space is left-associative (so f a b c is the