0

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

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

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

*関数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)

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

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.

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

1
  • 2
    「エラーの意味がわかりません」というタイトルだと抽象的すぎますので、質問の概要が分かるようなタイトルにしましょう。 Commented 2020年9月17日 6:43

1 件の回答 1

1

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

insertSortedList :: [Int] -> Int -> [Int]

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

insertSortedList([],x)=x

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

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

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

insertSortedList [] x = [x]

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

insertSortedList (a:as) x = if x < a then x:a:as else insertSortedList as x

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

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

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

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

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

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

insertSortedList [] x = [x]
insertSortedList (a:as) x = if x < a then x:a:as else a:insertSortedList as x
1
  • ご回答ありがとうございます。実際にコンパイルを実行して動作することを確認しました。
    – user41837
    Commented 2020年9月18日 12:14

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。