0

並べ替え対象のリストを先頭の要素と残りの要素のリストに分けたとき、残りの要素のリストを並び替えたものに先頭の要素を挿入する関数insSortを、昇順に並んでいる整数リストasに、昇順を維持したまま新しい整数xを挿入する関数「insertSortedList(as,x)」を用いて作成したいのですが、何度試行を繰り返してもエラーメッセージが出てきてしまいます。
ちなみに私は以下のようにプログラムしました。

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

エラーメッセージ

[1 of 1] Compiling Main             ( sample1002.hs, interpreted )

sample1002.hs:333:31: error:
    • Occurs check: cannot construct the infinite type: t ~ [t]
    • In the expression: a : insertSortedList (as, bs)
      In the expression:
        if a < bs then
            a : insertSortedList (as, bs)
        else
            insertSortedList (as, bs)
      In an equation for ‘insSort’:
          insSort (a : as, bs)
            = if a < bs then
                  a : insertSortedList (as, bs)
              else
                  insertSortedList (as, bs)
    • Relevant bindings include
        bs :: t (bound at sample1002.hs:333:14)
        as :: [t] (bound at sample1002.hs:333:11)
        a :: t (bound at sample1002.hs:333:9)
        insSort :: ([t], t) -> t (bound at sample1002.hs:332:1)
Failed, modules loaded: none.

今回求められているプログラムを、合成関数ではなく普通の関数で定義するなら、例えば関数「mergeSortedList」を用いて、

mergeSortedList(as,[])=as
mergeSortedList([],bs)=bs
mergeSortedList(a:as,b:bs)=if a<b then a:mergeSortedList(as,b:bs) else b:mergeSortedList(a:as,bs)

となると思うのですが、合成関数となりやり方がわからなくなりました。
ご回答よろしくお願いします。

2 件の回答 2

2

並べ替え対象のリストを先頭の要素と残りの要素のリストに分けたとき、残りの要素のリストを並び替えたものに先頭の要素を挿入する関数insSortを、昇順に並んでいる整数リストasに、昇順を維持したまま新しい整数xを挿入する関数「insertSortedList(as,x)」を用いて作成

まず関数insSortの型を考えましょう。関数なので、? -> ?という形式の型になります。->の左側の型(の値)から右側の型(の値)に変換する関数というわけです。いまの場合は、リストから(並び替えた)リストへの変換なので、[a] -> [a]となります。並び替えは、昇順になるようにするので、要素は大小比較可能なものであるという制約が必要ですね。というわけで、単純に考えればinsSort :: Ord a => [a] -> [a]となります。

示された、定義では、insSort :: Ord a => ([a], [a]) -> [a]という型の関数にしようとしているように見えます。そうであるとすると、定義2つめで型エラーになります。左辺にある(a:as, bs)という引数でそれぞれのパラメータの型を考えると、a :: aas :: [a]bs :: [a]です。そうすると、右辺のif式のなかの条件式a < bsが型付けできません。a型の値と[a]型の値を比較しようとしています。比較演算子(<)の型はOrd a => a -> a -> Boolです。すなわち、<は左右の被演算子が同じ型の値でなければなりません。ところが、実際には左被演算子の型はaであり、右被演算子の型は[a]です。エラーメッセージはa型と[a]型は同じとは見なせないというような意味です。

単純に仕様をそのままコードにしてみましょう。定義は以下のようになります。

insSort :: Ord a => [a] -> [a]
insSort []     = []
insSort (x:xs) = insertSortedList (insSort xs, x)

insertSortedList :: Ord a => ([a], a) -> [a]
insertSortedList ([], x)   = [x]
insertSortedList (a:as ,x) = if x < a then x:a:as else a:insertSortedList(as, x)
1
  • ご回答ありがとうございます。まず関数「insSort」の型からして間違っていたので、そこを修正し、ご指摘どおりにプログラムを実行したら、正しくコンパイルできました。
    – user41837
    Commented 2020年10月2日 5:57
2

エラーの内容としては型が何になるかが判別できないということです。

作成したい関数の内容から考えればinsSortはリストを受け取ってソートされたリストを返す関数で、insertSortedListはリストと要素を受け取って要素を挿入したリストを返す関数です。
そのコード中のinsSortはどういう型になってますか? おそらくリストを二つとる関数として書こうとしてるんだと思いますが、そうするとif a<bsinsertSortedList(as,bs)といったコードと矛盾します。bsがリストの要素と同じ型だとしても、insSortの戻り値が要素の場合(insSort([],bs)=bs)とリストの場合(a:insertSortedList(as,bs))があり、やはり矛盾します。それが原因でエラーが出てます。

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

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