哈斯克爾遞歸併添加到列表

Question

我是一個Haskell初學者，

我有一個函數

func :: Num a => [a] -> [a] 
func [] = [] 
func (x:xs) = x + func xs 

每個遞歸我想要的價值附加到了我的輸出列表。該函數將對列表中的連續索引進行求和，以使輸入[1, 2, 3, 4]產生[1, 3, 6, 10]。

如何將每次生成的值附加到我的列表中？

Answer 1

這裏你的問題不是如何追加，而是如何計算第一個值。每個項目都需要用它自身的總和代替它之前的所有項目。

下面是做到這一點的一種方法：

Prelude> func (x:xs) = x:map (+ x) (func xs); func [] = [] 
Prelude> func [1, 2, 3, 4] 
[1,3,6,10] 

這是如何工作的？我們給出了一個以元素x開頭的列表，其餘元素xs。我們希望遞歸地將算法應用於xs後，將xs中的每個項目遞增x。

這是x:map (+ x) (func xs)所做的。它讀作爲「在func xs中通過x的增量映射每個元素的結果」前面加上x「。

---

例如，對於[1, 2, 3, 4]，我們希望將1添加到將算法遞歸應用到[2, 3, 4]，然後預先計算的結果的每個成員中。對於[2, 3, 4]，我們希望2爲...至[3, 4]。依此類推，直到最終爲[4]，我們希望4被添加並應用到[]算法的結果之前。

這就是我們的基例（func [] = []）踢入的位置：該算法被定義爲使其返回一個空列表不變。因此func [4]是[4],func [3, 4]是[3, 7]，並且您不斷遞增和前置，直到您獲得[1,3,6,10]。

Answer 2

我認爲在這種特殊情況下，你可以使用scanl1像：

scanl1 (+) [1,2,3,4] -- [1,3,6,10] 

Answer 3

當遍歷列表，我們經常使用褶皺，這正是該列表縮減爲特定值的方式。

還有另一種類型的操作，這是收集沿途所有結果倍，這就是所謂的一個scan（從docs）：

scanl     = scanlGo 
    where 
    scanlGo   :: (b -> a -> b) -> b -> [a] -> [b] 
    scanlGo f q ls = q : (case ls of 
           [] -> [] 
           x:xs -> scanlGo f (f q x) xs) 

所以掃描有三個參數：一個函數它接受兩個值並返回一個值，一個初始值和一個值列表。

掃描將返回一個列表。

因此，您需要的是一個函數，它接受兩個值並返回與第一個相同類型的東西（如果兩者都相同，則可以）。二進制加法將在這裏工作：+。

您還需要一個值（b，這是我們函數的第二個參數），而0是整數加法的標識，所以我們應該使用它。

最後，我們通過您的列表來獲得結果。

試圖弄清楚如何寫作爲摺疊功能，然後作爲掃描，你會發現答案。