Aritmatika yang ditafsirkan

9

Fakta kecil yang diketahui adalah bahwa jika Anda mengaktifkan ekstensi bahasa yang cukup (ghc) Haskell menjadi bahasa yang ditafsirkan secara diketik secara dinamis! Misalnya program berikut mengimplementasikan penambahan.

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

Ini tidak terlihat seperti Haskell lagi. Untuk satu alih-alih mengoperasikan lebih dari objek, kami mengoperasikan lebih dari jenis. Setiap angka adalah jenisnya sendiri. Alih-alih fungsi kita memiliki kelas tipe. Ketergantungan fungsional memungkinkan kita untuk menggunakannya sebagai fungsi antar tipe.

Jadi bagaimana kita memanggil kode kita? Kami menggunakan kelas lain

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

Ini menetapkan tipe testke tipe 4 + 3. Jika kita membuka ini dalam ghci kita akan menemukan bahwa testmemang dari tipe 7:

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

Tugas

Saya ingin Anda menerapkan kelas yang mengalikan dua angka Peano (bilangan bulat non-negatif). Angka-angka Peano akan dibangun menggunakan tipe data yang sama dalam contoh di atas:

data Zero
data Succ a

Dan kelas Anda akan dievaluasi dengan cara yang sama seperti di atas juga. Anda dapat memberi nama kelas Anda apa pun yang Anda inginkan.

Anda dapat menggunakan ekstensi bahasa ghc apa pun yang Anda inginkan tanpa biaya ke byte.

Uji Kasus

Kasing uji ini menganggap kelas Anda bernama M, Anda dapat menamainya dengan nama lain jika Anda mau.

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

Hasil

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

Dapatkan inspirasi dari Mengetik wawancara teknis

Ad Hoc Garf Hunter
sumber
Apakah ekstensi bahasa gratis? Kalau begitu yang mana?
Potato44
@ Potato44 Oh ya. Semua ekstensi bahasa gratis.
Ad Hoc Garf Hunter
1
Heh ... Posting ini sepertinya meme-y meskipun tidak.
Magic Gurita Guci

Jawaban:

9

130 121 byte

-9 byte berkat Ø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

Cobalah online!

Ini mendefinisikan keluarga tipe tertutup untuk penambahan (+)dan perkalian (*). Kemudian kelas tipe (#)didefinisikan yang menggunakan (*)keluarga tipe bersama dengan batasan kesetaraan untuk mengkonversi dari dunia tipe familes ke dunia prolog typeclass.

Kentang44
sumber
3
Jika Anda menukar persamaan, Anda bisa menggantinya Zerodengan z.
Ørjan Johansen
1
@ ØrjanJohansen Selesai. Saya menyimpan 9 byte untuk seseorang dan 9 byte disimpan untuk saya.
Potato44
Saya tidak tahu cara menggunakan keluarga tipe, tapi mungkin fungsi seperti ini sehingga Anda tidak perlu mendefinisikan +berguna?
Lynn
@ Lynn yang akhirnya keluar lebih lama. TIO
Potato44
1
@WheatWizard Saya baru menyadari bahwa kode yang saya posting di komentar karena keluar lebih lama pada dasarnya adalah versi rekursif ekor jawaban Anda.
Potato44
6

139 byte

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

Cobalah online!

Menentukan operator tipe *. Setara dengan program 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 dan Hat Wizard masing-masing menyimpan 9 byte. Terima kasih!

Lynn
sumber
Anda tidak perlu menghitung deklarasi data ke total byte Anda. AKU AKAN membuat ini lebih jelas dalam pertanyaan ketika saya mendapatkan kesempatan
Ad Hoc Garf Hunter
Juga saya pikir Anda bisa menggunakan jenderal fbukannya Succ.
Ad Hoc Garf Hunter
1
Anda dapat menghemat 9 byte dengan membuang titik dua.
Potato44
Saya pikir Hat Wizard juga menyelamatkan 9, bukan 6. Ada tiga kejadian Succ.
Potato44
1

Versi Keluarga, 115 byte

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

Cobalah online!

Ini menggunakan keluarga tipe tertutup seperti kentang44 . Kecuali tidak seperti jawaban lain saya hanya menggunakan 1 jenis keluarga.

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

Ini mendefinisikan operator pada tiga jenis. Ini pada dasarnya mengimplementasikan (a*b)+c. Setiap kali kita ingin menambahkan argumen tangan kanan kita ke total kita malah memasukkannya ke dalam akumulator.

Ini mencegah kita dari perlu mendefinisikan (+)sama sekali. Secara teknis Anda dapat menggunakan keluarga ini untuk mengimplementasikan penambahan dengan melakukan

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

Versi Kelas, 137 byte

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

Cobalah online!

Versi kelas ini kehilangan beberapa alasan untuk versi keluarga, namun masih lebih pendek dari versi kelas terpendek di sini. Ini menggunakan pendekatan yang sama dengan versi keluarga saya.

Ad Hoc Garf Hunter
sumber
Bagus, saya melihat bahwa keluarga tipe Anda secara matematis menerapkan * b + c. Apakah penyebutan "pembagian" dimaksudkan sebagai "penambahan"?
Potato44
Tapi, Anda melanggar spec Anda sendiri saat ini. "mengimplementasikan kelas yang mengalikan dua angka Peano" Apa yang Anda miliki saat ini bukan kelas, itu memang sejenis Constraint. Jadi, Anda harus memperbarui spesifikasi atau kembali ke formulir yang menggunakan kelas alih-alih jenis sinonim. Jika saya menggunakan tipe sinonim, saya bisa mendapatkan jawaban saya hingga 96 byte, jadi saya menghemat satu byte lebih banyak daripada Anda
Potato44
@ Potato44 Saya mendapat kesan bahwa sebuah kelas hanyalah sesuatu dengan jenis yang menghasilkan suatu pengaduan. Mungkin itu karena kurangnya kejelasan dalam pertanyaan itu. Saya akan kembali ke 115 jawaban saya kemudian.
Ad Hoc Garf Hunter