私はデータベース操作のための Haskell-meets-SQL 言語に取り組んでおり、それと一緒に使用する共通の型クラス ライブラリに取り組んでおり、Hackage から意味のあるところはすべて取り入れています。
データベース クエリ オプティマイザーの重要な目的は不要な並べ替えをなくすことであるため、並べ替えが実際に必要な場所の静的な表現を保持することが重要です。これにより、折り畳みの型クラスを定義することができます。
Haskell's Data.Foldablehas: (私が作成しているポイントに関係のないデフォルトの定義を省略しています)
class Foldable t where
-- | Combine the elements of a structure using a monoid.
fold :: Monoid m => t m -> m
-- | Map each element of the structure to a monoid,
-- and combine the results.
foldMap :: Monoid m => (a -> m) -> t a -> m
-- | Right-associative fold of a structure.
foldr :: (a -> b -> b) -> b -> t a -> b
-- | Left-associative fold of a structure.
foldl :: (a -> b -> a) -> a -> t b -> a
-- | A variant of 'foldr' that has no base case,
-- and thus may only be applied to non-empty structures.
foldr1 :: (a -> a -> a) -> t a -> a
-- | A variant of 'foldl' that has no base case,
-- and thus may only be applied to non-empty structures.
foldl1 :: (a -> a -> a) -> t a -> a
このクラスは、ほとんどの Haskell アプリケーションにとって実用上はそれほど重要ではなく、データベースの設定ではより重要な違いを無視しているように思えます。つまり、すべてのData.Foldableインスタンスには順序があります。
要素に順序付けを課さないコンテナ型に適用されるこの概念の一般化の名前は何ですか?
Haskellの場合、実装に必要なコンテキストData.Setがあるため、問題なく機能します。Ordただし、順序付けの要件は実装のアーティファクトであり、多くの有用な型では、使用されている順序付けがドメイン レベルの意味を持たない場合があります。
より一般的なセットの場合fold :: Monoid m => t m -> m、それ自体の定義はほとんど正しいです (そうですfoldMap)。私が言う主な理由は、その型には ( の定義によるMonoid) 結合法則が含まれているが、必要な交換法則は含まれていないためです。他の亜種は存在しません。
必要のないところには導入したくありません。また、追跡できない非決定論を導入したくありません。toList :: Set a -> [a]次の二分法を導入するため、関数がどこにも転がっていない言語とライブラリを構築することに興味があります。
- セット/リレーションが物理的にどのように格納されているかについて、人々が実装の詳細を観察できるようにする
- 効果としての非決定論を見失う
明らかにsortBy :: (a -> a -> Ordering) -> Set a -> [a]との両方shuffle :: Set a -> Data.Random.RVar [a]が有用であり、異論の余地がなく、含まれます。実際、sortByは としてさらに一般的な型を持っていsortBy :: (TheUnorderedFoldableClassIAmTryingToName f) => (a -> a -> Ordering) -> f a -> [a]ます。
このアイデアは何と呼ばれていますか？基地から離れている場合、基地のパスをどこに残したのですか?