顛倒列表順序，而不會增加複雜性

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