4

我正在学习http://learnyouahaskell.com/starting-out上的（优秀的）Haskell 教程，并尝试了直角三角形示例：

> let triangles = [(a,b,c) | c <- [1..10], b <- [1..10], a <- [1..10], a^2 + b^2 == c^2]

运行这个我得到了，正如预期的那样：

> triangles 
[(4,3,5),(3,4,5),(8,6,10),(6,8,10)]

现在，我想尝试使用无限列表：

> let triangles = [(a,b,c) | c <- [1..], b <- [1..], a <- [1..], a^2 + b^2 == c^2]

但是当我尝试它时，例如：

> take 2 triangles

...程序只是运行并没有输出。我究竟做错了什么？我认为 Haskells 的懒惰会导致它找到前两个三角形然后停止？

4

2 回答 2

9

好吧，懒惰不是这里的问题。这是您在列表中迭代变量的顺序。

基本上发生的事情是：

  1. c 绑定到 1
  2. b 绑定到 1
  3. a 必然为 1
  4. 检查方程
  5. a 绑定到 2
  6. 检查方程
  7. a 绑定到 3
  8. 检查方程

它会永远持续下去。

所以生成器继续迭代和绑定值a，因为它不知道您需要停止并增加b或c进行更改。

所以你需要以更平衡的方式生成元组。

例如，您可以使用以下方法：

triplesN :: Int -> [(Int, Int, Int)]
triplesN n = [(i, j, n - i - j) | i <- [1..n - 2], 
                                  j <- [1..n - i - 1], i>=j, 
                                  let k = n - i - j,   j>=k]

isTriangle (a, b, c) = a^2 == b^2 + c^2

triangles = filter isTriangle $ concatMap triplesN [1..]

tripleN使用 sum 生成所有有序三元组n。通过将此函数映射到所有自然数上，我们实际上得到了所有有序对的流。最后，我们只过滤那些三角形的三元组。

通过做：

take 10 triangles

我们得到：

[(5,4,3),(10,8,6),(13,12,5),(15,12,9),(17,15,8),(20,16,12),(25,24,7),(25,20,15),(26,24,10),(29,21,20)]

于 2012-11-15T11:19:04.647 回答
6

您可能有兴趣阅读sigfpe 博客上的文章A Monad for Combinatorial Search 。

他定义了一个名为Penalty List或PList的新 monad ，类似于 list monad，但它也具有针对更复杂解决方案的惩罚的概念。当您组合 PLists 时，生成结果的顺序是顺序最小罚分 --> 最大罚分。

在您的示例中，与整数关联的惩罚可能等于整数的大小，与元组关联的惩罚是其元素惩罚的总和。所以元组(3,4,5)的罚分是 3+4+5 = 12，元组(5,12,13)的罚分是 5+12+13 = 30。

使用 list monad，产生的元组的顺序是

(1,1,1), (1,1,2), (1,1,3), (1,1,4), (1,1,5) ...

并且您永远不会看到不是形式的元组(1,1,x)。使用 PList monad，产生的元组可能是

(1,1,1), (1,1,2), (1,2,1), (2,1,1), (1,1,3), (1,3,1), (3,1,1), (1,2,2) ...

在“较大”元组之前生成所有“较小”元组。

对于您的特定问题，此解决方案过于矫枉过正，但在更复杂的问题中可能非常有用。

于 2012-11-15T12:18:07.717 回答