ソートされたリストに整数を挿入する方法

Question

整数をソートした整数リストに正しい位置に挿入しようとしました。

insert :: Int -> [Int] -> [Int] 
insert x [] = [x] 
insert x [y:ys] = if x <= y 
        then [x:y:ys] 
        else y insert x [ys] 

ここで何が間違っていて、それを修正する方法を教えてもらえますか？ここで私が遭遇したエラーは以下のとおりです。あなたが関数ではない要素としてyを扱っている

Answer 1

。新しいリストを作成するには、:を使用する必要があります。また、リストの場合は、[...]またはx:xsの両方を使用します。 [x,y]はx:y:[]の構文砂糖です。

insert x [] = x 
insert x (y:ys) = if x <= y 
        then x:y:ys 
        else y : insert x ys 

Answer 2

別の解決策、（リストに一致するW/O明示的な再帰とパターン）おそらく最も効率的ではありませんが、それでも良いことがあります：

insert :: Int -> [Int] -> [Int] 
insert x l = let (lower, greater) = span (< x) l in lower ++ x : greater 

そして、このソリューションは、あなたが見ることができるように怠惰です：

λ: insert 3 [1,2,4] 
[1,2,3,4] 
λ: take 10 $ insert 5 $ repeat 1 
[1,1,1,1,1,1,1,1,1,1] 

Answer 3

ここではいくつかのエラーがあります。引数リストで

• 、y:ysはすでにリストで、[y:ys]のように再びそれを包むにおける必要は、ありません - これはつまり、リストのリストである、[[Int]]を入力しています。 Haskellにこれが単一の関数記法であることを伝えるためには、ここでも角カッコを入れなければならないことに注意してください：(y:ys)。

• x:y:ysは、既に[x:y:ys]にラップしていません。あなたの「他の」句、y insert x [ys]で

• は関数適用ある - Haskellはyあなたは引数insert、xと[ys]に適用されている機能だと思います。 ysは[ys]にそれをラップしていない、すでにリストです：あなたは、あなたの「他の」句で、あなたが最初のエラーを繰り返し、再びy : insert ...

• のように、ここでオペレータ:を必要としています。

ので、固定ソリューションは、次のようになります。

insert :: Int -> [Int] -> [Int] 
insert x [] = [x] 
insert x (y:ys) = if x <= y 
        then x:y:ys 
        else y : insert x ys