haskell - 自己定義関数の型チェック

Question

私はこの関数を手に入れました：

foo [] = []
foo (x:xs) = foo us ++ foo ys
where us = filter (<=x) xs
      ys = filter (>=x) xs

この関数のタイプはOrda=>[a]->[b]です。

出力タイプが[a]ではなく[b]である理由がわかりません。出力リストの要素は入力リストの要素の一部になるので、[a]にする必要があると思います。

私はHugsを使用していますが、何も変わらないと思います。

Answer 1

ただし、タイプOrd a => [a] -> [b]は内部的に一貫しています。

問題は、入力リストから出力リストに実際に要素を追加することは決してないということです。ベースケースが必要です。のようなものfoo [x] = [x]。現状では、入力リストの要素が出力リストに追加されると実際に言うことはありません。この関数の結果は常にになり[]、入力に関係なくタイプを持つことができ[b]ます。

ただし、ここでクイックソートのようなものを実装しようとしている場合、実装には2つの論理的な問題があります。

1. x、ピボットは出力リストに追加されません。
2. リスト内のそれ自体x以外の値は、から1回とから1回の2回追加されます。xusys