解釋遞歸Haskell列表函數是如何工作的？

我知道下面的功能是什麼我只是想它是如何工作的解釋和所發生的計算：解釋遞歸Haskell列表函數是如何工作的？

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

我似乎失去了它所有的情節現在:(

任何幫助讓我回到正軌上:) :)

2011-06-12 maclunian

你說你已經失去的情節，並偏離了軌道，但你給任何線索到什麼你不明白。這很重要，因爲這段代碼只需要對Haskell非常基本的理解。那麼這裏有沒有你不明白的語法？ – 2011-06-13 01:19:57

這個問題是以誤導的方式編輯的。通過添加OP沒有使用的「遞歸」一詞，它給人留下這樣的印象：OP是有問題的遞歸，但是我們不知道OP在遞歸方面有問題......甚至OP知道遞歸是或知道函數是遞歸的。 – 2011-06-13 01:24:26

@Jim Balter添加了詞遞歸，所以我們可以稍後找到答案，按照適當的條件分類。像「解釋這個功能」這樣的標題是不可搜索的。 – 2011-06-17 17:22:44

它是兩個變量的遞歸函數。你可以打破它除了行由行去理解它：

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 $ \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爲正。

這裏是n和xs中間值的痕跡，通過hood debugger獲得：

enter image description here

2011-06-12 16:05:29

它需要兩個參數，你可以看到：一個Int和一個列表。它通過模式匹配來區分三種情況：1）Int爲零; 2）列表爲空;或者3）Int不爲零，列表也不爲空。

在情況1中它返回列表;在情況2中，它返回空列表（反正是第二個參數）;在情況3中，它遞歸地用原始Int參數減去1和原始列表減去它的第一個元素。

它看起來很像前奏曲中的「drop」。

2011-06-12 16:03:45 rickythesk8r

回答