haskell - (!!) 函数的递归定义

Question

所以我尝试递归地构建 GHC.List 中已定义的 (!!) 函数。我想提取列表的第 n 个元素并返回它。这是我首先得到的:

taken0 :: [β] -> Int -> β -- but not recursive
βs `taken0` 0 = head βs
βs `taken0` n = last (take (n+1) βs)

这有效，但不是递归......

然后我尝试了以下操作:

taken :: [γ] -> Int -> γ -- doesn't compile
taken γs 0 = head γs
taken γs 1 = head (tail γs)
taken γs n = head ( tail (takenth γs (n-1)) )

经过一番修复后，我得到了这个:

taken :: [γ] -> Int -> [γ] -- works, but returns a list
taken γs 0 = γs
taken γs 1 = tail γs
taken γs n = tail (taken γs (n-1))

它确实可以编译，但处理起来很难看，它返回一个列表，其第一个元素是由 n “输入”的元素。

*Main> head ([0,1,2,3,4,5,6,7,8,9] `taken` 0)      returns 0
*Main> head ([0,1,2,3,4,5,6,7,8,9] `taken` 1)      returns 1
*Main> head ([0,1,2,3,4,5,6,7,8,9] `taken` 2)      returns 2
etc.

始终返回右侧(第 n 个元素)但我之前必须插入头部。

我想要的是一个函数，虽然是递归的，但返回单个元素而不是列表......有没有一种方法可以完成此任务，而无需编写另一个函数或每次都使用 head ？像:

*Main> taken2 [5,8,6,0,2,5,7] 3                    returns 0

提前致谢!

Answer 1

taken :: [γ] -> Int -> [γ] -- works, but returns a list
taken γs 0 = γs
taken γs 1 = tail γs
taken γs n = tail (taken γs (n-1))

这非常接近。存在三个问题:

1. 您的案例太多。你只需要这两个:

   taken ys 0 = ...
   taken ys n = ...
   

2. 您想要返回列表的元素，而不是列表。特别是，第一条规则需要返回列表的第一个元素。一种方法是使用 head:

   taken ys 0 = head ys
   

3. 现在我们需要修复第二条规则。我们想递归地写这个，所以我们想做这样的事情:

   taken ys n = taken ?? ??
   

   我们用什么来代替??？好吧，我们知道 n 至少是 1。如果我们下降到0，我们可以使用第一条规则返回结果。这表明第二个参数应该是 (n-1) 正如您已经尝试过的那样。

   我们还知道 ys 的第一个元素不适合使用，因此我们想将其丢弃。为此，我们可以使用 tail ys。把这些放在一起我们得到

   taken ys n = taken (tail ys) (n-1)
   

所以看来这里的主要错误是你在错误的地方应用了tail。

注释

1. 该解决方案并不可靠。如果使用负索引调用它，将会导致无限递归。这种情况的处理留给读者作为练习。

2. 您可以使用模式匹配来代替 head 和 tail。例如第一种情况可以写为

   taken (y:_) 0 = y
   

   我将使用模式匹配实现第二种情况作为读者的练习。