Порядок обратного списка без увеличения сложности

Question

Мне нужна была альтернатива filter, которая вместо того, чтобы отбрасывать ложные случаи, хранит их в отдельном месте. Я придумал ниже, но, к сожалению, он меняет список.

Очевидно, я мог бы добавить x в ys или zs вместо cons, но это значительно увеличит сложность.

Есть ли способ сохранить его в порядке, не увеличивая сложность?

splitBy :: (a -> Bool) -> [a] -> ([a],[a]) 
splitBy f xs = splitBy' f xs ([],[]) 
      where 
       splitBy' :: (a -> Bool) -> [a] -> ([a],[a]) -> ([a],[a]) 
       splitBy' _ [] result = result 
       splitBy' f (x:xs) (ys,zs) = if f x then splitBy' f xs (x:ys,zs) 
                else splitBy' f xs (ys,x:zs) 

Answer 1

Как уже говорилось, функция называется partition, и это что-то работает, как этот

partition :: (a -> Bool) -> [a] -> ([a], [a]) 
partition f = foldr (\x ~(yes,no) -> 
         if f x 
         then (x:yes,no) 
         else (yes,x:no)) 
        ([], []) 

за исключением того, что реальная версия добавляет явный xs параметр, возможно, чтобы помочь правила слияния работать должным образом. Если это обалденный матч ленивый шаблон заставляет вас нервничать, вы можете написать это вместо того, чтобы:

partition f = foldr (\x r -> 
         if f x 
         then (x:fst r,snd r) 
         else (fst r,x:snd r)) 
        ([], []) 

Если foldr кажется таинственным для вас, вы можете сделать это следующим образом:

partition f [] = ([], []) 
partition f (x:xs) 
    | f x  = (x:fst r, snd r) 
    | otherwise = (fst r, x:snd r) 
    where r = partition f xs