Geek asks and answers

Designing a common slide window program in Haskell, does a class type be required?

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

A sliding window that runs from left to right and supports some data structure. The element goes beyond the window; it calls removein the data structure. if a new element falls into the window, we addelement in the data structure. It also has a function aggregatethat calculates something in the data structure.

The naive data structure to be used is dequeue, but it is potentially possible that someone would want to use a different data structure for special use cases.

My initial 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 if there is any Haskell method, so we can define some class Window a b cso 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 do not think this is the correct Haskell code. We want to force any type that is an instance Window a b cto 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

It is important to have a type class Window a b c, as this allows others to implement their own sliding windows.

I do not know how this can be done in Haskell. I think using a family of type classes is possible? I would like to see an example.

+5
2

, , " ", , .

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

Typeclasses , , () . 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 = (*)
                    }

, typeclass. typeclass ,

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, .

+5

More articles:


All Articles