2

考虑以下myUnion函数，它必须以如下方式开始：

myUnion xs ys = foldr ....

我想做的是使用foldr创建一个新列表，其中包含所有元素xs且ys没有任何重复项。我必须先复制所有xs不在ys的元素，然后再复制ys检查后剩余的所有元素。

我已经尝试解决这个问题很长一段时间了，但没有任何成功。我自然会尝试分解xsorys并使用 prelude 函数x:rest来检查某个元素是否在列表中，但是必须使用表明可能有一种更简单的方法来解决它，这让我很难思考关于解决这个问题的方法，因为它必须以 foldr 开头。y:rest2elemfoldr

我感谢有关如何解决此问题的任何建议。

提前谢谢了。

4

1 回答 1

2

请注意，将列表用于 set 并不是一个好主意：

myUnion xs ys = Data.List.foldr Data.Set.insert Data.Set.empty (xs ++ ys)

如果您对 uniq 值列表进行了排序，您可能希望使用展开器：

myUnions xs0 ys0 = unfoldr walk (xs0, ys0) where
    walk ([], []) = Nothing
    walk ([], (y:ys')) = Just (y, ([], ys'))
    walk ((x:xs'), []) = Just (x, (xs', []))
    walk (xs@(x:xs'), ys@(y:ys')) | x < y = Just (x, (xs', ys))
                                  | x > y = Just (y, (xs, ys'))
                                  | otherwise = Just (x, (xs', ys'))

但如果你仍然坚持：

myUnion xs ys = foldr myInsert [] (xs++ys) where
    myInsert x zs = if x `elem` zs then zs else (x:zs)

-- this one expects that both lists have uniq items
-- and checks only elements from xs for presence in ys
myUnion xs ys = foldr myInsert ys xs where
    myInsert x zs = if x `elem` ys then zs else (x:zs)
-- but this should be written differently I guess
myUnion xs ys = filter (`notElem` ys) xs ++ ys
于 2013-04-19T09:01:57.003 回答