我有以下定义：
fibs = 1 : scanl (+) 1 fibs
scanl :: (a -> b -> a) -> a -> [b] -> [a]
scanl f q ls =
q : (case ls of
[] ->[]
x:xs -> scanl f (f q x) xs
)
take :: Int -> [a] -> [a]
take n _ | n <= 0 = []
take _ [] = []
take n (x:xs) = x : take (n-1) xs我想还原下面的表述：
take 3 (fibs)因此，我将继续：
take 3 (fibs)
=
take 3 (1 : scanl (+) 1 fibs)
=
1 : take 2 (scanl (+) 1 fibs)
=
1 : take 2 (scanl (+) 1 (1 : (scanl (+) 1 fibs)))
=
...我怎么能继续推理？
编辑：我继续我的推理，但最后一行是不正确的，因为下一个计算出来的斐波那契数应该是5。我该如何解决这个问题？
take 3 (fibs)
=
take 3 (1 : scanl (+) 1 fibs)
=
1 : take 2 (scanl (+) 1 fibs)
=
1 : take 2 (scanl (+) 1 (1 : (scanl (+) 1 fibs)))
=
1 : take 2 (1 : scanl (+) 2 (scanl (+) 1 fibs))
=
1 : 1 : take 1 (scanl (+) 2 (scanl (+) 1 fibs))
=
1 : 1 : take 1 (scanl (+) 2 (1 : scanl (+) 1 fibs))
=
1 : 1 : take 1 (2 : scanl (+) 3 (scanl (+) 1 fibs))
=
1 : 1 : 2 : take 0 (scanl (+) 3 (1 : scanl (+) 1 fibs))
=
1 : 1 : 2 : take 0 (3 : scanl (+) 4 (1 : scanl (+) 1 fibs))
=
...
1条答案
按热度按时间sd2nnvve1#
使用等式推理，通常可以按任意顺序展开项，而且 * 通常 * 会得到相同的结果。您发现了一个例外--如果您选择了一个特别糟糕的展开顺序，比如不断展开
fibs项而忽略scanl项，您的解可能会无限循环而不产生任何结果，而Haskell对它的评价没有问题。如果你想以Haskell实际计算的方式来扩展你的程序，你需要理解，当且仅当模式匹配需要计算时，无论是在显式的
case语句中，还是在带有模式的函数定义的隐式case语句中，术语都会被计算。因此，当Haskell计算
take 3 fibs时，它需要计算/扩展fibs项的 * 原因 * 是，当第一个参数为正时，take定义中的模式匹配需要在第二个参数上进行模式匹配。详细地说，Haskell首先尝试匹配模式：这需要对
n求值，而n已经被求值为3。这需要计算第二个参数，因为这是Haskell判断它是否为空列表的唯一方法。
在你的（预编辑）资料片中，你实际上遵循了这个规则--即使你没有意识到你在遵循它--直到这个学期。
当Haskell在这里计算
take时，因为2是正数，它需要计算第二个参数。但是第二个参数的计算不会立即通过扩展fibs开始。只有当scanl模式匹配它的第三个参数时才会发生这种情况，所以我们需要先看看scanl在做什么。从代码中可以看出，定义：可以在完全没有模式匹配的情况下应用，因此正确的展开式（即与Haskell实际尝试对其求值的方式相匹配的展开式）为：
现在，
take有足够的关于其第二个参数的信息来继续，因此扩展将通过应用take的定义来继续：case语句需要扩展fibs以进行模式匹配，因此扩展的下一部分应该是：这对于X1 M18 N1 X来说是足够的信息以继续进行（通过应用具有X1 M19 N1 X和X1 M20 N1 X的第二种情况）：
为了使
take继续，它需要检查它的第二个参数，即scanl。这个scanl可以继续，而不需要通过直接应用定义来进一步求值：现在，
take作为足够的信息继续：此时，假设所有列表元素都已按顺序要求，Haskell的下一个工作顺序将是评估第三个元素：
最后一步是计算
take，当它的第一个参数为0时，它不需要进一步计算它的第二个参数，因此我们得到：这是最终的答案。
正如我所说的，这就是Haskell实际上评估程序的方式。（好吧，由于优化，它可能会做得有点不同，但答案肯定是相同的。）
你在编辑中的替代顺序也可以，尽管你做的评估比Haskell做的要多。你得到错误答案的原因是这一步：
不正确。如果要按照您的方法展开第二个
scanl，则需要首先再次展开fibs：现在您可以将
scanl的定义应用于第二个示例：和第一次发生的事件：
不需要更多的计算，但是如果你真的想更进一步，你必须在将
scanl从倒数第二个扩展到第一个之前，再次扩展fibs：你可以看到
5，而不是4，正在慢慢地进入计算。