CODEWITHSUNDEEP
haskelllazy-evaluation
Carcigenicate
Carcigenicate

Reputation: 45826

Haskell is evaluating much faster then I thought it would (no complaints)

I wrote the following to check if a number is prime:

factorsOf :: Int -> [Int]
factorsOf n = [factor | factor <- [2..sqrtOfN], n `rem` factor == 0]
    where sqrtOfN = round . sqrt $ fromIntegral $ n+1

isPrime :: Int -> Bool
isPrime n
    | factorsOf n == [] = True
    | otherwise = False

and it works, but I noticed something weird. If I run factorsOf on a large number (say 100000001), it takes a few seconds to calculate all the factors. If I run isPrime on the same number though, it will return almost immediately if it finds a factor. Does Haskell actually keep track of the condition that a function will return to to support (I'm assuming) lazy evaluation? Thats awesome if it's true.

Upvotes: 3

Views: 224

Answers (2)

cdk
cdk

Reputation: 6778

As noted in the comments, isPrime only needs to evaluate the result of factorsOf deeply enough to determine if it is an empty list or not. You could write isPrime more idiomatically like this:

isPrime = null . factorsOf

where null is simply

null (_:_) = False
null _ = True

Note that as soon as null can pattern match on a (:) constructor, it returns a result without evaluating the rest of the list.

This means only the factorsOf only needs to compute the first factor for isPrime to return, whereas factorsOf by itself will compute the entire list.

Upvotes: 5

sestus
sestus

Reputation: 1927

The basic principle of laziness is that nothing is evaluated unless it is really really needed. Really needed in your case means that the first function must return so that the other function gets its input. You can read more about Haskell's Laziness here

Upvotes: 1

Related Questions