使用foldr在haskell中实现插入

Question

如何在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 被插入一个。

编辑： 谢谢@Lee。

我现在有这个：

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]

解决方案：

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 Rodrigues（只需将 x>=y 更改为 x>y。）

（如何将此标记为已回答？）

Answer 1

你需要 paramorphism 为此：

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

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

有了它，

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

---

我们可以用

foldr

来模仿

init . tails

的同态，如下所示：需要根据元素升序的中断将列表划分为列表（Haskell）。

因此解决方案是

import Data.List (tails)

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

---

对同态进行编码的另一种方法是通过一系列函数，如 Pedro Rodrigues 的答案中所示，安排 从左到右信息流，同时传递输入列表本身的第二个副本：一个参数（复制

tails

的效果）：

insert v xs = foldr g (\ _ -> [v]) xs xs
  where
    g x r xs | v > x     = x : r (tail xs)   -- xs =@= (x:_)
             | otherwise = v : xs

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

与他的答案中的版本不同，这不会复制插入点之后的列表结构的其余部分（这是可能的，因为同态性“鱼与熊掌兼得”）。

Answer 2

这是我的看法：

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 z@(y : ys)
  | x <= y = x : z
  | otherwise = y : insert x ys

Answer 3

我想折叠在这里不太方便。它总是处理列表中的all元素，但是您需要在找到第一个出现的元素后停止。 当然这是可能的，但你可能不想使用这个：

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

Answer 4

这是另一个使用

foldr

的解决方案。与这里的其他人相比，它简单易懂。

insert :: Ord a => a -> [a] -> [a]
insert a = foldr swap [a]
  where
    swap y x_xs@(x:xs)
      | y > x = x:y:xs
      | otherwise = y:x_xs

但是，它有一个严重的限制：与使用正常递归解决方案的标准

Data.List.insert

不同，并且与 Pedro 和 Will Ness 的答案不同，这个版本在给定无限列表时会崩溃。

ghci> take 10 $ insert 4 [1,3..19] -- This works fine.
[1,3,4,5,7,9,11,13,15,17]
ghci> take 10 $ insert 4 [1,3..] -- This crashes.
*** Exception: stack overflow
ghci> import qualified Data.List as L (insert)
ghci> take 10 $ L.insert 4 [1,3..]
[1,3,4,5,7,9,11,13,15,17]