リストに要素を追加する

Question

1を正しい順序でリストに追加する関数を書いて、[2, 3]にしたいと思います。私はhaskellに新しく、Ordを使わずにそれを行う方法について助けが必要です。

Answer 1

ソートされたリストに要素を挿入する関数を書くのは難しくありません。これは次のようになります。

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）です。

Answer 2

Ordを使用しないとあなたの質問は意味をなさない。オードを使用して

、あなたが欲しい機能がinsert

あるinsert関数は、要素とリストを受け取り、それはまだより小さいまたは次と等しい最後の位置にリストに要素を挿入素子。