1

質問の一般的な（特殊化された とは対照的に）という用語は、関数が のインスタンスであるタイプである限り、アイテムをソートできることを意味しますOrd。

最も有名な Haskell 広告の 1 つを考えてみましょう

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser  = filter (< p) xs
        greater = filter (>= p) xs

上記の実装はインプレースではありません。
インプレースバージョンを作成しようとしていました。その場でクイックソートを行うのは簡単です。通常、必要なのは変更可能な配列だけであり、私はForeign.Marshal.Array.
私の実装はインプレースであり、非常にうまく動作しますが、その型シグネチャに満足していません

(Ord a, Storable a) => [a] -> IO [a]

より正確に言えば、型制約がStorable a私を悩ませました。

明らかに、アイテムを並べ替えたい場合は、Ord制約が必要ですが、Storable不要です。
対照的に、従来のクイックソートまたはsortinの型シグネチャData.Listは ですOrd a => [a] -> [a]。制約はちょうどOrdです。

追加の制約を取り除く方法が見つかりませんでした。

私は Stackoverflow を検索し、haskell のインプレース クイックソートに関するいくつかの質問を見つけまし
た
。

残念ながら、彼らの主な関心事はただの場所にあります。そこにあるすべてのインプレース クイックソートの例には、追加の型制約もあります。
たとえば、iqsortklapaucius によって指定され た型シグネチャは次のとおりです。

iqsort :: (Vector v a, Ord a) => v a -> v a

タイプ signature でインプレース クイックソート haskell 関数を実装する方法を知っている人はいますOrd a => [a] -> [a]か? インプレース クイックソートを作成する方法は知っていますが、一般
化する方法はわかりません。

4

2 に答える 2

5

iqsort実際、私には完全に一般的に見えます。Data.Vector.Generic ハドックを見ると、実際にはそのインターフェイスを任意の a! 違いは、指定された関数がより一般的であることです。これは、ボックス化されていないベクトルを選択できるためです。これはもちろん、いくつかの a.

リンクは次のとおりです: http://hackage.haskell.org/packages/archive/vector/0.10.0.1/doc/html/Data-Vector-Generic.html

したがって、V をボックス化するように選択すると、ベクトル制約がなくなります。

于 2013-02-03T19:18:36.077 に答える
3

Yes it is possible. (Although in Haskell you want to use this kind of imperative algorithms only in cases where you really need top performance.)

I know of 2 such algorithms:

(Introsort is basically refined quicksort that has O(n log n) worst case complexity.)

I'm not sure about MVector, but for MArrays, you don't have to worry about the additional constraints MArray a e m. They're there to make the type more general, not less. Signatures like

qsort :: (MArray a e m, Ord e) => a Int e -> m ()

allow to use the same algorithm for different array representations. For some data types, you can have specialized arrays of that type which are faster and more compact than generic arrays. For example, if you want to sort 8-bit integers, there is a specialized instance MArray IOUArray Int8 IO for unboxed arrays. And a specialization of qsort for this kind of arrays just using polymorphism is

qsort :: IOUArray Int Int8 -> IO ()

But you also have instance MArray IOArray e IO that works arbitrary e. By using qsort with IOArray, you get a specialization without constraints on e:

qsort :: (Ord e) => IOArray Int e -> IO ()

Furthermore, if you use STArrays and the ST monad, you can sort an array in-place using the same function, and get the result later as a pure value, without IO.

于 2013-02-03T20:04:18.057 に答える