Interpretowana arytmetyka

9

Mało znanym faktem jest to, że jeśli włączysz wystarczającą liczbę rozszerzeń języka (ghc), Haskell stanie się dynamicznie pisanym językiem interpretowanym! Na przykład poniższy program implementuje dodawanie.

{-# Language MultiParamTypeClasses, FunctionalDependencies, FlexibleInstances, UndecidableInstances #-}

data Zero
data Succ a

class Add a b c | a b -> c
instance Add Zero a a
instance (Add a b c) => Add (Succ a) b (Succ c)

To już tak naprawdę nie wygląda jak Haskell. Dla jednego zamiast działania na obiektach, działamy na typach. Każda liczba ma własny typ. Zamiast funkcji mamy klasy typów. Zależności funkcjonalne pozwalają nam wykorzystywać je jako funkcje między typami.

Jak więc wywołać nasz kod? Używamy innej klasy

class Test a | -> a
 where test :: a
instance (Add (Succ (Succ (Succ (Succ Zero)))) (Succ (Succ (Succ Zero))) a)
  => Test a

To ustawia typ testna typ 4 + 3. Jeśli otworzymy to w ghci, okaże się, że testrzeczywiście jest to typ 7:

Ok, one module loaded.
*Main> :t test
test :: Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero))))))

Zadanie

Chcę, abyś zaimplementował klasę, która zwielokrotnia dwie liczby Peano (nieujemne liczby całkowite). Liczby Peano zostaną zbudowane przy użyciu tych samych typów danych w powyższym przykładzie:

data Zero
data Succ a

Twoja klasa będzie również oceniana w taki sam sposób jak powyżej. Możesz nazwać swoją klasę, jak chcesz.

Możesz używać dowolnych rozszerzeń języka GHC bez bajtów.

Przypadki testowe

Te przypadki testowe zakładają, że twoja klasa ma nazwę M, możesz nazwać ją inną nazwą, jeśli chcesz.

class Test1 a| ->a where test1::a
instance (M (Succ (Succ (Succ (Succ Zero)))) (Succ (Succ (Succ Zero))) a)=>Test1 a

class Test2 a| ->a where test2::a
instance (M Zero (Succ (Succ Zero)) a)=>Test2 a

class Test3 a| ->a where test3::a
instance (M (Succ (Succ (Succ (Succ Zero)))) (Succ Zero) a)=>Test3 a

class Test4 a| ->a where test4::a
instance (M (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))) (Succ (Succ (Succ Zero))) a)=>Test4 a

Wyniki

*Main> :t test1
test1
  :: Succ
       (Succ
          (Succ
             (Succ
                (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))))))
*Main> :t test2
test2 :: Zero
*Main> :t test3
test3 :: Succ (Succ (Succ (Succ Zero)))
*Main> :t test4
test4
  :: Succ
       (Succ
          (Succ
             (Succ
                (Succ
                   (Succ
                      (Succ
                         (Succ
                            (Succ
                               (Succ
                                  (Succ
                                     (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))))))))))))

Inspiracje czerpie z pisania wywiadu technicznego

Ad Hoc Garf Hunter
źródło
Czy rozszerzenia językowe są bezpłatne? Jeśli tak, które?
Potato44
@ Potato44 O tak. Wszystkie rozszerzenia językowe są bezpłatne.
Ad Hoc Garf Hunter
1
Heh ... Ten post wydaje się memowy, nawet jeśli nie jest.
Magic Octopus Urn

Odpowiedzi:

9

130 121 bajtów

-9 bajtów dzięki Ørjan Johansen

