Does this function make use of haskell's lazy evaluation

Question

I wrote the following function to decide if a number is prime or not.

isPrime :: Int -> Bool
isPrime n = and (map (\x -> (n `mod` x > 0))[2..(intSquareRoot n)])

intSquareRoot :: Int -> Int
intSquareRoot n = intSq n
  where
    intSq x
      | x*x > n = intSq (x - 1)
      | otherwise = x

I just got started with using Haskell so this piece of code may be hideous to anyone who is trained in using it. However, I am curious if this piece of code makes use of Haskell's lazy evaluation. this part

(map (\x -> (n `mod` x > 0))[2..(intSquareRoot n)])

will create a list of booleans, if just one of these is False (so if a number between 2 and the sqrt of n divides n) then the whole thing is False using the 'and' function. But I think the whole list will be created first and then the 'and' function will be used. Is this true? If so, how can I make this faster by using lazy evaluation, so that the function stops and returns false once it finds the first divisor of n. Thanks in advance for any help!

I'd use a $ instead of parens before map; it's really a nice tool :) — Bartek Banachewicz
Instead of and you can use any: any (\x -> n mod` x > 0) [2..intSquareRoot n]. any` is equivalent to: any f = and . map f . — Bakuriu
@Bakuriu Actually any f = or . map f. You were thinking about all f = and . map f instead. — chi
That intSquareRoot is going to be incredibly slow for any sort of large input. You might want to consider a loop based on the old divide-and-average trick, instead. — Carl

bheklilr bheklilr · Accepted Answer · 2014-09-15T16:48:38

Let's look at the definitions of map and and to understand:

map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs

and :: [Bool] -> Bool
and [] = True
and (x:xs) = x && and xs

We'll also need the definition of &&:

(&&) :: Bool -> Bool -> Bool
True && x = x
_    && _ = False

It is important to note here that && can short-circuit, meaning if you pass it False && undefined, you'll get False immediately. The computation True && undefined will throw an error though, because the second argument has to be examined.

With map, we know it's lazy because : is lazy. We can produce an f x, then later ask for the rest of the list as we need it.

So looking at the line

and (map f [2..intSquareRoot n])
    where f x = n `mod` x > 0

This can be broken down into (n = 19)

and (map f [2..intSquareRoot n])
and (map f [2..4])
and (map f (2:[3..4]))
and (f 2 : map f [3..4])
f 2  && and (map f [3..4])
True && and (map f [3..4])
and (map f [3..4])
and (map f (3:[4..4]))
and (f 3 : map f [4..4])
f 3  && and (map f [4..4])
True && and (map f [4..4])
and (map f [4..4])
and (map f (4:[]))
and (f 4 : map f [])
f 4  && and (map f [])
True && and (map f [])
and (map f [])
and []
True

Hopefully from this expansion you can see how only one element from the list is processed at a time, while the rest of the list can remain uncomputed until its needed. All of these steps were performed simply through substitution directly from the function definitions. As you might be able to see, if instead I passed in n = 27, when f 3 is calculated it'll return False and cause the False && and (map f [4..5]) to just return False without consuming the rest of the list.

Does this function make use of haskell's lazy evaluation

3 Answers