2

サブリストのリストを取得し、サブリストを逆にして、連結された逆のサブリストを返す関数を作成しようとしました。これが私の試みです：

conrev :: Ord a => [[a]] -> [a]
conrev [[]] = []
conrev [[a]] = reverse [a]
conrev [(x:xs)] = reverse x ++ conrev [xs]

main = putStrLn (show (conrev [[1,2],[],[3,4]]))

次のエラーが表示されます。

3.hs:4:27:
    Could not deduce (a ~ [a])
    from the context (Ord a)
      bound by the type signature for conrev :: Ord a => [[a]] -> [a]
      at 3.hs:1:11-31
      `a' is a rigid type variable bound by
      the type signature for conrev :: Ord a => [[a]] -> [a] at 3.hs:1:11
    In the first argument of `reverse', namely `x'
    In the first argument of `(++)', namely `reverse x'
    In the expression: reverse x ++ conrev [xs]

私は何を間違っていますか？2 番目の質問は、型シグネチャをより汎用的にできるかどうかです。できるだけ一般的に書く必要があります。

4

2 に答える 2

6

方程式では

conrev [(x:xs)] = reverse x ++ conrev [xs]

空でない list である単一の要素を含むリストに一致しますx:xs。だから、与えられたタイプ

conrev :: Ord a => [[a]] -> [a]

リストx:xsには type が必要[a]であり、したがってx :: a.

ここで、 を呼び出します。これは、 がリストでなければならないことreverse xを意味します。そして、連結しますxx :: [b]

reverse x :: [b]

と

conrev [xs] :: [a]

bと同じ型でなければなりませんa。しかし、それは以前に決定されましたa ~ [b]。したがって、全体として、方程式は を要求しa ~ [a]ます。

(不要な)Ord a制約を記述していなかった場合、不透明度が低くなります。

Couldn't construct infinite type a = [a]

エラー。

外部を削除すると、実装が機能します[]。

conrev :: Ord a => [[a]] -> [a]
conrev [] = []
conrev [a] = reverse a
conrev (x:xs) = reverse x ++ conrev xs

しかし、より良い実装は

conrev = concat . map reverse
于 2013-01-08T20:43:31.763 に答える
3

2 番目のパターンは、必要なものと一致しません。型の構造を値の構造と間違えているようです。

[[a]]aタイプとしては、 「あるタイプのリストのリスト」を意味します

[[a]]パターンとして、「名前にバインドされる単一の要素を含む単一のリストを含むリストに一致します。 a

編集：あなたがやろうとしていることを理解していれば、中間のケースは実際には冗長です。3 番目のケースは空でないリストを処理し、最初のケースは空のリストを処理します。シングルトン リストの別のケースを作成する必要はありません。

編集2：

3 番目のケースの実装には、さらに問題があります。

conrev :: Ord a => [[a]] -> [a]
conrev [(x:xs)] = reverse x ++ conrev [xs]

xtype である必要があり、 type[a]であるxs必要があることがわかるタイプを指定します[[a]]。したがって、書き込みconrev [xs]は type の値を に渡し[[[a]]]ますconrev。これがタイプエラーの原因です。を呼び出す[a]のと同じ型であることを暗黙的に述べています。aconvrev [xs]

于 2013-01-08T20:25:13.407 に答える