haskell - 是否可以使用 foldl 而不是 foldr 来实现过滤器？

Question

是否可以使用 foldl 而不是 foldr 来实现过滤器？如果是这样，请温和地解释你的实现。

Answer 1

使用差异列表：

filter' :: (a -> Bool) -> [a] -> [a]
filter' p xs = foldl (\k x -> if p x then k . (x:) else k) id xs []

Answer 2

如果您想保持列表的顺序，则效率不高。天真的方法是将其更改为 foldl 然后反转结果列表。

Answer 3

想出了这个：

myFilter p coll =
  foldl step [] coll where 
    step acc e  
      | p e = acc ++ [e] 
      | otherwise = acc

这不是很有效，因为它必须在列表末尾插入一个元素。