Реализация вставки в haskell с foldr

Question

Как внедрить вставку с помощью складчатости в haskell. Я попытался:

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 вставляется один.

EDIT: Thanks @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 (Это просто nedded изменить х > = y до x> y.)

(Как отметить это как ответ?)

Answer 1

Вот мое взятие на него:

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 2

Я полагаю, что складки здесь не под рукой. Он всегда обрабатывает все элементы списка, но вам нужно остановиться, тогда первое обнаружение найдено. Конечно, это возможно, но вы вероятно, не хотите использовать эту функцию:

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 3

Вам нужен 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 

Мы можем подражать paramorphisms с foldr над 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 xs@(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] 

В отличие от веры в его ответе, это не копирует остальную структуру списка после точки вставки (что стало возможным благодаря способности параморфизма «съесть торт и иметь его», т. е. передав вторую копию списка входных данных как дополнительный аргумент).