在haskell中使用foldr實現插入

如何在haskell中使用foldr實現插入。我試過了：在haskell中使用foldr實現插入

insert'' :: Ord a => a -> [a] -> [a] 
insert'' e xs = foldr (\x -> \y -> if x<y then x:y else y:x) [e] xs

沒有骰子。我必須在列表中插入元素e，以便它在大於或等於它的第一個元素之前。

實施例：

insert'' 2.5 [1,2,3] => [1.0,2.0,2.5,3.0] 
insert'' 2.5 [3,2,1] => [2.5,3.0,2.0,1.0] 
insert'' 2 [1,2,1] => [1,2,2,1]

在最後一個例子中第一2插入一個。編輯：謝謝@李。

我現在有這樣的：

insert'' :: Ord a => a -> [a] -> [a] 
insert'' e xs = insert2 e (reverse xs) 
insert2 e = reverse . snd . foldr (\i (done, l) -> if (done == False) && (vj e i) then (True, e:i:l) else (done, i:l)) (False, []) 
    where vj e i = e<=i

但是這是行不通的：

insert'' 2 [1,3,2,3,3] => [1,3,2,2,3,3] 
insert'' 2 [1,3,3,4] => [1,3,2,3,4] 
insert'' 2 [4,3,2,1] => [4,2,3,2,1]

SOLUTION：

insert'' :: Ord a => a -> [a] -> [a] 
insert'' x xs = foldr pom poc xs False 
    where 
    pom y f je 
     | je || x > y = y : f je 
     | otherwise = x : y : f True 
    poc True = [] 
    poc _ = [x]

感謝@Pedro羅德里格斯（它只是nedded改變X > = y到x> y）

（如何標記爲已回答？）

來源

2013-12-13 excrucio

摺疊通常用於減少列表，而不是擴展它們。另外，你的描述和你的第三個例子是衝突的。根據你的描述，它應該插在3之前，就像你的第一個例子。 – bheklilr

對不起，我編輯了它。 – excrucio

@bheklilr：解決這個問題的最好方法是什麼？它是顯式遞歸還是有更高階的函數來解決這個問題？ – Sibi

這裏是我取它：

insert :: Ord a => a -> [a] -> [a] 
insert x xs = foldr aux initial xs False 
    where 
    aux y f done 
     | done || x > y = y : f done 
     | otherwise = x : y : f True 
    initial True = [] 
    initial _ = [x]

但是恕我直言，使用foldr是不是最合適的這個問題，對我而言以下解決方案更容易理解：

insert :: Int -> [Int] -> [Int] 
insert x [] = [x] 
insert x [email protected](y : ys) 
    | x <= y = x : z 
    | otherwise = y : insert x ys

來源

2013-12-13 15:00:29

你最後的解決方案是明確遞歸的。使用'fodlr'的要點是*隱式*遞歸，以便'foldr'封裝遞歸。 'foldr'的使用表示遞歸;明確的遞歸代碼需要由（人類）頭腦解釋，因此在觀察者眼中「更乾淨」。 :) –

@WillNess授予一個「更清潔」的解決方案是非常主觀的，所以我改變了措辭，說明這只是我的意見。這個問題也可以通過使用'unfoldr'使用隱式遞歸來解決，但那又如何？我仍然發現明確的遞歸解決方案更容易理解任何'foldr'解決方案。 –

當然，我從來沒有聲稱你*應該*做這個或那個。 :) - 順便說一句'unfoldr'封裝了* corecursion *。只是挑剔。 :) –

我想摺疊在這裏不方便。它始終處理列表中的所有元素，但是您需要停止然後才找到第一個發生的事件。當然是可能的，但你可能不希望使用此：

insert' l a = snd $ foldl (\(done, l') b -> if done then (True, l'++[b]) else if a<b then (False, l'++[b]) else (True, l'++[a,b])) (False, []) l

來源

2013-12-13 14:17:29 user3974391

這是與foldl，我不明白。爲什麼我的if不工作？ – excrucio

@excrucio你的程序甚至沒有輸入check，所以現在調試它太早了。 – user3974391

好吧，我知道，但我做錯了什麼。我的「如果」在我看來好，但是當我看着你的時候，你用「\\（done，l'）b」，我不明白爲什麼。也許是一個愚蠢的問題，但我是Haskell的新手。 – excrucio

您需要一個paramorphism爲：

para :: (a -> [a] -> b -> b) -> b -> [a] -> b 
foldr :: (a ->  b -> b) -> b -> [a] -> b 

para c n (x : xs) = c x xs (para c n xs) 
foldr c n (x : xs) = c x (foldr c n xs) 
para c n []  = n 
foldr c n []  = n

有了它，

insert v xs = para (\x xs ys-> if v <= x then (v:x:xs) else (x:ys)) [v] xs

我們可以模仿與foldr paramorphisms超過init . tails，因爲在這裏可以看到：Need to partition a list into lists based on breaks in ascending order of elements (Haskell)。

因此該解決方案是

import Data.List (tails) 

insert v xs = foldr g [v] (init $ tails xs) 
    where 
    g [email protected](x:_) ys | v <= x = v : xs 
        | otherwise = x : ys

的另一種方式爲編碼paramorphism是通過創建嵌套的功能鏈，如在answer by Pedro Rodrigues看出，爲左到右安排信息流程：

insert v xs = foldr g (const [v]) xs xs 
    where 
    g x f xs | v > x  = x : f (tail xs) 
      | otherwise = v : xs 

-- the visual aid to how this works, for list [a,b,c,d]: 
-- g a (g b (g c (g d (const [v])))) [a,b,c,d]

與ver不同在他的回答中，這不會複製插入點之後的其他列表結構（這可以通過paramorphism的「吃蛋糕並擁有它」的能力來實現，即通過傳遞輸入列表的第二個副本作爲額外的參數）。

來源

2013-12-13 15:42:46

在haskell中使用foldr實現插入

回答

相關問題