Interpretierte Arithmetik

9

Eine wenig bekannte Tatsache ist, dass Haskell eine dynamisch typisierte interpretierte Sprache wird, wenn Sie genügend Spracherweiterungen (ghc) aktivieren! Das folgende Programm implementiert beispielsweise das Hinzufügen.

{-# 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)

Das sieht nicht mehr wirklich nach Haskell aus. Zum einen operieren wir nicht über Objekte, sondern über Typen. Jede Nummer ist ein eigener Typ. Anstelle von Funktionen haben wir Typklassen. Die funktionalen Abhängigkeiten ermöglichen es uns, sie als Funktionen zwischen Typen zu verwenden.

Wie rufen wir unseren Code auf? Wir benutzen eine andere Klasse

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

Dies setzt den Typ testauf den Typ 4 + 3. Wenn wir dies in ghci öffnen, werden wir feststellen, dass testes sich tatsächlich um Typ 7 handelt:

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

Aufgabe

Ich möchte, dass Sie eine Klasse implementieren, die zwei Peano-Ziffern (nicht negative Ganzzahlen) multipliziert. Die Peano-Ziffern werden im obigen Beispiel mit denselben Datentypen erstellt:

data Zero
data Succ a

Und Ihre Klasse wird auf die gleiche Weise wie oben bewertet. Sie können Ihre Klasse nach Belieben benennen.

Sie können beliebige GHC-Spracherweiterungen kostenlos für Bytes verwenden.

Testfälle

In diesen Testfällen wird davon ausgegangen, dass Ihre Klasse benannt Mist. Sie können sie auch anders benennen , wenn Sie möchten.

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

Ergebnisse

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

Lässt sich von der Eingabe des technischen Interviews inspirieren

Ad-hoc-Garf-Jäger
quelle
Sind Spracherweiterungen kostenlos? Wenn ja, welche?
Potato44
@ Potato44 Oh ja. Alle Spracherweiterungen sind kostenlos.
Ad-hoc-Garf-Jäger
1
Heh ... Dieser Beitrag scheint meme-y, obwohl es nicht ist.
Magic Octopus Urn

Antworten:

9

130 121 Bytes

-9 Bytes dank Ø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

Probieren Sie es online aus!

Dies definiert geschlossene Typfamilien für Addition (+)und Multiplikation (*). Anschließend wird eine Typklasse (#)definiert, die die (*)Typfamilie zusammen mit einer Gleichheitsbeschränkung verwendet, um von der Welt der Typfamilien in die Welt des Typklassenprologs zu konvertieren.

Potato44
quelle
3
Wenn Sie die Gleichungen tauschen, können Sie ersetzen Zerodurch z.
Ørjan Johansen
1
@ ØrjanJohansen Fertig. Ich speichere 9 Bytes für jemanden und 9 Bytes werden für mich gespeichert.
Potato44
Ich weiß nicht, wie man Typfamilien verwendet, aber vielleicht ist eine Funktion wie diese , die Sie nicht definieren müssen, +nützlich?
Lynn
@Lynn das kommt länger raus. TIO
Potato44
1
@WheatWizard Ich habe gerade festgestellt, dass der Code, den ich im Kommentar gepostet habe, weil er länger herauskam, im Wesentlichen die rekursive Version Ihrer Antwort ist.
Potato44
6

139 Bytes

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

Probieren Sie es online aus!

Definiert einen Typoperator *. Entspricht dem Prolog-Programm:

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 und Hat Wizard haben jeweils 9 Bytes gespeichert. Vielen Dank!

Lynn
quelle
Sie müssen Ihre Datendeklarationen nicht zu Ihrer Bytesumme zählen. Ich werde dies in der Frage klarer machen, wenn ich eine Chance bekomme
Ad-hoc-Garf-Jäger
Ich denke auch, dass Sie fstattdessen einen General verwenden können Succ.
Ad-hoc-Garf-Jäger
1
Sie können 9 Bytes sparen, indem Sie die Doppelpunkte entfernen.
Potato44
Ich denke, Hat Wizard hat auch 9 und nicht 6 gespeichert. Es gab drei Vorkommen von Succ.
Potato44
1

Familienversion, 115 Bytes

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

Probieren Sie es online aus!

Dies verwendet eine geschlossene Typfamilie wie Potato44 . Außer im Gegensatz zu der anderen Antwort verwende ich nur 1 Typfamilie.

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

Dies definiert einen Operator für drei Typen. Es implementiert im Wesentlichen (a*b)+c. Wann immer wir unser rechtes Argument zur Summe hinzufügen wollen, legen wir es stattdessen in den Akkumulator.

Dies verhindert, dass wir überhaupt definieren müssen (+). Technisch gesehen können Sie diese Familie verwenden, um das Hinzufügen zu implementieren

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

Klassenversion, 137 Bytes

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

Probieren Sie es online aus!

Diese Klassenversion verliert etwas an Boden gegenüber der Familienversion, ist jedoch immer noch kürzer als die kürzeste Klassenversion hier. Es verwendet den gleichen Ansatz wie meine Familienversion.

Ad-hoc-Garf-Jäger
quelle
Schön, ich sehe, dass Ihre Typfamilie a * b + c mathematisch implementiert. Ist diese Erwähnung von "Teilung" als "Ergänzung" gemeint?
Potato44
Übrigens, Sie verletzen gerade Ihre eigene Spezifikation. "Implementiere eine Klasse, die zwei Peano-Ziffern multipliziert" Was du derzeit hast, ist keine Klasse, aber es ist zufällig von Art Constraint. Sie sollten also entweder die Spezifikation aktualisieren oder zu dem Formular zurückkehren, das eine Klasse anstelle eines Typensynonyms verwendet. Wenn ich das
Typensynonym verwenden würde,
@ Potato44 Ich hatte den Eindruck, dass eine Klasse nur etwas mit einer Art ist, die zu einer Kontraint führt. Vielleicht lag das an mangelnder Klarheit in der Frage. Ich werde dann auf meine Antwort zurückkommen.
Ad-hoc-Garf Hunter