70872


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

[code]

    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)
    
[/code]

エラーメッセージ

[code]

    [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.
    
[/code]

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

[code]

    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)
    
[/code]

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


CC BY-SA 4.0
2020-10-01T12:51:24.447
70867
2020-10-01T15:28:24.280
2020-10-01T13:37:26.987
19110
41837
question
haskell
Haskellの合成関数「insSort」の定義方法


>
> 並べ替え対象のリストを先頭の要素と残りの要素のリストに分けたとき、残りの要素のリストを並び替えたものに先頭の要素を挿入する関数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 :: a`、`as :: [a]`、`bs ::
[a]`です。そうすると、右辺の`if`式のなかの条件式`a <
bs`が型付けできません。a型の値と[a]型の値を比較しようとしています。比較演算子`(<)`の型は`Ord a => a -> a ->
Bool`です。すなわち、`<`は左右の被演算子が同じ型の値でなければなりません。ところが、実際には左被演算子の型は`a`であり、右被演算子の型は`[a]`です。エラーメッセージは`a`型と`[a]`型は同じとは見なせないというような意味です。

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

[code]

    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)
    
[/code]


CC BY-SA 4.0
2020-10-01T15:28:23.063
70872
2020-10-01T15:28:23.063
24701
70867
answer


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

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


CC BY-SA 4.0
2020-10-01T15:28:24.280
70873
2020-10-01T15:28:24.280
33033
70867
answer