Aritmética interpretada

9

Un hecho poco conocido es que si activa suficientes extensiones de idioma (ghc), ¡Haskell se convierte en un lenguaje interpretado de tipo dinámico! Por ejemplo, el siguiente programa implementa la suma.

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

Esto ya no se parece a Haskell. Para uno en lugar de operar sobre objetos, operamos sobre tipos. Cada número es su propio tipo. En lugar de funciones tenemos clases de tipo. Las dependencias funcionales nos permiten usarlas como funciones entre tipos.

Entonces, ¿cómo invocamos nuestro código? Usamos otra clase

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

Esto establece el tipo de testal tipo 4 + 3. Si abrimos esto en ghci, encontraremos que de testhecho es del tipo 7:

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

Tarea

Quiero que implementes una clase que multiplique dos números Peano (enteros no negativos). Los números de Peano se construirán utilizando los mismos tipos de datos en el ejemplo anterior:

data Zero
data Succ a

Y su clase será evaluada de la misma manera que arriba también. Puedes nombrar tu clase como quieras.

Puede usar cualquier extensión de idioma ghc que desee sin costo para los bytes.

Casos de prueba

Estos casos de prueba asumen que su clase se llama M, puede nombrarla de otra manera si lo desea.

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

Resultados

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

Se inspira en escribir la entrevista técnica

Ad Hoc Garf Hunter
fuente
¿Son gratis las extensiones de idioma? ¿De ser asi, cuales?
Papa44
@ Papa44 Oh, sí. Todas las extensiones de idioma son gratuitas.
Ad Hoc Garf Hunter
1
Je ... Esta publicación parece meme-a pesar de que no lo es.
Magic Octopus Urn

Respuestas:

9

130 121 bytes

-9 bytes gracias a Ø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

Pruébalo en línea!

Esto define familias de tipo cerrado para suma (+)y multiplicación (*). Luego, (#)se define una clase de tipo que usa la (*)familia de tipos junto con una restricción de igualdad para convertir del mundo de las familias de tipos al mundo del prólogo de la clase de tipos.

Papa44
fuente
3
Si intercambias las ecuaciones, puedes reemplazarlas Zeropor z.
Ørjan Johansen
1
@ ØrjanJohansen Hecho. Ahorro 9 bytes para alguien y 9 bytes se guardan para mí.
Papa44
No sé cómo usar familias de tipos, pero ¿quizás sea ​​útil una función como esta para que no necesite definirla +?
Lynn
@ Lynn que termina saliendo más tiempo. TIO
Papa44
1
@WheatWizard Me acabo de dar cuenta de que el código que publiqué en el comentario porque salió más tiempo es esencialmente la versión recursiva de tu respuesta.
Patata44
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

Pruébalo en línea!

Define un operador de tipo *. Equivalente al programa 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 y Hat Wizard guardaron 9 bytes cada uno. ¡Gracias!

Lynn
fuente
No necesita contar sus declaraciones de datos en el total de bytes. Dejaré esto más claro en la pregunta cuando tenga la oportunidad
Ad Hoc Garf Hunter
También creo que puedes usar un general en flugar de Succ.
Ad Hoc Garf Hunter
1
Puede guardar 9 bytes deshaciéndose de los dos puntos.
Papa44
Creo que Hat Wizard también salvó 9, no 6. Hubo tres ocurrencias de Succ.
Papa44
1

Versión familiar, 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

Pruébalo en línea!

Esto utiliza una familia de tipo cerrado como potato44's . Excepto a diferencia de la otra respuesta, uso solo 1 familia tipo.

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

Esto define un operador en tres tipos. Básicamente se implementa (a*b)+c. Siempre que queramos agregar nuestro argumento de la mano derecha al total, lo colocamos en el acumulador.

Esto nos impide tener que definir (+)en absoluto. Técnicamente, puede usar esta familia para implementar la suma haciendo

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

Versión de clase, 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

Pruébalo en línea!

Esta versión de clase pierde algo de terreno con la versión familiar, sin embargo, todavía es más corta que la versión de clase más corta aquí. Utiliza el mismo enfoque que mi versión familiar.

Ad Hoc Garf Hunter
fuente
Bien, veo que tu familia tipo está implementando matemáticamente a * b + c. ¿Esa mención de "división" significa "adición"?
Patata44
por cierto, estás violando tu propia especificación en este momento. "implementar una clase que multiplique dos números Peano" Lo que tienes actualmente no es una clase, sin embargo, es muy amable Constraint. Por lo tanto, debe actualizar la especificación o volver al formulario que utiliza una clase en lugar de un sinónimo de tipo. Si
tuviera
@ Potato44 Tenía la impresión de que una clase era simplemente algo con un tipo que resulta en una restricción. Quizás eso se debió a la falta de claridad en la pregunta. Volveré a mi respuesta 115 entonces.
Ad Hoc Garf Hunter