9
\$\begingroup\$

A little known fact is that if you turn on enough language extensions (ghc) Haskell becomes a dynamically typed interpreted language! For example the following program implements 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)

This doesn't really look like Haskell any more. For one instead of operating over objects, we operate over types. Each number is it's own type. Instead of functions we have type classes. The functional dependencies allows us to use them as functions between types.

So how do we invoke our code? We use another class

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

This sets the type of test to the type 4 + 3. If we open this up in ghci we will find that test is indeed of type 7:

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

Task

I want you to implement a class that multiplies two Peano numerals (non-negative integers). The Peano numerals will be constructed using the same data types in the example above:

data Zero
data Succ a

And your class will be evaluated in the same way as above as well. You may name your class whatever you wish.

You may use any ghc language extensions you want at no cost to bytes.

Test Cases

These test cases assume your class is named M, you can name it something else if you would like.

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

Results

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

Draws inspiration from Typing the technical interview

\$\endgroup\$
  • \$\begingroup\$ Are language extensions free? If so which ones? \$\endgroup\$ – Potato44 Jun 10 '18 at 13:15
  • \$\begingroup\$ @Potato44 Oh yeah. All language extensions are free. \$\endgroup\$ – Wheat Wizard Jun 10 '18 at 13:23
  • 1
    \$\begingroup\$ Heh... This post seems meme-y even though it's not. \$\endgroup\$ – Magic Octopus Urn Jun 12 '18 at 18:01
9
\$\begingroup\$

130 121 bytes

-9 bytes thanks to Ø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

Try it online!

This defines closed type families for addition (+) and multiplication (*). Then a type class (#) is defined that uses the (*) type family along with an equality constraint to convert from the world of type familes to the world of typeclass prolog.

\$\endgroup\$
  • 3
    \$\begingroup\$ If you swap the equations, you can replace Zero by z. \$\endgroup\$ – Ørjan Johansen Jun 10 '18 at 20:28
  • 1
    \$\begingroup\$ @ØrjanJohansen Done. I save 9 bytes for someone and 9 bytes is saved for me. \$\endgroup\$ – Potato44 Jun 10 '18 at 23:14
  • \$\begingroup\$ I don't know how to use type families, but maybe a function like this so you don't need to define + is useful? \$\endgroup\$ – Lynn Jun 11 '18 at 9:42
  • \$\begingroup\$ @Lynn that ends up coming out longer. TIO \$\endgroup\$ – Potato44 Jun 11 '18 at 10:53
6
\$\begingroup\$

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

Try it online!

Defines a type operator *. Equivalent to the Prolog program:

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 and Hat Wizard saved 9 bytes each. Thanks!

\$\endgroup\$
  • \$\begingroup\$ You don't need to count your data declarations to your byte total. I'LL make this clearer in the question when I get a chance \$\endgroup\$ – Wheat Wizard Jun 10 '18 at 15:52
  • \$\begingroup\$ Also I think you can use a general f instead of Succ. \$\endgroup\$ – Wheat Wizard Jun 10 '18 at 15:53
  • 1
    \$\begingroup\$ You can save 9 bytes by ditching the colons. \$\endgroup\$ – Potato44 Jun 10 '18 at 18:51
  • \$\begingroup\$ I think Hat Wizard also saved 9, not 6. There were three occurrences of Succ. \$\endgroup\$ – Potato44 Jun 10 '18 at 23:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.