haskell - Haskell - セットの作成 (一意のソート済みリスト) - 再帰なし、ナブなし

Question

リストの入力でセットを作成する関数を作成することは可能ですか。

再帰を使わずに考えることはできません。

フォールド、フィルター、マップ、ジップなどの高次関数を使用できます。関数に再帰を含めることはできません。

もちろんナブは使えません。

私は、再帰や任意のタイプのループを使用せずに重複を取り除く方法を見つけようとして、頭を悩ませてきました (少なくとも、ループを使用できるとは思わないので、尋ねます)。

Answer 1

それを行う1つの方法：

1. リストを並べ替えます。
2. リストを末尾で圧縮します（たとえば[1,1,2,3]、に変換します[(1,1),(1,2),(2,3)]）
3. 両方の項目が同じであるすべてのペアを削除します。
4. 圧縮されたリストの各ペアの 2 番目の項目が後に続く、ソートされたリストの最初の要素を含むリストを返します。

コード内:

import Data.List

setify [] = []
setify xs = x : map snd (filter (uncurry (/=)) (zip sxs (tail sxs)))
    where sxs = sort xs
          x   = head sxs

Answer 2

もう 1 つは、折り畳みを使用して値を蓄積し、それが以前に見られた場合はメンバーシップ チェックを行うことです。

setify :: (Eq b) => [b] -> [b]
setify = foldl f []
where f acc next | next `elem` acc = acc 
                 | otherwise       = next:acc

最速の方法ではありませんが、仕事は完了します。

Answer 3

グループメソッドを使用できますか? その場合は、リストを並べ替えてグループ化し、最終的に各グループから 1 つの項目を取得できます。

import Data.List

setify :: Eq a => [a] -> [a]
setify = map head . group . sort

Answer 4

なぜ複雑な (そして間違った!) ソリューションが必要なのですか? これを行うだけです：

uniq [] = []
uniq (x:xs)= x:(uniq (filter (/=x) xs))

setify xs = uniq $ sort xs -- If you want to sort too.

リストの末尾から各要素をフィルタリングします。単純。