7

この挿入機能がある場合：

insert x []     = [x]
insert x (h:t)
  | x <= h      = x:(h:t)
  | otherwise   = h:(insert x t)

これにより、ソートされたリストが生成されます。

foldr insert [] [1,19,-2,7,43]

でも、これ：

foldr1 insert [1,19,-2,7,43]

生成する'無限型を構築することはできません：a0 = [a0] '

2番目の呼び出しが機能しない理由について混乱しています。

foldrとfoldr1の両方の定義を確認し、両方を単純な算術関数でトレースしましたが、2番目の呼び出しが失敗する理由を明確に説明することはできません。

4

5 に答える 5

16

いくつかの型シグネチャを見てみましょう。

foldr  :: (a -> b -> b) -> b -> [a] -> b
foldr1 :: (a -> a -> a) ->      [a] -> a

どちらの場合も、最初の引数は 2 つの引数の関数です。

  • の場合foldr1、これら 2 つの引数は同じ型でなければなりません (結果も同じ型になります)。
  • の場合foldr、これら 2 つの引数の型は異なる場合があります (結果は 2 番目の引数と同じ型になります)。

あなたのタイプは何insertですか？

于 2012-12-08T21:43:36.297 に答える
11

ここで提供される型ベースの回答が好きですが、これを型チェックしたくない理由を説明する運用上の回答も提供したいと思います。foldr1のソースから始めましょう。

foldr1          :: (a -> a -> a) -> [a] -> a
foldr1 _ [x]    = x
foldr1 f (x:xs) = f x (foldr1 f xs)

それでは、プログラムを実行してみましょう。

foldr1 insert [1,19,-2,7,43]
= { list syntax }
foldr1 insert (1:[19,-2,7,43])
= { definition of foldr1 }
insert 1 (foldr1 insert [19,-2,7,43])
= { three copies of the above two steps }
insert 1 (insert 19 (insert (-2) (insert 7 (foldr1 insert [43]))))
= { definition of foldr1 }
insert 1 (insert 19 (insert (-2) (insert 7 43)))

...おっと！それinsert 7 43は決してうまくいきません。=)

于 2012-12-09T01:34:58.200 に答える
4

の型はfoldr1is です(a -> a -> a) -> [a] -> a。つまり、この関数の引数と結果は同じ型です。ただし、inserttype を持っていOrd a => a -> [a] -> [a]ます。foldr1 insert適切に型付けされているため、同じ型aで[a]ある必要があります。

しかし、これはa == [a] == [[a]] == [[[a]]] == ...つまり、a無限に多くのリストの型であることを意味します。

于 2012-12-08T21:42:51.823 に答える
1

foldr1これをやろうとしているからです：

insert 43 -7

これは失敗します。

于 2012-12-08T21:41:50.357 に答える
1

問題は次のとおりです。

foldrこのようにします：

  1. 結果セットinsert 43 []
  2. 結果セットinsert 7 result
  3. 等々

これは明らかに機能します。

一方foldr1、次のことを試みます：

  1. 結果セットinsert 7 43
  2. 結果セットinsert -2 result
  3. 等

これは間違いなく間違っています。ご覧のとおり、foldr1では操作の引数が同じ型である必要がありますが、 の場合はそうではありませんinsert。

于 2012-12-08T21:45:12.893 に答える