2

myUnion次のように開始する必要がある次の関数を検討してください。

myUnion xs ys = foldr ....

私がやろうとしているのは、重複のないすべての要素をfoldr含む新しいリストを作成するために使用することです。まず、 にないのすべての要素をコピーしてから、このチェック後に残っているすべての要素をコピーする必要があります。xsysxsysys

私はかなり長い間この問題を解決しようとしてきましたが、成功していません。私は当然のことながら、いくつかの要素がリストに含まれているかどうかを確認するために prelude 関数をxs使用して分解しようとysx:restますが、使用しなければならないことは、それについてもっと簡単な方法があるかもしれないことを示唆し、私が考えるのを難しくしますこの問題がfoldrで始まらなければならないことを考えると、この問題を解決する方法について。y:rest2elemfoldr

この問題に取り組む方法についての提案に感謝します。

よろしくお願いします。

4

1 に答える 1

2

set に list を使用するのは得策ではないことに注意してください:

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

一意の値のリストを並べ替えた場合は、おそらく unfoldr を使用する必要があります。

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 に答える