自己的小块功能 - 如何使用foldl / foldr？

Question

这是我自己的nub实现（删除重复项）：

nub :: (Eq a) => [a] -> [a]
nub lista = nub_rec lista []
    where
        nub_rec :: (Eq a) => [a] -> [a] -> [a]
        nub_rec [] acc = acc
        nub_rec (x:xs) acc = nub_rec (filter (\y -> if y == x then False else True) xs) (x:acc)

我考虑如何使用foldr / foldl来实现nub，你能帮助我吗？我看不出办法。

Answer 1

首先，你对nub的实现比它需要的要复杂得多（并且它颠倒了列表中元素的顺序）。这是一个更简单的：

myNub :: Eq a => [a] -> [a]
myNub (x:xs) = x : filter (/= x) (myNub xs)
myNub [] = []

现在，如果我们想使用foldr编写一个将输出的函数，而不仅仅是一个“聚合”而是一个完整的列表，首先看一下最简单的基于foldr的函数是很有用的，它接受一个列表并吐出一个列表：

myNoop :: [a] -> [a]
myNoop l = foldr (\ x xs -> x : xs) [] l

鉴于此，filter必须插入某处。既然我认为这是一个功课，我会把它留给OP作为练习:)

Answer 2

解决方案只有filter和foldr，没有直接（或自我）递归：

removeDuplicates :: Eq a => [a] -> [a]
removeDuplicates = foldr (\z ys -> z : filter (/= z) ys) []