haskell - 使用foldr和函数应用($)解释查找列表的第K个元素

Question

我目前正在学习 Haskell 的第 6 章...最近刚刚开始解决 99 个问题。

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

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

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

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

Answer 1

如果展开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) xs if xs 足够长，但如果太短则会引发错误，并获取结果列表的 head(如果 xs 太短，后者也会引发错误 drop (n-1))。

它的作用是这样的

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

Also, is this often used as a solution to various problems, is this idiomatic or just... acrobatic

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