在不增加复杂性的情况下反转列表顺序

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