在Haskell中设计一般的幻灯片窗口程序,需要类型类系列吗？

Question

我试图在元素列表上实现一般的滑动窗口算法.一个常见的用例是在长度为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中如何做到这一点.我认为使用类型族这是可能的吗？我想看一个例子.

Answer 1

每当你想到"我需要一个类型类"时,停下来,考虑一下函数记录是否会这样做.

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)]

Answer 2

当您合理地期望类型和实现之间存在(近似)一对一的对应关系时,最好使用类型类.虽然newtype包装器允许一个人为给定类型公开多个实例,但依赖于此通常表明该类的语义未被指定.许多Haskellers将更加正式的法律,以一个类型类,以更好地明确其语义(他这样说,不明确的情况下,仍然会存在:例如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使用类型类作为实现基本类型级别函数的手段.