haskell - 在Haskell中设计一个通用的滑动窗口程序，需要type类族吗？

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