Pytanie Wymuszony porządek wzoru


Piszę silnik gry Magic The Gathering (MTG) w Haskell.

Dla tych, którzy nie znają MTG, jest to gra karciana, w której karty mogą mieć maksymalnie 5 kolorów: biały (W), niebieski (U), czarny (B), czerwony (R) i zielony (G).

{-# LANGUAGE ViewPatterns #-}
import Data.Set

data Color = W | U | B | R | G
    deriving (Show, Eq, Ord)

data Card = Card (Set Color) -- simplified Card type with only its colors

viewColors :: Card -> [Color]
viewColors (Card colors) = toList colors

Chciałbym dopasować wzór do kolorów takich jak:

foo :: Card -> String
foo (viewColors -> [W, B]) = "card is white and black"
foo _ = "whatever"

Jak na razie dobrze. Ale jest jeden problem: mogę nieprawidłowo wpisać kolejność kolorów we wzorcu widoku:

bar :: Card -> String
bar (viewColors -> [B, W]) = "this will never get hit"
bar _ = "whatever"

Oczywiście, mógłbym napisać viewColors w sposób, który bezpośrednio rozwiązuje ten problem. Albo mógłbym użyć strażników, ale wolałbym nie. Oto kilka sposobów, aby to zrobić

viewColors :: Card -> (Bool, Bool, Bool, Bool, Bool)
viewColors (Card colors) = let m = (`member` colors)
    in (m W, m U, m B, m R, m G)

To rozwiązanie jest zbyt szczegółowe, gdy dopasowuję wzorce, nawet jeśli używam typu izomorficznego Bool ale z krótszymi (i / lub znaczącymi) identyfikatorami. Dopasowanie zielonej karty powinno wyglądać

baz :: Card -> String
baz (viewColors -> (False, False, False, False, True)) = "it's green"

data ColorView = W | WU | WUB | ... all combos here

viewColors :: Card -> ColorView
viewColors (Card colors) = extract correct Colorview from colors

To rozwiązanie ma kombinatoryczną eksplozję. Wydaje się bardzo złe do wdrożenia, ale przyjemne w użyciu, szczególnie jeśli mam colorViewToList :: ColorView -> [Color] aby umożliwić ekstrakcję programową po dopasowaniu wzorca.


Nie mam pojęcia, czy w Haskell można podać przybliżoną wartość, ale następujące rozwiązanie byłoby idealne:

fuz :: Card -> String
fuz (viewColors -> (W :* ())) = "it's white"
fuz (viewColors -> (W :* U :* ())) = "it's white and blue"
fuz (viewColors -> (W :* B :* ())) = "it's white and black"

Jestem gotów użyć zaawansowanych rozszerzeń językowych, aby zezwolić na ten rodzaj kodu: DataKinds, PolyKinds, TypeFamilies, MultiParamTypeClasses, GADTs, co ty na to.

Czy coś takiego jest możliwe? Czy masz inne sugerowane podejścia?


11
2017-09-24 19:03


pochodzenie


Dlaczego nie używać strażników? Strażnik byłby prawie tak piękny jak wzór widoku: f card | card kolor` [B, W] = ... | karta color [B, U, W] = ... ". To także brzmi jak fajny projekt; co zamierzasz z tym zrobić? - Tikhon Jelvis
Możesz chcieć sprawdzić to na zewnątrz. - Paul Visschers
@TikhonJelvis: Nie jestem uczulony na strażników ... są one czyste i łatwe. Po prostu kocham wzór pasujący do wielu innych. Również nauka tej teorii jest interesująca sama w sobie. - Thomas Eding
@PaulVisschers: Dzięki za link. Byłem zaskoczony, że znalazłem ten sam link, gdy googlowałem "Haskell mtg". Zdecydowanie coś, co chciałbym przejrzeć, ale uważam, że zamierzam przyjąć radykalnie odmienne podejście do mojego silnika (to samo odnosi się do innych programów magicznych Open Source). - Thomas Eding
OverloadedLists pomogłoby tutaj.


Odpowiedzi:


Podoba mi się rozwiązanie rekordowe, ale łatwo zrobić z typami

{-# LANGUAGE ViewPatterns, ScopedTypeVariables #-}

import qualified Data.Set as Set

data Color = W' | U' | B' | R' | G' deriving (Show, Eq, Ord)
data Card = Card (Set.Set Color) 

newtype W a = W a
newtype U a = U a
newtype B a = B a
newtype R a = R a
newtype G a = G a

class ToColors x where
  toColors :: x -> [Color]
  reify :: x

instance ToColors () where
  toColors _ = []
  reify = ()

instance ToColors a => ToColors (W a) where
  toColors (W a) = W':toColors a
  reify = W reify

--other instances

members :: Set.Set Color -> [Color] -> Bool
members s = foldl (\b e -> b && (Set.member e s)) True

viewColors :: forall a. ToColors a => Card -> Maybe a
viewColors (Card s) = let a = reify :: a in 
  if members s (toColors a) then (Just a) else Nothing

foo :: Card -> String
foo (viewColors -> Just (W (B ()))) = "card is white and black"
foo _ = "whatever"

można to łatwo przerobić, aby uzyskać inne składnie. Podobnie, można zdefiniować kolory, które mają być typami, które nie pobierają parametrów, a następnie użyć niejednorodnego konstruktora list infix. Tak czy inaczej nie dba o porządek.

Edycja: jeśli chcesz dopasować dokładne zestawy, które również są łatwe - po prostu zastąp members działają tak jak

viewColors :: forall a. ToColors a => Card -> Maybe a
viewColors (Card s) = let a = reify :: a in 
  if s == (Set.fromList . toColors $ a) then (Just a) else Nothing

3
2017-09-24 22:23



Niesamowite, to dokładnie zaspokaja moje potrzeby. Powiedział, że ScopedTypeVariables jest całkowicie niepotrzebny, aby to skompilować;) (Cóż, przynajmniej jeśli ograniczenie monomorfizmu nie jest wyłączone.) - Thomas Eding
@ThomasEding. Powinienem był o tym pomyśleć. Możesz również uzyskać to do typecheck nawet z NoMonomorphismRestriction włączone, jeśli używasz abstrakcji zamiast let aby uniknąć uogólnienia viewColors (Card s) = flip ($) reify (\a -> if s == (Set.fromList . toColors $ a) then (Just a) else Nothing) ma typ inferencyjny viewColors :: ToColors a => Card -> Maybe a właśnie tego chcesz - Philip JF
@ThomasEding To rozwiązanie ma tę samą moc co "rozwiązanie rekordowe". Just (W (B ()))) jest zarówno [W',B',U'] i [W',B'], ale nie [W'] - wit
@wit edycja daje dokładne dopasowanie. Więc nie. - Philip JF


Głównym problemem jest to, że chcesz mieć permutację zamiast pojedynczej wartości z view. Mamy tylko jeden typ, który umożliwia permutację - zapis.

Możemy więc dodać nowe dane, typ rekordu

data B = F|T -- just shorter name for Bool in patterns
data Palette = P {isW, isU, isB, isR, isG :: B}

bool2b :: Bool -> B
bool2b True  = T
bool2b False = F

viewColors :: Card -> Palette
viewColors (Card colors) = let m = bool2b . (`member` colors)
    in P {isW = m W, isU = m U, isB = m B, isR = m R, isG = m G}

foo :: Card -> String
foo (viewColors -> P {isW=T, isB=T}) = "card is white and black"
foo _ = "whatever"

ZAKTUALIZOWANE

My też mogliśmy zaprzeczać niewłaściwe wzory. Ale to rozwiązanie jest bardziej brzydkie, ale pozwala używać "klasycznych" wzorów

{-# LANGUAGE GADTs #-}
{-# LANGUAGE EmptyDataDecls #-}
{-# LANGUAGE RankNTypes #-}
data Color = W | U | B | R | G  deriving (Eq)

data W' 
data U' 
data B'
data R'
data G'

data Color' a where
      W' :: Color' W'
      U' :: Color' U'
      B' :: Color' B'
      R' :: Color' R'
      G' :: Color' G'

data M a = N | J a -- just shorter name for Maybe a in patterns

data Palette = Palette 
      (M (Color' W')) 
      (M (Color' U')) 
      (M (Color' B')) 
      (M (Color' R')) 
      (M (Color' G'))

i zdefiniuj viewColor:

viewColors :: Card -> Palette
viewColors (Card colors) = 
  let 
    m :: Color -> Color' a -> M (Color' a)
    m c e = if c `member` colors then J e else N
  in P (m W W') (m U U') (m B B') (m R R') (m G G')

foo :: Card -> String
foo (viewColors -> Palette (J W') N (J B') N N) = 
      "card is white and black"
foo _ = "whatever"

4
2017-09-24 21:48



Fajne rozwiązanie, ale czy istnieje sposób, aby uzyskać kartę, której kolory nie pasują do WUB? foo (viewColors -> P { isW=T })? Niezależnie od tego przydaje się przynajmniej przetestowanie części kolorów karty. - Thomas Eding
@ThomasEding, dodaj także odmawianie złych wzorców - wit


EDYTOWAĆ: Dalsze testy pokazują, że to rozwiązanie w rzeczywistości nie działa.


W rzeczywistości nie potrzebujesz więcej rozszerzeń, wymyśliłem rozwiązanie, które robi to, co chcesz, ale prawdopodobnie będziesz chciał je zoptymalizować, zmienić nazwy niektórych rzeczy i uczynić je nieco mniej brzydkimi. Trzeba tylko utworzyć nowy typ danych i zaimplementować Eq siebie i użyj operatora infixr:

{-# LANGUAGE ViewPatterns #-}
import Data.Set

data Color = W | U | B | R | G
    deriving (Show, Eq, Ord)

data Card = Card (Set Color) -- simplified Card type with only its colors

-- you may need to fiddle with the precedence here
infixr 0 :*
data MyList a = END | a :* (MyList a) deriving (Show)

myFromList :: [a] -> MyList a
myFromList [] = END
myFromList (x:xs) = x :* myFromList xs

instance Eq a => Eq (MyList a) where
    END == END = True
    END == _   = False
    _   == END = False
    l1  == l2  = allElem l1 l2 && allElem l2 l1
        where
            -- optimize this, otherwise it'll just be really slow
            -- I was just too lazy to write it correctly
            elemMyList :: Eq a => a -> MyList a -> Bool
            elemMyList a ml = case ml of
                END -> False
                (h :* rest) -> if a == h then True else elemMyList a rest
            allElem :: Eq a => MyList a -> MyList a -> Bool
            allElem END l = True
            allElem (h :* rest) l = h `elemMyList` l && allElem rest l

viewColors :: Card -> MyList Color
viewColors (Card colors) = myFromList $ toList colors

fuz :: Card -> String
fuz (viewColors -> (W :* END)) = "it's white"
fuz (viewColors -> (W :* U :* END)) = "it's white and blue"
fuz (viewColors -> (W :* B :* END)) = "it's white and black"
fuz (viewColors -> (W :* B :* R :* END)) = "it's white, black, and red"
fuz (viewColors -> (W :* U :* B :* R :* G :* END)) = "it's all colors"
fuz _ = "I don't know all my colors"

main = do
    putStrLn $ fuz $ Card $ fromList [W, B]
    putStrLn $ fuz $ Card $ fromList [B, W]

EDYCJA: Poprawiono trochę kod


2
2017-09-24 19:48



Innym podobnym rozwiązaniem byłoby przekonwertowanie każdego MyList a w [a], posortuj, po prostu użyj ==. Prawdopodobnie będzie to mniej linii łatwiejszego do odczytania kodu. Jednak napisałem to dość szybko, więc istnieje wyraźna możliwość poprawy. - bheklilr
To rozwiązanie również nie działa. Na przykład, jeśli piszę WU jako (U :* W :* END) i zmień main kolory kart do [W, U] i [U, W] Dostaję "Nie znam wszystkich moich kolorów" dla obu. To powiedziawszy, twoja uwaga zainspirowała mnie do napisania wzorca dla meczu, z którego byłbym zadowolony: fuz (matchColors [W, U] -> True) = blah gdzie matchColors może masować wejście do pracy bez względu na pisemną kolejność. - Thomas Eding
@ThomasEding Huh, dziwne, powiem tylko, że napisałem ten kod dość szybko i nie robiłem z nim zbyt wielu testów, ale podstawy są po to, by dostać to, czego chcesz. Jeśli jednak zamierzasz po prostu użyć matchColors, więc możesz równie dobrze użyć strażników, to też byłby czystszy kod. - bheklilr
Tak. Więcej lub ciekawość niż cokolwiek innego. Prawdopodobnie skończę robić oczywiste (strażnicy), ale nadal będę majstrować przy moim oryginalnym problemie, aby nauczyć się czegoś nowego. - Thomas Eding
Nie wiem zbyt wiele ViewPatterns, więc sprawdziłem wyjście z ghc --make -ddump-simpl code.hs i szybko przekonałem się, że zamienia to na dopasowywanie do wzorca z opisem sprawy, więc nie sądzę, by istniała jakakolwiek możliwość, że będzie działał tak, jak byś tego chciał. Możesz spróbować trochę więcej, ale nie sądzę, że to, czego chcesz, jest naprawdę możliwe. Wygląda na to, że moje wcześniejsze testy mogły być tylko przypadkiem, ponieważ nie używają one Eq wystąpienie w ogóle. - bheklilr


Myślę, że powinieneś skupić się na wyrażeniu tego, co kolory karty mogą być pierwsze, a następnie martwić się o inne kwestie, takie jak późniejsza komplikacja. Brzmi dla mnie jak twoje Bool rozwiązanie krotkowe jest prawie idealne, ale zgaduję, że karta musi mieć jeden kolor, prawda?

W takim przypadku coś takiego może działać i być całkiem łatwe do dopasowania wzoru:

data CardColors = W' BlackBool GreenBool ...
                | B' WhiteBool GreenBool ...
                | G' BlackBool WhiteBool ...
                ....

data BlackBool = B 
               | NotB
-- etc.

Możesz stworzyć heterogeniczną listę o określonej kolejności dość łatwo, ale nie sądzę, że ten rodzaj polimorfizmu będzie ci tu służyć.


0
2017-09-24 20:16



Karty mogą być bezbarwne w Magic. Niezależnie od praktyczności mojego pierwotnego pytania, nadal byłbym zafascynowany techniką pracy, aby dowiedzieć się, jak to się robi. Chociaż teraz myślę, że coś w rodzaju klasy napisanej w taki sposób, jak mógłby działać bezpieczny dla typów printf w Haskell, chociaż nie byłbym w stanie wypróbować takiego kodu dzisiaj. - Thomas Eding


(Nie jest to odpowiedź na twoje pytanie, ale mam nadzieję, że rozwiązanie twojego problemu!)

Poszedłbym z najgłupszą rzeczą, która mogłaby działać:

is :: Card -> Color -> Bool
is card col = col `elem` (viewColors card) -- can be optimized to use the proper elem!

i wtedy

foo :: Card -> String
foo c
    | c `is` B && c `is` W = "card is black and white"
    | c `is` R || c `is` G = "card is red or green"
    | otherwise = "whatever"

Jeśli przeliterowanie całej listy w celu sprawdzenia, czy karta ma wszystkie 5 kolorów jest zbyt długie, można zdefiniować dodatkowe kombinatory, takie jak

hasColors :: Card -> [Color] -> Bool
hasColors card = all (`elem` (viewColors card))

Czy istnieje powód, dla którego nie jest to dopuszczalne?


0
2017-09-25 11:40



Głównym powodem, dla którego nie używam osłon, jest często to, że zdecydowanie preferuję przypadki wyrażeń nad dopasowaniem wzorców do wielu definicji. Używanie strażników jest denerwujące w tych przypadkach (nie gra słów przeznaczonych) w tym myślę, że pisanie case () of _ | x == 1 -> 1; _ | x == 2 -> 2 ; ... jest brzydki (zrobiony, gdy zagnieżdżony w "rzeczywistych" wzorach dopasowywania wzorca oczywiście). Powiedziałem, że po prostu czytałem o rozszerzeniu MultiWayIf, które zniszczyłoby ten rodzaj kodu. - Thomas Eding