5

我目前在《Learn you a Haskell》的第 6 章……最近才开始研究 99 个问题。

第三个问题是找到列表的第 K 个元素。我已经使用takeand实现了它zip。

我遇到的问题是了解提供的替代解决方案：

elementAt''' xs n = head $ foldr ($) xs 
                     $ replicate (n - 1) tail

我“快到了”，但我不太明白。我知道$但是..你能解释一下上面代码的执行顺序吗？此外，这是否经常被用作各种问题的解决方案，这是惯用的还是只是......杂技？

4

2 回答 2

7

如果扩大定义foldr

foldr f z (x1:x2:x3:...:[]) = x1 `f` x2 `f` x3 `f`... `f` z

你看那elementAt'''变成

elementAt''' xs n = head (tail $ tail $ ... $ tail $ xs)

（注意：如果索引是从 0 开始的，它应该replicate n tail代替）。replicate (n-1) tail

因此，您应用tail适当xs的次数，其结果与drop (n-1) xsifxs足够长的结果相同，但如果太短则会引发错误，并采用head结果列表的 （如果xs太短，后者也会引发错误与drop (n-1)）。

它所做的就是这样

  • 丢弃列表的第一个元素
  • 丢弃结果列表的第一个元素（n-1总共次）
  • 取head结果列表的

此外，这是否经常被用作各种问题的解决方案，这是惯用的还是只是......杂技

在这种情况下，只是杂技。必须先扩展整个foldr应用程序，然后才能返回到前面获取tails，因此它的效率低于直接遍历。

于 2013-01-25T16:50:37.493 回答
6

将其分解为两个主要步骤。首先，该函数复制tail (n-1)时间。所以你最终会得到类似的东西

elementAt''' xs n = head $ foldr ($) xs [tail, tail, tail, ..., tail]

现在，foldron a list 的定义扩展为这样的

foldr f x [y1, y2, y3, ..., yn] = (y1 `f` (y1 `f` (... (yn `f` x))) ...)

因此，该折叠将扩展为（替换f为$和所有ys 为tail）

foldr ($) xs [tail, tail, tail, ..., tail] 
= (tail $ (tail $ (tail $ ...  (tail xs))) ... )
{- Since $ is right associative anyway -}
= tail $ tail $ tail $ tail $ ... $ tail xs

哪里有组合在一起的(n-1)调用。tail取n-1 尾后，它只提取剩余列表的第一个元素并将其返回。

另一种使组合更明确的写法（在我看来）是这样的

elementAt n = head . (foldr (.) id $ replicate (n-1) tail)
于 2013-01-25T16:49:22.923 回答