Интерпретируемая арифметика

9

Малоизвестный факт: если вы включите достаточное количество расширений языка (ghc), Haskell станет интерпретируемым языком с динамической типизацией! Например, следующая программа реализует сложение.

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

Это больше не похоже на Haskell. Для одного вместо того, чтобы работать над объектами, мы работаем над типами. Каждый номер - это его собственный тип. Вместо функций у нас есть классы типов. Функциональные зависимости позволяют нам использовать их как функции между типами.

Итак, как мы можем вызвать наш код? Мы используем другой класс

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

Это устанавливает тип testдля типа 4 + 3. Если мы откроем это в ghci, мы обнаружим, что testон действительно имеет тип 7:

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

задача

Я хочу, чтобы вы реализовали класс, который умножает две цифры Пеано (неотрицательные целые числа). Числа Пеано будут построены с использованием тех же типов данных в примере выше:

data Zero
data Succ a

И ваш класс будет оцениваться так же, как и выше. Вы можете назвать свой класс как хотите.

Вы можете использовать любые расширения языка GHC, которые вы хотите, бесплатно для байтов.

Тестовые случаи

В этих тестах предполагается, что ваш класс назван M, вы можете назвать его как-нибудь еще, если хотите.

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

Результаты

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

Черпает вдохновение в наборе технических интервью

Специальный охотник за гарфами
источник
Бесплатные языковые расширения? Если да, то какие?
Potato44
@ Potato44 О да. Все языковые расширения бесплатны.
Специальный охотник за
1
Хех ... Этот пост кажется мне мем, хотя это не так.
Волшебная Урна Осьминога

Ответы:

9

130 121 байт

-9 байт благодаря Орджану Йохансену

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

Попробуйте онлайн!

Это определяет семейства закрытых типов для сложения (+)и умножения (*). Затем определяется класс типов, (#)который использует семейство (*)типов вместе с ограничением равенства для преобразования из мира семейств типов в мир пролога класса типов.

Potato44
источник
3
Если вы меняете уравнения, вы можете заменить Zeroна z.
Орджан Йохансен
1
@ ØrjanJohansen Готово. Я сохраняю 9 байтов для кого-то и 9 байтов для меня.
Potato44
Я не знаю , как использовать семьи типа, но , возможно, функция , как это так , что вам не нужно , чтобы определить +это полезно?
Линн
@ Линн, который заканчивает тем, что выходил дольше. TIO
Potato44
1
@WheatWizard Я только что понял, что код, который я разместил в комментарии, потому что он вышел длиннее, по сути является хвостовой рекурсивной версией вашего ответа.
Potato44
6

139 байт

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

Попробуйте онлайн!

Определяет оператор типа *. Эквивалент программы Пролог:

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 и Hat Wizard сохранили по 9 байт каждый. Спасибо!

Линн
источник
Вам не нужно считать ваши объявления данных до вашего общего байта. Я проясню этот вопрос, когда у меня появится шанс
Ad Hoc Garf Hunter
Также я думаю, что вы можете использовать общее fвместо Succ.
Специальный охотник за
1
Вы можете сохранить 9 байтов, исключив двоеточия.
Potato44
Я думаю, что Hat Wizard также сохранил 9, а не 6. Было три случая Succ.
Potato44
1

Семейная версия, 115 байт

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

Попробуйте онлайн!

Это использует семейство закрытых типов, как potato44 . Кроме в отличие от другого ответа я использую только 1 тип семейства.

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

Это определяет оператор трех типов. Это по существу реализует (a*b)+c. Всякий раз, когда мы хотим добавить наш аргумент правой руки к итогу, мы вместо этого помещаем его в накопитель.

Это мешает нам (+)вообще определять . Технически вы можете использовать это семейство для реализации сложения, выполнив

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

Класс-версия, 137 байт

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

Попробуйте онлайн!

Эта версия класса немного уступает семейной версии, однако она все еще короче, чем самая короткая версия класса. Он использует тот же подход, что и моя семейная версия.

Специальный охотник за гарфами
источник
Хорошо, я вижу, что ваше семейство типов математически реализует * b + c. Это упоминание о «делении» означает «дополнение»?
Potato44
Кстати, вы случайно нарушаете свои собственные спецификации в данный момент. "реализовать класс, который умножает две цифры Пеано". То, что у вас есть в настоящее время, не является классом, Constraintхотя оно действительно является полезным. Поэтому вы должны либо обновить спецификацию, либо вернуться обратно в форму, которая использует класс вместо синонима типа. Если бы я использовал синоним типа, я мог бы получить свой ответ до 96 байтов, так что это
спасло
@ Potato44 У меня сложилось впечатление, что урок - это что-то вроде того, что приводит к противопоказанию. Возможно, это было связано с отсутствием ясности в этом вопросе. Я вернусь к своему ответу 115 тогда.
Ad Hoc