Designing a general slide window program in Haskell, need type class family?

Question

I was trying to implement a general sliding window algorithm on a list of elements. A common use case is find the largest number in all windows of length 5. Or it can count how many elements in the window is true for some predicate.

The sliding window going from left to right, and maintain some data structure. An element fall outside the window it calls remove on the data structure. if a new element falls within the window, we add the element to the data structure. It also has a function aggregate, which compute something on the data structure.

The naive data structure to use is a dequeue, but it's potentially possible someone want to use other kind of data structure for special use cases.

My original idea was to have a long function that looks like this

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

But I was wondering are there some Haskell way so we can define some class Window a b c, such that we can rewrite the function as

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

runSlidingWindow window input

Of course I don't think the above is valid Haskell code. We want to force any type that is a instance of Window a b c to have functions of the form

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

So having this type class Window a b c is important, since this allows others to implement their own sliding windows.

I'm not aware of how this can be done in Haskell. I think using type class family this is possible? I would like to see an example.

Answer 1

Whenever you think “I need a typeclass”, stop, and consider whether a record of functions would do.

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

Or even, hiding the implementation type:

{-# 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

Typeclasses are best used when you have a reasonable expectation that there is a (near) one-to-one correspondence between types and implementations. While newtype wrappers enable one to expose multiple instances for a given type, relying on this too often is a sign that the semantics of the class are underspecified. Many Haskellers will give more formal laws to a typeclass to better specify its semantics (that being said, ambiguous cases will still exist: e.g. the Applicative instances of [] and ZipList).

To expand further upon the equivalence of typeclasses and records of functions, when you write a typeclass declaration,

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

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

You can equivalently write this as a record (dictionary) of functions,

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

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

The real difference comes when one goes to use the typeclass. While in the case of a typeclass, you get access to the dictionary implicitly,

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

whereas in the case of the record of functions, one must explicitly provide a dictionary,

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

The implicit passing of the dictionary that typeclasses provide makes polymorphic code arguably much nicer to work with. That being said, they are easy to abuse.

I should also say that the role of typeclasses is no longer limited to polymorphism in the dictionary. For instance, recent type system extensions such as TypeFamilies use type classes as a means of implementing basic type level functions.