如何在Haskell中使用foldr實現刪除

Question

過去幾天我一直在研究褶皺。我可以用它們實現簡單的功能，如length,concat和filter。我所堅持的是試圖用foldr功能來實現，如delete,take和find。我已經實現了這些顯式遞歸，但它似乎並不明顯如何將這些類型的函數轉換爲正確的摺疊。

我已經研究了Graham Hutton和Bernie Pope的教程。仿效Hutton的dropWhile，我能夠使用foldr實現delete，但它在無限列表上失敗。

從閱讀Implement insert in haskell with foldr，How can this function be written using foldr?和Implementing take using foldr，它似乎是我需要使用foldr生成的函數，然後做一些事情。但我不太瞭解這些解決方案，也不知道如何實施delete這種方式。

您能否向我解釋一下使用foldr懶惰版本實現的一般策略，就像我提到的那些。也許你也可以實施delete作爲例子，因爲這可能是最簡單的一個。

我正在尋找初學者可以理解的詳細解釋。我對解決方案不感興趣，我想開發一種理解，這樣我就可以自己想出類似問題的解決方案。

謝謝。

編輯：在寫這篇文章的時候有一個有用的答案，但它不是我正在尋找的。我更感興趣的是使用foldr生成一個函數的方法，然後它執行一些操作。我的問題中的鏈接有這樣的例子。我不太瞭解這些解決方案，因此我想獲得有關此方法的更多信息。

Answer 1

delete是模態搜索。它有兩種不同的操作模式 - 無論它是否已經找到結果。您可以使用foldr構造一個函數，在檢查每個元素時將狀態傳遞給行。因此，在delete的情況下，狀態可以是簡單的Bool。這不是最好的類型，但它可以。

一旦確定了狀態類型，就可以開始使用foldr構造。我將通過我的方式來解決問題。我將啓用ScopedTypeVariables，以便我可以更好地註釋子表達式的類型。一個你知道狀態類型，你知道你想要foldr生成一個函數獲取該類型的值，並返回一個期望的最終類型的值。這足以開始草繪東西。

