Problem
Rozważ następujący problem projektowy w Haskell. Mam prosty, symboliczny EDSL, w którym chcę wyrażać zmienne i wyrażenia ogólne (wielomiany wielomianowe), takie jak x^2 * y + 2*z + 1
. Ponadto chcę wyrazić pewne równania symboliczne zamiast wyrażeń, powiedzmy x^2 + 1 = 1
, a także definicji , takich jak x := 2*y - 2
.
Celem jest:
- Mają osobny typ dla zmiennych i wyrażeń ogólnych - niektóre funkcje mogą być stosowane do zmiennych, a nie wyrażeń złożonych. Na przykład operator definicji
:=
może być typu(:=) :: Variable -> Expression -> Definition
i przekazanie złożonego wyrażenia jako parametru po lewej stronie nie powinno być możliwe (chociaż powinno być możliwe przekazanie zmiennej jako parametru po prawej stronie, bez jawnego rzutowania ) . - Mają wyrażenia na przykład
Num
, aby można było promować dosłowne liczby całkowite do wyrażeń i używać wygodnej notacji do typowych operacji algebraicznych, takich jak dodawanie lub mnożenie, bez wprowadzania niektórych pomocniczych operatorów opakowujących.
Innymi słowy, chciałbym mieć niejawny i statyczny typ rzutowania (przymusu) zmiennych na wyrażenia. Teraz wiem, że jako takie nie ma w Haskell rzutów typu niejawnego. Niemniej jednak niektóre koncepcje programowania obiektowego (w tym przypadku proste dziedziczenie) są wyrażalne w systemie typów Haskell, z rozszerzeniami językowymi lub bez nich. Jak mogłem spełnić oba powyższe punkty, zachowując lekką składnię? Czy to w ogóle możliwe?
Dyskusja
Oczywiste jest, że głównym problemem jest tutaj Num
ograniczenie typu, np
(+) :: Num a => a -> a -> a
Zasadniczo możliwe jest napisanie jednego (uogólnionego) algebraicznego typu danych zarówno dla zmiennych, jak i wyrażeń. Następnie można by napisać :=
w taki sposób, że wyrażenie po lewej stronie jest dyskryminowane i akceptowany jest tylko konstruktor zmiennej, z innym błędem wykonania. Nie jest to jednak czyste, statyczne (tj. Czas kompilacji) rozwiązanie ...
Przykład
Idealnie chciałbym uzyskać lekką składnię, taką jak
computation = do
x <- variable
t <- variable
t |:=| x^2 - 1
solve (t |==| 0)
W szczególności chcę zabronić notacji,
t + 1 |:=| x^2 - 1
ponieważ odtąd :=
powinna zawierać definicję zmiennej, a nie całe wyrażenie po lewej stronie.
class FromVar e
metody zfromVar :: Variable -> e
i podać instancje dla,Expression
iVariable
wtedy twoje zmienne mają typy polimorficznex :: FromVar e => e
itp. Nie testowałem, jak dobrze to działa, ponieważ jestem teraz na telefonie.FromVar
rodzaj czcionki byłby pomocny. Chcę uniknąć jawnych rzutów, zachowującExpr
instancjęNum
. Zredagowałem pytanie, dodając przykład notacji, którą chciałbym osiągnąć.Odpowiedzi:
Aby wykorzystać polimorfizm zamiast podtypu (ponieważ to wszystko, co masz w Haskell), nie myśl, że „zmienna jest wyrażeniem”, ale „zarówno zmienne, jak i wyrażenia mają pewne wspólne operacje”. Te operacje można umieścić w klasie typu:
Następnie zamiast rzucać rzeczy, uczyń je polimorficznymi. Jeśli tak
v :: forall e. HasVar e => e
, możesz go użyć zarówno jako wyrażenia, jak i zmiennej.Szkielet, aby wykonać kod poniżej, sprawdź typ: https://gist.github.com/Lysxia/da30abac357deb7981412f1faf0d2103
źródło
V
. Początkowo nie tego chciałem, ale być może byłem zbyt szybki, aby to odrzucić ... Prawdopodobnie nie mogę pozbyć się nieprzezroczystościV
. W powiązanej notatce, jak mogę utworzyć instancjęV (forall e . HasVar e => e)
? W Coq używałbym obliczeń typu i dopasowywania wzorów dla typu indukcyjnego, ale nie jest jasne, jak to osiągnąć w Haskell.w :: Variable
jakoś i zastosowaćfromVar
do niego:variable = (\w -> V (fromVar w)) <$> (_TODO_ :: Solver Variable)
.V
można tego uniknąć za pomocą impredykatywnych typów, ale nadal jest to PWT. Lub możemyvariable
podjąć kontynuację z polimorficznym argumentem jawnie zamiast pośrednio przez(>>=)
.