Implement insert in haskell with foldr

Question

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?)

Answer 1

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").