是否可以使用 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

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

Answer 3

想出了这个：

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

它的效率并不高，因为它必须在列表的末尾插入一个元素。