1
を正しい順序でリストに追加する関数を書いて、[2, 3]
にしたいと思います。私はhaskellに新しく、Ord
を使わずにそれを行う方法について助けが必要です。リストに要素を追加する
答えて
ソートされたリストに要素を挿入する関数を書くのは難しくありません。これは次のようになります。
insert :: Ord a => a -> [a] -> [a]
insert x [] = [x]
insert x (y:ys)
| x > y = y : insert x ys
| otherwise = x : y : ys
ただし、これはユースケースでは効率的ではありません。リストの問題は、この種の挿入問題を繰り返して、脊柱の大部分の新しいコピーを繰り返し作成するということです。適切な場所を見つけるまでは、リスト全体を直線的にスキャンする必要があります。これは正しい場所を検索する最速の方法ではありません。
Data.SetやData.IntSetなどのデータ構造を使用する方がよい場合があります。これらは、ツリーや他のデータ構造を使用してリストよりも多くの共有を可能にし、適切な場所をすばやく見つけるため、通常はO(log n)です。
大きなn(リスト/セットサイズ)に対して、O(log n)はO(n)よりも大幅に優れています。これは、提案したようにリストを使用すると得られるものです。 – chrisdb
[a]を返さなければならないのですか?あなたはその答えを詳述できますか? –
リストが「Ord」なしで「正しい順序」にあるかどうかを確認するには – kennytm
これについて設定する前に、必要なものをもっと明確にする必要がありますか? 'louie 1 [2,3]'と 'louie 2 [1,3]'はともに '' 1,2,3 ''であると思います。しかし、例えば、 'louie 1 [3,2]'や 'louie 2 [3,1]'や 'louie 6 [5,3,17,2]'とは何ですか? – applicative