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

Question

我目前正在学习哈斯克尔的第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如果xs是足够长的时间,但引发错误,如果它是太短了,走head在结果列表中(如果xs太短,那后者也将引发错误与drop (n-1)).

它的作用是什么

• 丢弃列表的第一个元素
• 丢弃结果列表的第一个元素(n-1完全时间)
• 获取head结果列表

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

在这种情况下,只是杂技.该foldr程序必须展开全面的应用,才可以上班后向前走的是tailS,因而它比简单的遍历效率较低.

Answer 2

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

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

现在,foldr列表上的定义扩展为类似的内容

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)