解释递归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),则sponge调用结果n-1并列出列表的尾部.

那么这个功能会做什么呢？删除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 .

这是通过引擎调试器获得的n和的中间值的跟踪:xs