Implement insert in haskell with foldr

问题:

How to implement insert using foldr in haskell. I tried:

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

No dice. I have to insert element e in list so that it goes before first element that is larger or equal to it.

Example:

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]

In last example first 2 is inserted one.

EDIT: Thanks @Lee.

I have this now:

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

But for this is not working:

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]

Thanks @Pedro Rodrigues (It just nedded to change x>=y to x>y.)

(How to mark this as answered?)

回答1:

Here's my take at it:

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]

However IMHO using foldr is not the best fit for this problem, and for me the following solution is easier to understand:

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

回答2:

You need paramorphism for that:

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

with it,

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

---

We can imitate paramorphisms with foldr over init . tails, as can be seen here: Need to partition a list into lists based on breaks in ascending order of elements (Haskell).

Thus the solution is

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

---

Another way to encode paramorphisms is by a chain of functions, as seen in the answer by Pedro Rodrigues, to arrange for the left-to-right information flow while passing a second copy of the input list itself as an argument (replicating the effect of 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]

Unlike the version in his answer, this does not copy the rest of the list structure after the insertion point (which is possible because of paramorphism's "eating the cake and having it too").

回答3:

I suppose fold isn't handy here. It always processes all elements of list, but you need to stop then first occurence was found. Of course it is possible, but you probable don't want to use this:

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