type family a+b where s a+b=a+s b;z+b=b
type family a*b where s a*b=a*b+b;z*b=z
class(a#b)c|a b->c
instance a*b~c=>(a#b)c

Wypróbuj online!

Definiuje to rodziny zamkniętych typów dla dodawania (+)i mnożenia (*). Następnie (#)definiowana jest klasa typów, która wykorzystuje (*)rodzinę typów wraz z ograniczeniem równości do konwersji ze świata famili typów na świat prologów klasowych.

Ziemniak44
źródło
3
Jeśli zamienić równań, można zastąpić Zeroprzez z.
Ørjan Johansen
1
@ ØrjanJohansen Gotowe. Zapisuję dla kogoś 9 bajtów, a dla mnie zapisano 9 bajtów.
Potato44
Nie wiem, jak korzystać z rodzin typ, ale może to funkcja jak to więc nie trzeba definiować +jest przydatna?
Lynn
@ Lynn, który kończy się wychodzić dłużej. TIO
Potato44
1
@WheatWizard Właśnie zdałem sobie sprawę, że kod, który zamieściłem w komentarzu, ponieważ wyszedł dłużej, jest zasadniczo rekurencyjną wersją twojej odpowiedzi.
Ziemniak44
6

139 bajtów

class(a+b)c|a b->c;instance(Zero+a)a;instance(a+b)c=>(s a+b)(s c)
class(a*b)c|a b->c;instance(Zero*a)Zero;instance((a*b)c,(b+c)d)=>(s a*b)d

Wypróbuj online!

Definiuje operator typu *. Odpowiednik programu Prolog:

plus(0, A, A).
plus(s(A), B, s(C)) :- plus(A, B, C).
mult(0, _, 0).
mult(s(A), B, D) :- mult(A, B, C), plus(B, C, D).

Potato44 i Hat Wizard zapisały po 9 bajtów. Dzięki!

Lynn
źródło
Nie musisz liczyć deklaracji danych do całkowitej liczby bajtów. Wyjaśnię to jeszcze bardziej w pytaniu, gdy będę miał szansę
Ad Hoc Garf Hunter,
Myślę też, że możesz użyć generała fzamiast Succ.
Ad Hoc Garf Hunter,
1
Możesz zaoszczędzić 9 bajtów, porzucając dwukropki.
Potato44
Myślę, że Kapelusznik Uratował także 9, a nie 6. Wystąpiły trzy przypadki Succ.
Potato44
1

Wersja rodzinna, 115 bajtów

type family(a%b)c where(a%b)(s c)=s((a%b)c);(s a%b)z=(a%b)b;(z%b)z=z
class(a#b)c|a b->c
instance(a%b)Zero~c=>(a#b)c

Wypróbuj online!

Jest to rodzina zamknięta, taka jak potato44 . Z wyjątkiem, w przeciwieństwie do innych odpowiedzi, używam tylko rodziny 1 typu.

type family(a%b)c where
  -- If the accumulator is Succ c:
  -- the answer is Succ of the answer if the accumulator were c
  (a%b)(s c)=s((a%b)c)
  -- If the left hand argument is Succ a, and the right hand is b
  -- the result is the result if the left were a and the accumulator were b
  (s a%b)z=(a%b)b
  -- If the left hand argument is zero
  -- the result is zero
  (z%b)z=z

To definiuje operatora dla trzech typów. Zasadniczo implementuje (a*b)+c. Ilekroć chcemy dodać nasz argument prawej ręki do sumy, zamiast tego umieszczamy go w akumulatorze.

To uniemożliwia nam (+)w ogóle zdefiniowanie . Technicznie możesz użyć tej rodziny do implementacji dodawania poprzez działanie

class Add a b c | a b -> c
instance (Succ Zero % a) b ~ c => Add a b c

Wersja klasy, 137 bajtów

class(a#b)c d|a b c->d
instance(a#b)c d=>(a#b)(f c)(f d)
instance(a#b)b d=>(f a#b)Zero d
instance(Zero#a)Zero Zero
type(a*b)c=(a#b)Zero c

Wypróbuj online!

Ta wersja klasowa traci trochę podstaw do wersji rodzinnej, jednak wciąż jest krótsza niż najkrótsza wersja klasowa tutaj. Wykorzystuje to samo podejście, co moja wersja rodzinna.

Ad Hoc Garf Hunter
źródło
Fajnie, widzę, że twoja rodzina typów matematycznie implementuje * b + c. Czy ta wzmianka o „podziale” ma być „dodatkiem”?
Potato44
tak przy okazji, w tej chwili naruszasz własną specyfikację. „zaimplementuj klasę, która zwielokrotnia dwie cyfry Peano”. To, co obecnie posiadasz, nie jest klasą, ale okazuje się, że jest to coś miłego Constraint. Powinieneś więc zaktualizować specyfikację lub powrócić do formularza, który używa klasy zamiast synonimu typu. Gdybym użył synonimu typu, mógłbym uzyskać odpowiedź do 96 bajtów, więc oszczędza mi to jeszcze jeden bajt
Potato44,
@ Potato44 Miałem wrażenie, że klasa była po prostu czymś w rodzaju przeciwności. Być może wynikało to z niejasności pytania. Wrócę do mojej 115 odpowiedzi.
Ad Hoc Garf Hunter