nowicjusz Haskell o typach

Question

Jestem całkowicie nowy w Haskell (a bardziej ogólnie w programowaniu funkcjonalnym), więc wybacz mi, jeśli to naprawdę podstawowe rzeczy. Aby uzyskać więcej niż smak, staram się zaimplementować w Haskell jakieś algorytmiczne rzeczy, nad którymi pracuję. Mam prosty moduł Interval, który implementuje interwały na linii. Zawiera funkcję pomocnika

makeInterval :: (Ord t) => t -> t -> Interval t 
makeInterval l r | l <= r = Interval l r 
        | otherwise = error "bad interval" 

i niektóre funkcje użytkowe o odstępach rodzaju

data Interval t = Interval t t 

.

Tutaj interesuję się wielowymiarowymi interwałami (d-interwałami), tymi obiektami, które składają się z interwałów d. Chciałbym osobno rozważyć interwały d, które są połączeniem d rozłącznych przedziałów na linii (wiele przedziałów) od tych, które są związkiem interwału d na d oddzielnych liniach (interwał ścieżki). Z odrębnych algorytmicznych zabiegów na uwadze, że byłoby miło mieć dwa różne typy (nawet jeśli oba są wykazy odstępach tutaj), takie jak

import qualified Interval as I 

-- Multilple interval 
newtype MInterval t = MInterval [I.Interval t] 

    -- Track interval 
newtype TInterval t = TInterval [I.Interval t]  

aby umożliwić odrębne kontrole, np Sanity

makeMInterval :: (Ord t) => [I.Interval t] -> MInterval t 
makeMInterval is = if foldr (&&) True [I.precedes i i' | (i, i') <- zip is (tail is)] 
        then (MInterval is) 
        else error "bad multiple interval" 


makeTInterval :: (Ord t) => [I.Interval t] -> TInterval t 
makeTInterval = TInterval 

Przejdę teraz do sedna! Ale niektóre funkcje dotyczą oczywiście zarówno wielokrotnych interwałów, jak i interwałów ścieżek. Na przykład funkcja order zwróci liczbę interwałów w wielu odstępach lub odstępach między ścieżkami. Co mogę zrobić? Dodawanie

-- Dimensional interval 
data DInterval t = MIntervalStuff (MInterval t) | TIntervalStuff (TInterval t) 

nie pomaga wiele, ponieważ, jeśli dobrze rozumiem (poprawcie mnie jeśli się mylę), musiałbym napisać

order :: DInterval t -> Int 
order (MIntervalStuff (MInterval is)) = length is 
order (TIntervalStuff (TInterval is)) = length is 

i nazywają order jak order (MIntervalStuff is) lub order (TIntervalStuff is) gdy is to MInterval lub TInterval. Nie tak wspaniale, to wygląda dziwnie. Nie chcę też powielać funkcji (mam wiele funkcji związanych zarówno z wielokrotnymi i śledzącymi intevals, jak i kilkoma innymi definicjami d-interval, takimi jak wielokrotność długości równej i interwały ścieżek).

Pozostało mi poczucie, że całkowicie się mylę i przegapiłem jakiś ważny punkt dotyczący typów w Haskell (i/lub nie można tu zapomnieć o programowaniu OO). Więc, całkiem nowe pytanie, jaki byłby najlepszy sposób w Haskell, aby poradzić sobie z taką sytuacją? Czy muszę zapomnieć o wprowadzaniu MInterval i TInterval i używać tylko jednego typu?

dziękuję za pomoc,

Garulfo

Answer 1

rozważyć zastosowanie typeclasses pokazać podobieństwa między różnymi rodzajami. Zobacz samouczek haskell [1] o klasach i przeciążaniu, aby uzyskać pomoc.

[1]: http://www.haskell.org/tutorial/classes.html Haskell poradnik

Answer 2

Co chcesz to typy o tej samej strukturze i wspólnych operacji, ale które mogą być wybitny, i dla których pewne operacje sens tylko na jednej lub innego typu. Idiomem tego w Haskell są Phantom Types.

1. http://www.haskell.org/haskellwiki/Phantom_type
2. http://www.haskell.org/haskellwiki/Wrapper_types
3. http://blog.malde.org/index.php/2009/05/14/using-a-phantom-type-to-label-different-kinds-of-sequences/
4. http://neilmitchell.blogspot.com/2007/04/phantom-types-for-real-problems.html

Answer 3

Edycja: jest to ten sam pomysł jako odpowiedź SCLV za; jego linki dostarczają więcej informacji na temat tej techniki.

Co z tym podejściem?

data MInterval = MInterval --multiple interval 
data TInterval = TInterval --track interval 

data DInterval s t = DInterval [I.Interval t] 

