haskell - 这个函数是否利用了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)])

将创建一个 bool 值列表，如果其中只有一个为 False(因此，如果 2 和 n 的 sqrt 之间的数字整除 n)，则使用“and”函数，整个结果为 False。但我认为将首先创建整个列表，然后使用“and”函数。这是真的？如果是这样，我怎样才能通过使用惰性求值来加快速度，以便函数在找到 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 && 和 (map f [4..5]) 仅返回 False 而不消耗列表的其余部分。