70481


昇順に並んでいる整数リストasに、昇順を維持したまま新しい整数xを挿入する関数`interSortedList(as,x)`を定義したいのですが、何回プログラムを実行してもコンパイルエラーが出てしまいます。

私は以下のようにプログラムしました。

[code]

    insertSortedList([],x)=x
    insertSortedList(a:as,x)=if x<a then x:a:as else sort(as,x)
    
[/code]

＊関数sortはすでに定義積みなので割愛。

片方のリストが空だった場合には、そのまま新しい整数xを挿入するだけなので、xと定義する。(`insertSortedList([],x)=x`）  
両方のリストが空ではない場合、もし、挿入する数字xがa未満の場合、xはリストのどの値よりも小さいので、先頭に挿入する。そうでない場合、リストの残りasの中に挿入する。（`insertSortedList(a:as,x)=if
x<a then x:a:as else sort(as,x)`）

このように考えたのですが、次のようなエラーが出てきました。

[code]

    Prelude> :l sample1002.hs
    [1 of 1] Compiling Main             ( sample1002.hs, interpreted )
    
    sample1002.hs:329:54: error:
        • Couldn't match expected type ‘[t]’
                      with actual type ‘([[t]], [t])’
        • In the first argument of ‘sort’, namely ‘(as, x)’
          In the expression: sort (as, x)
          In the expression: if x < a then x : a : as else sort (as, x)
        • Relevant bindings include
            x :: [t] (bound at sample1002.hs:329:23)
            as :: [[t]] (bound at sample1002.hs:329:20)
            a :: [t] (bound at sample1002.hs:329:18)
            insertSortedList :: ([[t]], [t]) -> [t]
              (bound at sample1002.hs:328:1)
    Failed, modules loaded: none.
    
[/code]

どこがおかしいのでしょうか、ご回答お願いします。


CC BY-SA 4.0
2020-09-17T05:58:50.320
70480
2020-09-17T08:21:51.397
2020-09-17T08:21:51.397
153
41837
question
haskell
エラーの意味がわかりません：Couldn't match type


まず `insertSortedList`
の型を考えてみましょう。引数の1つめは昇順のリストで2つめは新規に挿入したい値、そして返り値は挿入済みのリストとなります。これを Haskell
の型で表すと（要素が `Int` であるとするなら）次のようになります。（おそらくプログラミング初心者であると想定して `Ord`
型クラスは使わないようにしています。）

[code]

    insertSortedList :: [Int] -> Int -> [Int]
    
[/code]

さてここで質問の実装を見てみましょう。

[code]

    insertSortedList([],x)=x
    
[/code]

引数に関してですが、`([],x)` とするとタプルを受ける1つの引数になってしまうので `[] x`
として2引数とするのが必須ではありませんが一般的です。

次に返り値に注目すると `x` となっています。これは `Int` であるので `insertSortedList` がリストを返すということと矛盾します。

では何を返すべきなのかを考えると、`x` が要素に1つあるリストを返すべきです。なので正しくは下記となります。

[code]

    insertSortedList [] x = [x]
    
[/code]

空リストで場合でない定義は次のようにします。

[code]

    insertSortedList (a:as) x = if x < a then x:a:as else insertSortedList as x
    
[/code]

変更点は、引数をタプルでなくしました。else 節の `sort` を `insertSortedList` にしました。

これでコンパイルエラーはなくなりました。

実行してみると次のようになります。

[code]

    > insertSortedList [1, 2, 5] 3
    [3,5]
    
[/code]

期待する返り値は `[1, 2, 3, 5]` のはずです。何かバグがあります。

答は空リストでない定義の else 節で `a` が消えている（使われていない）ことにあります。修正すると次のようになります。

[code]

    insertSortedList [] x = [x]
    insertSortedList (a:as) x = if x < a then x:a:as else a:insertSortedList as x
    
[/code]


CC BY-SA 4.0
2020-09-17T06:42:46.100
70481
2020-09-17T06:42:46.100
153
70480
answer