Arithmétique interprétée

9

Un fait peu connu est que si vous activez suffisamment d'extensions de langage (ghc), Haskell devient un langage interprété à typage dynamique! Par exemple, le programme suivant implémente l'addition.

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

Cela ne ressemble plus vraiment à Haskell. Pour l'un au lieu d'opérer sur des objets, nous opérons sur des types. Chaque numéro est son propre type. Au lieu de fonctions, nous avons des classes de types. Les dépendances fonctionnelles nous permettent de les utiliser comme fonctions entre types.

Alors, comment invoquer notre code? Nous utilisons une autre classe

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

Cela définit le type de testsur le type 4 + 3. Si nous ouvrons cela dans ghci, nous trouverons qu'il tests'agit bien du type 7:

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

Tâche

Je veux que vous implémentiez une classe qui multiplie deux nombres Peano (entiers non négatifs). Les chiffres Peano seront construits en utilisant les mêmes types de données dans l'exemple ci-dessus:

data Zero
data Succ a

Et votre classe sera également évaluée de la même manière que ci-dessus. Vous pouvez nommer votre classe comme vous le souhaitez.

Vous pouvez utiliser toutes les extensions de langage ghc que vous souhaitez sans frais en octets.

Cas de test

Ces cas de test supposent que votre classe est nommée M, vous pouvez la nommer autrement si vous le souhaitez.

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

Résultats

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

S'inspire de Taper l'entretien technique

Ad Hoc Garf Hunter
la source
Les extensions linguistiques sont-elles gratuites? Si oui, lesquels?
Potato44
@ Potato44 Oh ouais. Toutes les extensions linguistiques sont gratuites.
Ad Hoc Garf Hunter
1
Hé ... Ce post semble meme-y même s'il ne l'est pas.
Urne de poulpe magique

Réponses:

9

130 121 octets

-9 octets grâce à Ø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

Essayez-le en ligne!

Ceci définit des familles de types fermées pour l'addition (+)et la multiplication (*). Ensuite, une classe de type (#)est définie qui utilise le(*) famille de types avec une contrainte d'égalité pour convertir du monde des familles de types au monde des prologues de classe de types.

Pomme de terre44
la source
3
Si vous échangez les équations, vous pouvez les remplacer Zeropar z.
Ørjan Johansen
1
@ ØrjanJohansen Terminé. J'économise 9 octets pour quelqu'un et 9 octets pour moi.
Potato44
Je ne sais pas comment utiliser les familles de types, mais peut-être qu'une fonction comme celle-ci, que vous n'avez pas besoin de définir, +est utile?
Lynn
@Lynn qui finit par sortir plus longtemps. TIO
Potato44
1
@WheatWizard Je viens de réaliser que le code que j'ai publié dans le commentaire car il est sorti plus longtemps est essentiellement la version récursive de votre réponse.
Potato44
6

139 octets

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

Essayez-le en ligne!

Définit un opérateur de type *. Equivalent au programme 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 et Hat Wizard ont enregistré 9 octets chacun. Merci!

Lynn
la source
Vous n'avez pas besoin de compter vos déclarations de données dans votre total d'octets. Je vais clarifier ce point dans la question lorsque j'en
aurai l'
Je pense aussi que vous pouvez utiliser un général fau lieu de Succ.
Ad Hoc Garf Hunter
1
Vous pouvez économiser 9 octets en abandonnant les deux-points.
Potato44
Je pense que Hat Wizard a également sauvé 9, pas 6. Il y avait trois occurrences de Succ.
Potato44
1

Version familiale, 115 octets

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

Essayez-le en ligne!

Il s'agit d'une famille de type fermée comme celle de potato44 . Sauf contrairement à l'autre réponse, je n'utilise qu'une seule famille de types.

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

Cela définit un opérateur sur trois types. Il implémente essentiellement (a*b)+c. Chaque fois que nous voulons ajouter notre argument de droite au total, nous le mettons à la place dans l'accumulateur.

Cela nous empêche d'avoir à définir (+)du tout. Techniquement, vous pouvez utiliser cette famille pour implémenter l'addition en faisant

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

Version de classe, 137 octets

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

Essayez-le en ligne!

Cette version de classe perd du terrain par rapport à la version familiale, mais elle est toujours plus courte que la version de classe la plus courte ici. Il utilise la même approche que ma version familiale.

Ad Hoc Garf Hunter
la source
Bien, je vois que votre famille de types implémente mathématiquement a * b + c. Cette mention de «division» est-elle censée être «addition»?
Potato44
btw, vous êtes en train de violer vos propres spécifications en ce moment. "implémentez une classe qui multiplie deux nombres Peano" Ce que vous avez actuellement n'est pas une classe, mais il se trouve qu'il est de nature Constraint. Vous devez donc mettre à jour la spécification ou revenir au formulaire qui utilise une classe au lieu d'un synonyme de type. Si je devais utiliser le synonyme de type, je pourrais obtenir ma réponse à 96 octets, donc cela me fait gagner un octet de plus que vous
Potato44
@ Potato44 J'avais l'impression qu'une classe était juste quelque chose avec un genre qui se traduisait par une contraint. Cela est peut-être dû à un manque de clarté de la question. Je reviendrai alors à ma 115 réponse.
Ad Hoc Garf Hunter