haskell - カスタムフィルター付きクイックソート

haskell quicksort

クイックソートを作成する必要がありますが、カスタムフィルターを使用します。
コンパイル中にfilter (>=x) xsでエラーが発生します。

--sort with two filters
quicksort (x:xs) = (quicksort lesser) ++[x] ++ (quicksort greater)
                  where lesser  = filter (<x) xs
                        greater = filter (>=x) xs

--sort with custom filter
csort f (x:xs) = (csort f lesser) ++ [x] ++ (csort f greater)
                    where lesser  = [e | e <- xs, f x e]
                          greater = [e | e <- xs, not $ f x e]


なにが問題ですか?
答え
あなたを困らせるかもしれないと思う2つの問題があります。

まず、定義を含むファイルをghciにロードします。

ghci> csort (>= x) [2,1,3]

<interactive>:1:10: Not in scope: 'x'


あなたが書いたように、fは2つのパラメーターを取ります。そして実際、xはここでは範囲外です。したがって、カスタムフィルター関数は単に(>=)である必要があります。

ghci> csort (>=) [2,1,3]
***Exception: blahblah: Non-exhaustive patterns in function csort


ここで本当の問題:網羅的でないパターン。これは何を意味するのでしょうか?少なくとも1つの要素でリストをソートする方法の定義を記述しました。しかし、要素のないリストをどのように並べ替えますか?単純です。カスタムフィルター関数を無視して、単に空のリストを生成します。空のリストには要素がないため、すでに「ソート」されています。

csort _ [] = []


その行をソースファイルに追加すると、突然機能しました。パターン[]はパターン(x:xs)を補完し、これらの2つのパターンは共に完全です(リストが空であるか、リストに少なくとも1つの要素があります)。

ghci> csort (>=) [2,1,3]
[1,2,3]
ghci> csort (<) [2,1,3]
[3,2,1]
ghci> quickCheck (\xs -> csort (<) xs == (reverse $ csort (>) xs))
+++ OK, passed 100 tests.




これが私のsort.hsファイルです:

csort _ [] = []
csort f (x:xs) = csort f lesser ++ [x] ++ csort f greater
  where lesser  = [e | e <- xs, f x e]
        greater = [e | e <- xs, not $ f x e]


なぜエラーが続くのか、私にはわかりません。これは私にとっては完璧に機能します。
関連記事

haskell - 文字\ USの字句エラー

haskell - Haskellにllvmバインディングをインストールする

haskell - Happstackで例外をキャッチ

haskell - ハスケル。 MongoDBドライバーまたはAeson文字セットの問題

haskell - ソースコードにアクセスせずにGHCiを使用してモジュールをロードする

haskell - yesodをインストールできません

haskell - このHappstackフォームコードの一部をリファクタリングする方法はありますか?

performance - collat​​zチェーンのパフォーマンスの問題

haskell - 独自のデータ型をモナド関数チェーンの戻り値として定義する方法は?

haskell - 型クラスによる関数型シグネチャのクリーンアップ