makeMInterval :: (Ord t) => [I.Interval t] -> Maybe (DInterval MInterval t) 
makeMInterval is = if foldr (&&) True [I.precedes i i' | (i, i') <- zip is (tail is)] 
    then Just (DInterval is) 
    else Nothing 

order :: DInterval s t -> Int 
order (DInterval is) = length is 

equalOrder :: DInterval s1 t -> DInterval s2 t -> Bool 
equalOrder i1 i2 = order i1 == order i2 

addToMInterval :: DInterval MInterval t -> Interval t -> Maybe (DInterval MInterval t) 
addToMInterval = .. 

W tym przypadku typ DInterval reprezentuje interwały wielowymiarowe, ale przyjmuje dodatkowy parametr typu jako typ fantomowy. Ta dodatkowa informacja o typie pozwala rozróżniać typy interwałów, nawet jeśli mają dokładnie taką samą reprezentację.

Otrzymujesz bezpieczeństwo swojego oryginalnego projektu, ale wszystkie twoje struktury mają tę samą implementację. Co istotne, gdy typ interwału nie ma znaczenia, możesz pozostawić go nieokreślonym.

Zmieniłem również implementację Twojej funkcji makeMisior; zwrócenie Maybe dla takiej funkcji jest o wiele bardziej idiomatyczne niż wywołanie błędu.

Więcej wyjaśnienie Może:

Przeanalizujmy swoją funkcję makeInterval. Ta funkcja powinna mieć listę Interwałów, a jeśli spełniają kryteria, zwrócić wielokrotny interwał, w przeciwnym razie odstęp między śladami. To wyjaśnienie prowadzi do typu:

makeInterval :: (Ord t) => 
    [I.Interval t] -> 
    Either (DInterval TInterval t) (DInterval MInterval t) 

Teraz, kiedy mamy ten typ, jak możemy go wdrożyć? Chcielibyśmy ponownie użyć naszej funkcji makeMInterval.

makeInterval is = maybe 
        (Left $ DInterval TInterval is) 
        Right 
        (makeMInterval is) 

Funkcja maybe przyjmuje trzy argumenty: domyślny b używać jeżeli Może to Nothing, funkcję a -> b jeśli Może to Just a i Maybe a. Zwraca wartość domyślną lub wynik zastosowania funkcji do wartości Może.

Naszą domyślną wartością jest interwał ścieżki, dlatego dla pierwszego argumentu tworzymy lewy interwał ścieżki. Jeśli może to być Just (DInterval MInterval t), już istnieje wiele interwałów, więc wszystko, co konieczne, to wstawienie go do prawej strony. Ostatecznie, makeMInterval służy do tworzenia wielokrotnego przedziału.

Answer 4

Czego chcesz, to typografia. Typ jest taki, jak przeciążanie odbywa się w Haskell. Klasa typów jest wspólną strukturą wspólną wielu typom. W twoim przypadku, gdy chcesz utworzyć klasę wszystkich typów, które mają order funkcję:

class Dimensional a where 
    order :: a -> Int 

to mówiąc istnieje klasa typów a zwanych Dimensional, a dla każdego typu należącym do tej klasy jest funkcją a -> Int nazywa order.Teraz musisz zadeklarować wszystkie swoje typy jako należące do klasy:

instance Dimensional MInterval where 
    order (MInterval is) = length is 

i tak dalej. Można również zadeklarować funkcje, które działają na rzeczy, które są z danej klasy, w ten sposób:

isOneDimensional :: (Dimensional a) => a -> Bool 
isOneDimensional interval = (order interval == 1) 

deklaracji typu można odczytać „dla wszystkich rodzajów a które należą do typeclass Dimensional, to funkcje wykonuje a i zwraca Bool ".

Lubię myśleć o klasach jako strukturach algebraicznych w matematyce (nie jest to całkiem to samo, czego nie można wymusić na ograniczeniach logicznych, ale ...): podajesz, jakie są wymagania, aby dany typ należał do niektóre klasy (analogicznie operacje muszą być zdefiniowane w zestawie, aby należały do ​​pewnej algebraicznej konstrukcji), a następnie, dla każdego określonego typu, podajesz, jaka jest specyficzna implementacja wymaganych funkcji (w analogii, co są określone funkcje dla każdego określonego zestawu).

Weźmy na przykład grupę. Grupy musi mieć tożsamość, to odwrotność dla każdego elementu i mnożenie:

class Group a where: 
     identity :: a 
     inverse :: a -> a 
     (<*>)  :: a -> a -> a 

i Liczby tworzą grupę pod Ponadto:

instance Group Integer where: 
     identity = 0 
     inverse x = (- x) 
     x <*> y  = x + y 

Należy pamiętać, że to nie rozwiąże powtórzeń, jak trzeba stwórz każdy typ.