这个函数是否使用了haskell的惰性评估

Question

我编写了以下函数来判断数字是否为素数.

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

我刚刚开始使用Haskell,所以这段代码可能对任何受过使用训练的人都是可怕的.但是,我很好奇这段代码是否使用了Haskell的懒惰评估.这部分

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

将创建一个布尔列表,如果只有其中一个是假的(所以如果一个介于2和n的sqrt之间的数字除以n)那么使用'和'函数整个事件是假的.但我认为将首先创建整个列表,然后使用'和'函数.这是真的？如果是这样,我怎样才能通过使用延迟求值来加快速度,以便函数停止并在找到n的第一个除数后返回false.在此先感谢您的帮助!

Answer 1

让我们看一下定义map并and理解:

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

我们还需要定义&&:

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

重要的是要注意这里&&可以短路,这意味着如果你通过它False && undefined,你会False立即得到.但计算True && undefined会抛出错误,因为必须检查第二个参数.

有了map,我们知道它很懒,因为:很懒.我们可以生成一个f x,然后在我们需要时请求列表的其余部分.

所以看着这条线

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

这可以分解为(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

希望通过此扩展,您可以看到一次只处理列表中的一个元素,而列表的其余部分可以保持未计算直到需要.所有这些步骤都是通过直接从函数定义中替换来执行的.正如你可能会看到的那样,如果相反我传入了n = 27,当f 3计算它时它将返回False并导致False && and (map f [4..5])返回False而不消耗列表的其余部分.