{-# LANGUAGE ScopedTypeVariables #-} 

delete :: forall a. Eq a => a -> [a] -> [a] 
delete a xs = foldr f undefined xs undefined 
    where 
    f :: a -> (Bool -> [a]) -> (Bool -> [a]) 
    f x g = undefined 

這是一個開始。 g的確切含義在這裏有點棘手。它實際上是處理列表的其餘部分的函數。事實上，把它看作是一個延續是準確的。它絕對代表了您執行摺疊的其餘部分，無論您選擇傳遞什麼狀態。鑑於此，現在是時候弄清楚在undefined的某些地方放些什麼。

{-# LANGUAGE ScopedTypeVariables #-} 

delete :: forall a. Eq a => a -> [a] -> [a] 
delete a xs = foldr f undefined xs undefined 
    where 
    f :: a -> (Bool -> [a]) -> (Bool -> [a]) 
    f x g found | x == a && not found = g True 
       | otherwise   = x : g found 

這似乎相對簡單。如果當前元素是正在搜索的元素，但尚未找到，請不要輸出它，並繼續設置爲True的狀態，表示已找到該元素。 otherwise，輸出當前值並繼續當前狀態。這隻剩下參數foldr。最後一個是初始狀態。另一個是空列表的狀態函數。好的，那些也不算太壞。

{-# LANGUAGE ScopedTypeVariables #-} 

delete :: forall a. Eq a => a -> [a] -> [a] 
delete a xs = foldr f (const []) xs False 
    where 
    f :: a -> (Bool -> [a]) -> (Bool -> [a]) 
    f x g found | x == a && not found = g True 
       | otherwise   = x : g found 

無論狀態是什麼，遇到空列表時都會產生一個空列表。初始狀態是正在搜索的元素尚未找到。

該技術也適用於其他情況。例如，foldl可以這樣寫爲foldr。如果您將foldl看作一個重複轉換初始累加器的函數，那麼您可以猜測這是正在生成的函數 - 如何轉換初始值。

{-# LANGUAGE ScopedTypeVariables #-} 

foldl :: forall a b. (a -> b -> a) -> a -> [b] -> a 
foldl f z xs = foldr g id xs z 
    where 
    g :: b -> (a -> a) -> (a -> a) 
    g x cont acc = undefined 

基座情況都不是太棘手問題時被定義爲操縱所述初始累積器，命名爲z那裏找到。空列表是標識轉換，id，傳遞到創建的函數的值是z。

g的執行更爲棘手。它不能只是盲目地在類型上完成，因爲有兩種不同的實現使用所有期望的值和類型檢查。這種情況下類型不夠，你需要考慮可用函數的含義。

讓我們從看起來應該使用的值及其類型的清單開始。看起來像他們必須在g正文中使用的東西是f :: a -> b -> a,x :: b,cont :: (a -> a)和acc :: a。 f明顯地將x作爲第二個參數，但是存在使用cont的適當位置的問題。要確定它的位置，請記住它表示處理列表的其餘部分返回的轉換函數，並且foldl處理當前元素，然後將處理結果傳遞給列表的其餘部分。

{-# LANGUAGE ScopedTypeVariables #-} 

foldl :: forall a b. (a -> b -> a) -> a -> [b] -> a 
foldl f z xs = foldr g id xs z 
    where 
    g :: b -> (a -> a) -> (a -> a) 
    g x cont acc = cont $ f acc x 

這也表明，foldl'可以這樣寫，只有一個微小的變化：

{-# LANGUAGE ScopedTypeVariables #-} 

foldl' :: forall a b. (a -> b -> a) -> a -> [b] -> a 
foldl' f z xs = foldr g id xs z 
    where 
    g :: b -> (a -> a) -> (a -> a) 
    g x cont acc = cont $! f acc x 

不同的是，($!)在使用之前它傳遞給cont暗示的f acc x評價。 （我說的「建議」，是因爲有一些特殊的情況($!)不會強制評估甚至遠WHNF。）

Answer 2

delete不能在整個列表中均勻操作。計算的結構並不僅僅考慮整個列表中的一個元素。它在碰到要查找的元素後會有所不同。這告訴你它不能被執行爲只是 a foldr。必須進行某種後處理。

發生這種情況時，一般情況是您建立了一對值並在完成foldr時只取其中一個值。這可能是您在模仿Hutton的dropWhile時所做的，儘管我不確定，因爲您沒有包含代碼。像這樣？

delete :: Eq a => a -> [a] -> [a] 
delete a = snd . foldr (\x (xs1, xs2) -> if x == a then (x:xs1, xs1) else (x:xs1, x:xs2)) ([], []) 

主要的想法是，xs1總是會在名單的飽滿的尾部，並xs2是delete在名單尾部的結果。由於您只想刪除匹配的第一個元素，因此當您匹配搜索的值時，您不希望在尾部使用delete的結果，而只是想要將列表的其餘部分保持不變 - 幸運的是總是會在xs1。

是的，這不適用於無限列表 - 但僅限於一個非常具體的原因。 lambda太嚴格了。foldr只適用於無限列表時，它提供的函數並不總是強制評估其第二個參數，並且lambda始終強制評估其對模式匹配中的第二個參數。切換到不可改變的模式匹配可以解決這個問題，即在檢查第二個參數之前，允許lambda生成一個構造函數。

delete :: Eq a => a -> [a] -> [a] 
delete a = snd . foldr (\x ~(xs1, xs2) -> if x == a then (x:xs1, xs1) else (x:xs1, x:xs2)) ([], []) 

這不是獲得該結果的唯一方法。使用let-binding或fst和snd作爲元組的訪問者也可以完成這項工作。但它是最小差異的變化。

這裏最重要的一點是要謹慎處理您傳遞給foldr的還原函數的第二個參數。您希望儘可能延遲檢查第二個參數，以便foldr可以在儘可能多的情況下延遲流動。

如果你看看這個lambda，你會發現在採用第二個參數對reduce函數進行任何操作之前選擇了該分支。此外，大多數情況下，reduce函數都會在結果元組的兩半部分產生一個列表構造函數，然後它需要評估第二個參數。由於這些列表構造函數是使它脫離delete的原因，因此它們對於流式傳輸而言是重要的 - 只要您不讓這一對阻礙。並且使這一對上的模式匹配無可辯駁是讓它不受阻礙的原因。

由於foldr流特性的獎金例如，考慮一下我最喜歡的例子：

dropWhileEnd :: (a -> Bool) -> [a] -> [a] 
dropWhileEnd p = foldr (\x xs -> if p x && null xs then [] else x:xs) [] 

它流 - 儘可能多的，因爲它可以。如果你確切地知道何時以及爲什麼它並沒有流式傳輸，你幾乎可以理解foldr的流式結構的每一個細節。

Answer 3

這裏是一個簡單的刪除，用foldr相似實現：

delete :: (Eq a) => a -> [a] -> [a] 
delete a xs = foldr (\x xs -> if x == a then (xs) else (x:xs)) [] xs