解释递归Haskell列表函数是如何工作的？

Question

我知道下面的函数是做什么的，我只想解释一下它是如何工作的，以及发生的计算：

sponge :: Int -> [a] -> [a]
sponge 0 xs = xs
sponge n [] = []
sponge n (x:xs) = sponge (n-1) xs

我现在似乎已经失去了所有的情节：

如果能帮助我重回正轨，我将不胜感激！:)

Answer 1

这是一个关于两个变量的递归函数。您可以逐行拆分它来理解它：

sponge :: Int -> [a] -> [a]

两个参数，一个是Int，一个是一些元素的列表。

sponge 0 xs = xs

基本情况。如果Int参数为零，则返回未修改的列表参数。

sponge n [] = []    

另一种基本情况是，如果列表为空，则立即返回空列表。

sponge n (x:xs) = sponge (n-1) xs

最后，归纳步骤。如果列表是非空的(即至少由一个元素和一个尾部组成，用x:xs表示)，那么结果是在n-1和列表的尾部调用sponge。

那么这个函数会做什么呢？在删除n元素后，它将返回列表的尾部。与drop函数相同：

> drop 10 [1..20]
[11,12,13,14,15,16,17,18,19,20]

和

> sponge 10 [1..20]
[11,12,13,14,15,16,17,18,19,20]

事实上，我们可以要求QuickCheck确认：

> quickCheck $ \n xs -> sponge n xs == drop n xs
*** Failed! Falsifiable (after 7 tests and 5 shrinks):    
-1
[()]

阿!他们不一样。当n为负数时！因此我们可以修改与这两个函数相关的属性：

> quickCheck $ \n xs -> n >= 0 ==> sponge n xs == drop n xs
+++ OK, passed 100 tests.

因此，对于n为正的情况，您的函数的行为类似于drop。

下面是通过hood debugger获取的n和xs中间值的跟踪

​

​

Answer 2

它有两个参数，如您所见:一个Int和一个list。它进行模式匹配以区分三种情况: 1) Int为零；2)列表为空；或3) Int不为零，列表也不为空。

在第一种情况下，它返回列表；在第二种情况下，它返回空列表(这就是第二个参数)；在第三种情况下，它递归地使用原始Int参数减1和原始列表减去第一个元素来调用自己。

它看起来很像前奏曲中的"drop“。