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

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