6

我试图在元素列表上实现通用滑动窗口算法。一个常见的用例是在所有长度为 5 的窗口中找到最大的数字。或者它可以计算窗口中有多少元素对于某个谓词是正确的。

滑动窗口从左到右，并保持一些数据结构。一个元素落在它调用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)]

但我想知道是否有一些 Haskell 方法，所以我们可以定义一些类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

当您合理地期望类型和实现之间存在（接近）一一对应时，最好使用类型类。虽然newtype包装器使人们能够为给定类型公开多个实例，但过于频繁地依赖这一点表明该类的语义未指定。许多 Haskeller 会为类型类提供更正式的规则以更好地指定其语义（也就是说，模棱两可的情况仍然存在：例如and的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 回答