Um fato pouco conhecido é que, se você ativar extensões de idioma suficientes (ghc), Haskell se tornará uma linguagem interpretada de tipo dinâmico! Por exemplo, o programa a seguir implementa a adição.

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

Isso realmente não se parece mais com Haskell. Por um lado, em vez de operar sobre objetos, operamos sobre tipos. Cada número é do seu próprio tipo. Em vez de funções, temos classes de tipos. As dependências funcionais nos permitem usá-las como funções entre tipos.

Então, como invocamos nosso código? Nós usamos outra classe

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

Isso define o tipo de testcomo o tipo 4 + 3. Se abrirmos isso em ghci, descobriremos que testé realmente do tipo 7:

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

Tarefa

Quero que você implemente uma classe que multiplique dois números Peano (números inteiros não negativos). Os números do Peano serão construídos usando os mesmos tipos de dados no exemplo acima:

data Zero
data Succ a

E sua turma será avaliada da mesma maneira que acima. Você pode nomear sua classe como desejar.

Você pode usar as extensões de idioma ghc que desejar, sem nenhum custo para bytes.

Casos de teste

Esses casos de teste assumem que sua classe é nomeada M; você pode nomear outra coisa, se desejar.

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

Inspira-se em Digitando a entrevista técnica

130 121 bytes

^{-9 bytes graças 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

Experimente online!

Isso define famílias de tipos fechados para adição (+)e multiplicação (*). Em seguida, (#)é definida uma classe de tipo que usa a (*)família de tipos junto com uma restrição de igualdade para converter do mundo das famílias de tipos para o mundo do prólogo da classe de tipos.

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

Experimente online!

Define um operador de tipo *. Equivalente ao 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 e Hat Wizard salvaram 9 bytes cada. Obrigado!

Versão da família, 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

Experimente online!

Isto é usa uma família de tipo fechado como potato44's . Exceto ao contrário da outra resposta, eu uso apenas um tipo de família.

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

Isso define um operador em três tipos. É essencialmente implementado (a*b)+c. Sempre que queremos adicionar o argumento da mão direita ao total, o colocamos no acumulador.

Isso nos impede de precisar definir (+). Tecnicamente, você pode usar essa família para implementar a adição fazendo

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

Versão de classe, 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

Experimente online!

Essa versão de classe perde terreno para a versão de família, porém ainda é mais curta que a versão de classe mais curta aqui. Ele usa a mesma abordagem da versão da minha família.