7

纯粹是为了娱乐和练习，我正在尝试编写一个简单的 Haskell 函数来确定整数是否是完美的平方。现在我知道还有其他解决方案，但我想知道是否有办法使用无限列表来做到这一点。我已经从这个开始了，但出于明确的原因，它不起作用（它永远不会停止！）

    isSquare :: Integer -> Bool
    isSquare n = sum[ 1 | x <- [1..], x*x == n] /= 0

另外，如果我可以补充，有人可以指出如何在无限列表中搜索某事的第一个实例，然后停止！?

4

5 回答 5

11

关于无限搜索功能：

已经有一个函数可以在列表中搜索值 - elem。

如果您假设无限列表已排序，我们可以编写一个适用于此类列表的 elem 版本。这可以通过首先拒绝任何小于搜索值的元素来轻松完成。那么第一个未被拒绝的值必须等于或大于搜索元素。如果相等 - 返回真，否则返回假

infiniteElem1 :: (Ord a) => a -> [a] -> Bool
infiniteElem1 x list = (== x) $ head $ dropWhile (< x) list

示例用法：

> infiniteElem1 10 [1..]
True
> infiniteElem1 10 [1,3..]
False

但是有一个问题infiniteElem1：如果在有限列表上使用，如果找不到元素，它可能会抛出异常：

> infiniteElem1 100 [1,2,3]
*** Exception: Prelude.head: empty list

head这是最好避免使用该功能的原因。一个更好的解决方案是：

infiniteElem :: (Ord a) => a -> [a] -> Bool
infiniteElem x list = case dropWhile (< x) list of
  [] -> False
  (v:_) -> v == x

现在它也适用于有限排序列表：

> infiniteElem 100 [1,2,3]
False

有了这个，你的问题就变得微不足道了：

let isSquare n = n `infiniteElem` [ x * x | x <- [1..]]
于 2013-04-26T04:57:55.807 回答
6

您可以使用takeWhile或dropWhile。例如：

isSquare n = head (dropWhile (< n) squares) == n
  where squares = [x*x | x <- [0..]]
于 2013-04-26T04:11:35.380 回答
5

不幸的是，在无限列表上使用 Sum 是行不通的。特别是，您怎么知道列表中的每个未来元素都将为零？你不能，所以你必须在计算总和之前得到整个列表。对于无限列表，这可能需要一些时间。

如果你真的想使用无限列表——毕竟无限列表很有趣——我建议构建一个无限的平方数列表。然后检查是否n在该列表中。你必须对如何做到这一点有点聪明才能确保它终止，但我将把它作为练习留给读者。（伙计，我喜欢这句话：P。）

您可以使用诸如可预测的函数从无限列表中找到某些内容find。一旦发现某些东西，这实际上会停止。但是，如果它没有找到该元素，它将永远不会停止。这可能不是您想要的行为。没有解决此问题的通用方法，但您可以找出解决任何特定问题的方法：例如，如果列表按升序排序，您可以计算可能答案的上限在takeWhile (< limit)哪里。limit

于 2013-04-26T04:11:30.243 回答
4 
let isSquare n = elem n (takeWhile (<=n) [ x*x | x <- [1..]])
ghci> isSquare 25
True
ghci> isSquare 28
False
于 2013-04-26T04:13:05.830 回答
4

只是为了好玩，这是另一个无限列表版本：

isSquare n = isSquare' [1..] where
  isSquare' infiniteList@(x:xs)
    | x*x == n  = True
    | x*x > n   = False
    | otherwise = isSquare' xs
于 2013-04-26T15:27:15.917 回答