listhaskellinsertlambdafold

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


Solution

  • 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