6

要素のリストに一般的なスライディング ウィンドウ アルゴリズムを実装しようとしていました。一般的な使用例は、長さ 5 のすべてのウィンドウで最大数を見つけることです。または、ウィンドウ内のいくつかの述語に対して true である要素の数をカウントできます。

左から右に移動するスライディング ウィンドウで、一部のデータ構造を維持します。remove要素が、データ構造で呼び出すウィンドウの外に出ます。新しい要素がウィンドウ内にある場合、addその要素をデータ構造に追加します。aggregateまた、データ構造で何かを計算する関数もあります。

使用する単純なデータ構造はデキューですが、特別なユースケースのために他の種類のデータ構造を使用したい人がいる可能性があります。

私の最初のアイデアは、このような長い関数を持つことでした

runSlidingWindow :: (c->(Int,a)->c)  -- add
                 -> (c->(Int,a)->c)  -- remove
                 -> (c->b)           -- aggregate
                 -> c                -- identity
                 -> Int              -- width
                 -> [(Int,a)]        -- input
                 -> [(Int,b)]

しかしWindow a b c、関数を

runSlidingWindow :: (Window a b c=>WindowInstance a b c)
                 -> WindowInstance a b c
                 -> [(Int,a)]
                 -> [(Int,b)]

runSlidingWindow window input

もちろん、上記は有効な Haskell コードではないと思います。Window a b cのインスタンスであるすべての型に、次の形式の関数を持つように強制したい

add :: (Window a b c=>WindowInstance a b c)
    -> WindowInstance a b c
    -> a
    -> WindowInstance a b c 
remove :: (Window a b c=>WindowInstance a b c)
       -> WindowInstance a b c
       -> a
       -> WindowInstance a b c 
aggregate :: (Window a b c=>WindowInstance a b c)
          -> WindowInstance a b c
          -> b

したがって、この型クラスを持つことWindow a b cは重要です。これにより、他のユーザーが独自のスライディング ウィンドウを実装できるようになるからです。

Haskellでこれを行う方法がわかりません。タイプクラスファミリーを使用すると、これは可能だと思いますか? 例を見てみたい。

4

2 に答える 2

9

「型クラスが必要だ」と思うときはいつでも、立ち止まって、関数の記録で十分かどうかを検討してください。

data Window a b c = Window {
    add       :: c -> (Int, a) -> c,
    remove    :: c -> (Int, a) -> c,
    aggregate :: c -> b,
    identity  :: c,
    width     :: Int}

runSlidingWindow :: Window a b c -> [(Int, a)] -> [(Int, b)]

または、実装タイプを非表示にします。

{-# LANGUAGE ExistentialQuantification #-}

data Window a b = forall c. Window {
    add       :: c -> (Int, a) -> c,
    remove    :: c -> (Int, a) -> c,
    aggregate :: c -> b,
    identity  :: c,
    width     :: Int}

runSlidingWindow :: Window a b -> [(Int, a)] -> [(Int, b)]
于 2013-04-01T10:29:53.533 に答える
5

型クラスは、型と実装の間に (ほぼ) 1 対 1 の対応があるという合理的な期待がある場合に最適に使用されます。ラッパーをnewtype使用すると、特定の型の複数のインスタンスを公開できますが、これに依存しすぎると、クラスのセマンティクスが十分に指定されていないことがわかります。多くの Haskeller は、型クラスのセマンティクスをより適切に指定するために、より正式な規則を型クラスに与えます (とは言え、あいまいなケースは依然として存在します: たとえば と のインスタンスApplicative) 。[]ZipList

型クラスと関数のレコードの等価性をさらに拡張するには、型クラス宣言を記述するときに、

class MyNum t where
    add    :: t -> t -> t
    mul    :: t -> t -> t

instance MyNum Int where
    add = (+)
    mul = (*)

これを関数の記録（辞書）と同等に書くことができ、

data MyNumDict t = MyNumDict { add :: t -> t -> t
                             , mul :: t -> t -> t
                             }

intDict :: MyNumDict Int
intDict = MyNumDict { add = (+)
                    , mul = (*)
                    }

本当の違いは、型クラスを使用するときに発生します。型クラスの場合、暗黙的に辞書にアクセスできますが、

f :: MyNum t => t -> t -> t
f a b = mul a (add a b)

一方、関数のレコードの場合、辞書を明示的に提供する必要があります。

f :: MyNumDict t -> t -> t -> t
f dict a b = myMul a (myAdd a b)
  where myMul = mul dict
        myAdd = add dict

型クラスが提供するディクショナリを暗黙的に渡すことで、ポリモーフィック コードがより使いやすくなることはほぼ間違いありません。そうは言っても、それらは乱用されやすいです。

また、型クラスの役割はもはやディクショナリ内のポリモーフィズムに限定されません。たとえば、TypeFamilies基本的な型レベル関数を実装する手段として型クラスを使用するなどの最近の型システム拡張。

于 2013-04-01T13:43:54.787 に答える