Projektując ogólny program okna slajdów w Haskell, potrzebujesz rodziny klasy?

Question

Próbowałem zaimplementować ogólny algorytm przesuwnego okna na liście elementów. Typowym przypadkiem użycia jest znalezienie największej liczby we wszystkich oknach o długości 5. Lub można policzyć, ile elementów w oknie jest prawdziwe w przypadku niektórych predykatów.

Przesuwne okno przechodzące od lewej do prawej i utrzymanie struktury danych. Element wypada poza okno, które wywołuje remove na strukturze danych. jeśli nowy element wchodzi w okno, my add element do struktury danych. Ma także funkcję aggregate, która oblicza coś na strukturze danych.

Naiwna struktura danych do użycia to kolejka, ale potencjalnie jest możliwe, że ktoś chce użyć innego rodzaju struktury danych do specjalnych zastosowań.

Mój oryginalny pomysł była długa funkcję, która wygląda tak

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

Ale zastanawiałem się, istnieją pewne Haskell sposób więc możemy zdefiniować jakąś klasę Window a b c, tak że możemy przepisać funkcję

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

runSlidingWindow window input 

Oczywiście nie sądzę, że powyższy kod jest prawidłowy. Chcemy wymusić dowolny typ, który jest instancją Window a b c mieć funkcje postaci

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 

więc posiadanie tej klasy typu Window a b c jest ważna, ponieważ pozwala to inni realizują swoje własne okna przesuwne.

Nie jestem świadomy, jak można tego dokonać w Haskell. Myślę, że używając rodziny klasy typu jest to możliwe? Chciałbym zobaczyć przykład.

Answer 1

Ilekroć myślisz "Potrzebuję typeklass", zatrzymaj się i zastanów się, czy zrobiłby to zapis funkcji.

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

Albo nawet, ukrywając typ realizacji:

{-# 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 najlepiej stosować, gdy masz podstawy sądzić, że istnieje (w pobliżu) korespondencja jeden do jednego między rodzajami i wdrożeń. Podczas gdy owijki newtype umożliwiają ujawnienie wielu instancji dla danego typu, poleganie na tym zbyt często jest znakiem, że semantyka klasy jest niedookreślona. Wielu Haskellerów da bardziej formalne prawa do typu, aby lepiej sprecyzować swoją semantykę (co oznacza, że ​​nadal będą występować niejednoznaczne przypadki: np. Instancje Applicative z [] i ZipList).

Aby rozwinąć dalej na równoważności typeclasses i zapisów funkcji podczas pisania deklarację typeclass,

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

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

można równoważnie napisać to jako zapis (słownik) funkcji,

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

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

Prawdziwa różnica pojawia się, gdy używa się czcionki typograficznej.O ile w przypadku typeclass, można uzyskać dostęp do słownika dorozumiany

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

natomiast w przypadku zapisu funkcji, trzeba wyraźnie dostarczenie słownika

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

Domniemana mijania ze słownika, którego dostarcza typografia, sprawia, że ​​polimorficzny kod jest znacznie przyjemniejszy w obsłudze. Biorąc to pod uwagę, łatwo ich nadużywać.

Powinienem również powiedzieć, że rola typografii nie jest już ograniczona do polimorfizmu w słowniku. Na przykład, ostatnie rozszerzenia systemu typu, takie jak TypeFamilies, wykorzystują klasy typów jako sposób implementacji podstawowych funkcji poziomu.