所以我尝试构建 GHC 中已经定义的 (！！) 函数。递归列出。 我想提取列表的第 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
提前感谢！
taken :: [γ] -> Int -> [γ] -- works, but returns a list
taken γs 0 = γs
taken γs 1 = tail γs
taken γs n = tail (taken γs (n-1))
这是非常接近的。有三个问题：
你的案例太多了。您只需要这两个：
taken ys 0 = ... taken ys n = ...您希望返回列表的元素，而不是列表。特别是，第一个规则需要返回列表的第一个元素。一种方法是使用
head：taken ys 0 = head ys现在我们需要修复第二条规则。我们想递归地编写这个，所以我们想做这样的事情：
taken ys n = taken ?? ??我们用什么来代替
??？好吧，我们知道n至少是1.如果我们归结为0，我们可以使用第一条规则返回结果。这表明应该像您已经尝试过的那样(n-1)第二个参数。我们也知道
ys的第一个元素不适合使用，所以我们想把它扔掉。为此，我们可以使用tail ys.把这一切放在一起，我们得到taken ys n = taken (tail ys) (n-1)
因此，这里的主要错误似乎是您在错误的地方应用了tail。
笔记
此解决方案并不可靠。如果使用负索引调用它，则会导致无限递归。对这种情况的处理留给读者作为练习。
您可以使用模式匹配代替
head和tail。例如，第一种情况可以写为taken (y:_) 0 = y我将第二种情况与模式匹配作为读者的练习。
在列表上编写递归函数时，您几乎总是应该从镜像列表类型本身的递归定义开始：空列表的情况和缺点对的情况：
taken :: [γ] -> Int -> γ
taken [] n = _
taken (γ:γs) n = _
请注意，上面带有下划线占位符的语法是实际的 Haskell 语法(对于足够新的 GHC)，这将导致编译器打印出这样的错误，要求您填写空白，并告诉您可用于填写它们的部分：
foo.hs:2:14: error:
• Found hole: _ :: γ
Where: ‘γ’ is a rigid type variable bound by
the type signature for:
taken :: forall γ. [γ] -> Int -> γ
at foo.hs:1:1-24
• In the expression: _
In an equation for ‘taken’: taken [] n = _
• Relevant bindings include
n :: Int (bound at foo.hs:2:10)
taken :: [γ] -> Int -> γ (bound at foo.hs:2:1)
|
2 | taken [] n = _
| ^
foo.hs:3:18: error:
• Found hole: _ :: γ
Where: ‘γ’ is a rigid type variable bound by
the type signature for:
taken :: forall γ. [γ] -> Int -> γ
at foo.hs:1:1-24
• In the expression: _
In an equation for ‘taken’: taken (γ : γs) n = _
• Relevant bindings include
n :: Int (bound at foo.hs:3:14)
γs :: [γ] (bound at foo.hs:3:10)
γ :: γ (bound at foo.hs:3:8)
taken :: [γ] -> Int -> γ (bound at foo.hs:2:1)
|
3 | taken (γ:γs) n = _
|
所以我们需要填补的第一个洞是γ型 .然而，我们唯一可用的东西是Intn，以及对taken进行递归调用。由于列表是空的，因此递归对我们没有帮助;它最终会回到我们所处的同一案例。想想我们的函数应该做什么，无论n是什么，我们都无法获得空列表的第n个元素。所以我们只需要在这里打电话给error。
taken :: [γ] -> Int -> γ
taken [] n = error "Index out of range"
taken (γ:γs) n = _
第二个孔也是γ型，GHC告诉我们：
• Relevant bindings include
n :: Int (bound at foo.hs:3:14)
γs :: [γ] (bound at foo.hs:3:10)
γ :: γ (bound at foo.hs:3:8)
taken :: [γ] -> Int -> γ (bound at foo.hs:2:1)
所以我们显然可以使用γ来安抚类型检查器，但从逻辑上讲，我们返回的值应该取决于n。如果我们采用此列表中的第 0 个元素，那么由于我们的模式匹配，我们已经将 head 元素分解为值γ，因此在这种情况下是正确的。让我们试试：
taken :: [γ] -> Int -> γ
taken [] n = error "Index out of range"
taken (γ:γs) n
| n == 0 = γ
| otherwise = _
这给了我们：
foo.hs:5:17: error:
• Found hole: _ :: γ
Where: ‘γ’ is a rigid type variable bound by
the type signature for:
taken :: forall γ. [γ] -> Int -> γ
at foo.hs:1:1-24
• In the expression: _
In an equation for ‘taken’:
taken (γ : γs) n
| n == 0 = γ
| otherwise = _
• Relevant bindings include
n :: Int (bound at foo.hs:3:14)
γs :: [γ] (bound at foo.hs:3:10)
γ :: γ (bound at foo.hs:3:8)
taken :: [γ] -> Int -> γ (bound at foo.hs:2:1)
|
5 | | otherwise = _
|
相同类型的孔，相同的相关绑定可用。但我们知道γ不是正确的答案，因为我们已经处理过这种情况。我们确实想要返回的答案应该在γs的某个地方，并且我们知道我们想递归地编写这个函数，所以显而易见的事情是插入一个递归调用：
taken :: [γ] -> Int -> γ
taken [] n = error "Index out of range"
taken (γ:γs) n
| n == 0 = γ
| otherwise = taken γs _
foo.hs:5:26: error:
• Found hole: _ :: Int
• In the second argument of ‘taken’, namely ‘_’
In the expression: taken γs _
In an equation for ‘taken’:
taken (γ : γs) n
| n == 0 = γ
| otherwise = taken γs _
• Relevant bindings include
n :: Int (bound at foo.hs:3:14)
γs :: [γ] (bound at foo.hs:3:10)
γ :: γ (bound at foo.hs:3:8)
taken :: [γ] -> Int -> γ (bound at foo.hs:2:1)
|
5 | | otherwise = taken γs _
|
现在我们到了某个地方。剩下的洞是Int型，我们有n :: Int可用。直接插入是很诱人的，但如果我们停下来思考我们正在做的事情，那就没有意义了。当n = 0应该与获取γs的第(n - 1)个元素相同时，取列表的第n个元素(γ:γs)(这是我们应该返回的结果)，因此：
taken :: [γ] -> Int -> γ
taken [] n = error "Index out of range"
taken (γ:γs) n
| n == 0 = γ
| otherwise = taken γs (n - 1)
没有更多的洞！这实际上有效。唯一的问题是我们不处理n的负值。事实证明，这实际上还不错;对于有限列表，我们最终会跑到最后并达到error "Index out of range"情况，这是准确的。但是，在迭代整个列表之前失败会更好。所以：
taken :: [γ] -> Int -> γ
taken [] n = error "Index out of range"
taken (γ:γs) n
| n == 0 = γ
| n < 0 = error "Negative index"
| otherwise = taken γs (n - 1)
我强烈推荐这种"孔驱动开发"风格(无论你是使用实际的孔语法并让GHC进行类型检查，还是在编写代码时自己做)。让你正在使用的类型结构指导你正在编写的函数的"形状"(例如，在列表上编写函数时，使用大小写表示[]，使用大小写表示(x:xs))，然后一次填充一个孔。有时你需要一个不同的结构，而不是引导你前进，但通常不是，即使你已经开始这种方法并找出问题所在，也能为你提供更好的信息来猜测正确的结构。
是的，一个简单的是：
nth0 :: [a] -> Int -> a
nth0 (x:xs) i | i >= 1 = nth0 xs (i-1)
| i < 0 = error "Index less than zero"
| otherwise = x
nth0 [] i = error "Index too large"
所以递归部分是nth0 xs (i-1)。因此，在这里，我们在列表xs的尾部执行递归，并使用递减的索引i-1。
基本情况是otherwise(在i == 0情况下触发)，在这种情况下，我们返回列表的头部x。
其余情况包括指数可能为负数，或指数大于或等于列表长度的事实。