Apakah mungkin untuk "memanggang dimensi menjadi tipe" di haskell?

Misalkan saya ingin menulis perpustakaan yang berhubungan dengan vektor dan matriks. Apakah mungkin untuk memanggang dimensi ke dalam jenis, sehingga operasi dimensi yang tidak kompatibel menghasilkan kesalahan pada waktu kompilasi?

Misalnya saya ingin tanda tangan dari produk titik menjadi sesuatu seperti

dotprod :: Num a, VecDim d => Vector a d -> Vector a d -> a

di mana dtipe berisi nilai integer tunggal (mewakili dimensi dari vektor-vektor ini).

Saya kira ini bisa dilakukan dengan mendefinisikan (dengan tangan) tipe terpisah untuk setiap integer, dan mengelompokkannya dalam tipe kelas yang disebut VecDim. Apakah ada mekanisme untuk "menghasilkan" jenis seperti itu?

Atau mungkin cara yang lebih baik / lebih sederhana untuk mencapai hal yang sama?

Untuk memperluas jawaban @ KarlBielefeldt, berikut adalah contoh lengkap tentang cara mengimplementasikan Vektor - daftar dengan jumlah elemen yang diketahui secara statis - di Haskell. Pegang topimu ...

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE ExistentialQuantification #-}
{-# LANGUAGE DeriveFoldable #-}
{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE DeriveTraversable #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE TypeFamilies #-}

import Prelude hiding (foldr, zipWith)
import qualified Prelude
import Data.Type.Equality
import Data.Foldable
import Data.Traversable

Seperti yang Anda lihat dari daftar panjang LANGUAGEarahan, ini hanya akan bekerja dengan versi terbaru GHC.

Kita membutuhkan cara untuk merepresentasikan panjang dalam sistem tipe. Menurut definisi, bilangan alami adalah nol ( Z) atau merupakan penerus beberapa bilangan alami lainnya ( S n). Jadi, misalnya, angka 3 akan ditulis S (S (S Z)).

data Nat = Z | S Nat

Dengan ekstensi DataKinds , datadeklarasi ini memperkenalkan jenis yang disebut Natdan dua tipe konstruktor yang disebut Sdan Z- dengan kata lain kita memiliki bilangan alami tipe-level . Perhatikan bahwa tipe Sdan Ztidak memiliki nilai anggota - hanya tipe *yang dihuni oleh nilai.

Sekarang kami memperkenalkan GADT yang mewakili vektor dengan panjang yang diketahui. Perhatikan jenis tanda tangan: Vecmembutuhkan jenis jenisNat (yaitu jenis Zatau a S) untuk mewakili panjangnya.

data Vec :: Nat -> * -> * where
    VNil :: Vec Z a
    VCons :: a -> Vec n a -> Vec (S n) a
deriving instance (Show a) => Show (Vec n a)
deriving instance Functor (Vec n)
deriving instance Foldable (Vec n)
deriving instance Traversable (Vec n)

Definisi vektor mirip dengan daftar tertaut, dengan beberapa informasi tingkat tipe tambahan tentang panjangnya. Vektor adalah salah satu VNil, dalam hal ini memiliki panjang Z(ero), atau itu adalah VConssel yang menambahkan item ke vektor lain, dalam hal ini panjangnya adalah satu lebih dari vektor lainnya ( S n). Perhatikan bahwa tidak ada argumen tipe konstruktor n. Ini hanya digunakan pada waktu kompilasi untuk melacak panjang, dan akan dihapus sebelum kompiler menghasilkan kode mesin.

Kami telah mendefinisikan jenis vektor yang membawa sekitar pengetahuan statis panjangnya. Mari kita tanyakan tipe beberapa Vecuntuk mengetahui bagaimana mereka bekerja:

ghci> :t (VCons 'a' (VCons 'b' VNil))
(VCons 'a' (VCons 'b' VNil)) :: Vec ('S ('S 'Z)) Char  -- (S (S Z)) means 2
ghci> :t (VCons 13 (VCons 11 (VCons 3 VNil)))
(VCons 13 (VCons 11 (VCons 3 VNil))) :: Num a => Vec ('S ('S ('S 'Z))) a  -- (S (S (S Z))) means 3

Produk titik dihasilkan seperti halnya untuk daftar:

-- note that the two Vec arguments are declared to have the same length
vap :: Vec n (a -> b) -> Vec n a -> Vec n b
vap VNil VNil = VNil
vap (VCons f fs) (VCons x xs) = VCons (f x) (vap fs xs)

zipWith :: (a -> b -> c) -> Vec n a -> Vec n b -> Vec n c
zipWith f xs ys = fmap f xs `vap` ys

dot :: Num a => Vec n a -> Vec n a -> a
dot xs ys = foldr (+) 0 $ zipWith (*) xs ys

vap, yang 'zippily' menerapkan vektor fungsi ke vektor argumen, bersifat Vecaplikatif <*>; Saya tidak memasukkannya ke dalam Applicativecontoh karena menjadi berantakan . Perhatikan juga bahwa saya menggunakan foldrinstance dari compiler-generate dari Foldable.

Mari kita coba:

ghci> let v1 = VCons 2 (VCons 1 VNil)
ghci> let v2 = VCons 4 (VCons 5 VNil)
ghci> v1 `dot` v2
13
ghci> let v3 = VCons 8 (VCons 6 (VCons 1 VNil))
ghci> v1 `dot` v3
<interactive>:20:10:
    Couldn't match type ‘'S 'Z’ with ‘'Z’
    Expected type: Vec ('S ('S 'Z)) a
      Actual type: Vec ('S ('S ('S 'Z))) a
    In the second argument of ‘dot’, namely ‘v3’
    In the expression: v1 `dot` v3

Besar! Anda mendapatkan kesalahan waktu kompilasi ketika Anda mencoba untuk dotvektor yang panjangnya tidak cocok.

Berikut adalah upaya pada fungsi untuk menggabungkan vektor bersama:

-- This won't compile because the type checker can't deduce the length of the returned vector
-- VNil +++ ys = ys
-- (VCons x xs) +++ ys = VCons x (concat xs ys)

Panjang vektor keluaran akan menjadi jumlah dari panjang dua vektor input. Kita perlu mengajari pemeriksa tipe cara menambahkan Nats bersama-sama. Untuk ini kami menggunakan fungsi tipe-level :

type family (n :: Nat) :+: (m :: Nat) :: Nat where
    Z :+: m = m
    (S n) :+: m = S (n :+: m)

type familyDeklarasi ini memperkenalkan fungsi pada tipe yang disebut :+:- dengan kata lain, itu adalah resep untuk pemeriksa tipe untuk menghitung jumlah dua bilangan alami. Itu didefinisikan secara rekursif - setiap kali operan kiri lebih besar dari Zero kita menambahkan satu ke output dan menguranginya dengan satu dalam panggilan rekursif. (Ini adalah latihan yang baik untuk menulis fungsi tipe yang mengalikan dua Nats.) Sekarang kita dapat membuat +++kompilasi:

infixr 5 +++
(+++) :: Vec n a -> Vec m a -> Vec (n :+: m) a
VNil +++ ys = ys
(VCons x xs) +++ ys = VCons x (concat xs ys)

Begini cara Anda menggunakannya:

ghci> VCons 1 (VCons 2 VNil) +++ VCons 3 (VCons 4 VNil)
VCons 1 (VCons 2 (VCons 3 (VCons 4 VNil)))

Sejauh ini sangat sederhana. Bagaimana kalau kita ingin melakukan kebalikan dari penggabungan dan membagi vektor menjadi dua? Panjang vektor keluaran tergantung pada nilai runtime argumen. Kami ingin menulis sesuatu seperti ini:

-- this won't work because there aren't any values of type `S` and `Z`
-- split :: (n :: Nat) -> Vec (n :+: m) a -> (Vec n a, Vec m a)

tapi sayangnya Haskell tidak akan membiarkan kita melakukan itu. Memungkinkan nilai dari nargumen untuk muncul dalam tipe kembali (ini biasa disebut fungsi tergantung atau jenis pi ) akan membutuhkan "full-spectrum" jenis tergantung, sedangkan DataKindshanya memberi kita dipromosikan jenis konstruktor. Dengan kata lain, ketik konstruktor Sdan Ztidak muncul pada tingkat nilai. Kita harus puas dengan nilai singleton untuk representasi run-time tertentu Nat. *

data Natty (n :: Nat) where
    Zy :: Natty Z  -- pronounced 'zed-y'
    Sy :: Natty n -> Natty (S n)  -- pronounced 'ess-y'
deriving instance Show (Natty n)

Untuk jenis yang diberikan n(dengan jenis Nat), tepat ada satu istilah jenis Natty n. Kita dapat menggunakan nilai singleton sebagai saksi run-time untuk n: belajar tentang a Nattymengajarkan kita tentang itu ndan sebaliknya.

split :: Natty n ->
         Vec (n :+: m) a ->  -- the input Vec has to be at least as long as the input Natty
         (Vec n a, Vec m a)
split Zy xs = (Nil, xs)
split (Sy n) (Cons x xs) = let (ys, zs) = split n xs
                           in (Cons x ys, zs)

Mari kita putar:

ghci> split (Sy (Sy Zy)) (VCons 1 (VCons 2 (VCons 3 VNil)))
(VCons 1 (VCons 2 VNil), VCons 3 VNil)
ghci> split (Sy (Sy Zy)) (VCons 3 VNil)
<interactive>:116:21:
    Couldn't match type ‘'S ('Z :+: m)’ with ‘'Z’
    Expected type: Vec ('S ('S 'Z) :+: m) a
      Actual type: Vec ('S 'Z) a
    Relevant bindings include
      it :: (Vec ('S ('S 'Z)) a, Vec m a) (bound at <interactive>:116:1)
    In the second argument of ‘split’, namely ‘(VCons 3 VNil)’
    In the expression: split (Sy (Sy Zy)) (VCons 3 VNil)

Pada contoh pertama, kami berhasil membagi vektor tiga elemen pada posisi 2; kemudian kami mendapat kesalahan ketik ketika kami mencoba untuk membagi vektor pada posisi melewati akhir. Lajang adalah teknik standar untuk membuat jenis bergantung pada nilai dalam Haskell.

_{* singletonsPerpustakaan berisi beberapa pembantu Template Haskell untuk menghasilkan nilai tunggal seperti Nattyuntuk Anda.}

Contoh terakhir. Bagaimana ketika Anda tidak tahu dimensi vektor Anda secara statis? Misalnya, bagaimana jika kita mencoba membangun vektor dari data run-time dalam bentuk daftar? Anda memerlukan jenis vektor untuk bergantung pada panjang daftar input. Dengan kata lain, kita tidak dapat menggunakan foldr VCons VNiluntuk membangun vektor karena jenis vektor keluaran berubah dengan setiap iterasi flip. Kita perlu merahasiakan panjang vektor dari kompiler.

data AVec a = forall n. AVec (Natty n) (Vec n a)
deriving instance (Show a) => Show (AVec a)

fromList :: [a] -> AVec a
fromList = Prelude.foldr cons nil
    where cons x (AVec n xs) = AVec (Sy n) (VCons x xs)
          nil = AVec Zy VNil

AVecadalah tipe eksistensial : variabel tipe ntidak muncul dalam tipe kembalinya AVeckonstruktor data. Kami menggunakannya untuk mensimulasikan pasangan dependen : fromListtidak dapat memberi tahu Anda panjang vektor secara statis, tetapi dapat mengembalikan sesuatu yang dapat Anda sesuaikan dengan pola untuk mempelajari panjang vektor - Natty nelemen pertama tuple . Seperti yang dikatakan Conor McBride dalam jawaban terkait , "Anda melihat satu hal, dan dengan demikian, belajarlah tentang hal lain".

Ini adalah teknik umum untuk tipe yang dikuantifikasi secara eksistensial. Karena Anda tidak dapat benar-benar melakukan apa pun dengan data yang Anda tidak tahu jenisnya - coba tulis fungsi data Something = forall a. Sth a- keberadaan sering dibundel dengan bukti GADT yang memungkinkan Anda untuk memulihkan jenis aslinya dengan melakukan tes pencocokan pola. Pola umum lain untuk eksistensial termasuk mengemas fungsi untuk memproses tipe Anda ( data AWayToGetTo b = forall a. HeresHow a (a -> b)) yang merupakan cara yang rapi untuk melakukan modul kelas satu, atau membangun kamus tipe kelas ( data AnOrd = forall a. Ord a => AnOrd a) yang dapat membantu meniru polimorfisme subtipe.

ghci> fromList [1,2,3]
AVec (Sy (Sy (Sy Zy))) (VCons 1 (VCons 2 (VCons 3 Nil)))

Pasangan tangguh berguna setiap kali sifat statis data bergantung pada informasi dinamis yang tidak tersedia pada waktu kompilasi. Ini filteruntuk vektor:

filter :: (a -> Bool) -> Vec n a -> AVec a
filter f = foldr (\x (AVec n xs) -> if f x
                                    then AVec (Sy n) (VCons x xs)
                                    else AVec n xs) (AVec Zy VNil) 

Untuk dotdua AVecs, kita perlu membuktikan kepada GHC bahwa panjangnya sama. Data.Type.Equalitymendefinisikan GADT yang hanya dapat dibangun ketika argumen tipenya sama:

data (a :: k) :~: (b :: k) where
    Refl :: a :~: a  -- short for 'reflexivity'

Ketika Anda mencocokkan pola aktif Refl, GHC tahu itu a ~ b. Ada juga beberapa fungsi untuk membantu Anda bekerja dengan jenis ini: kami akan gunakan gcastWithuntuk mengonversi antara jenis yang setara, dan TestEqualityuntuk menentukan apakah dua Nattys sama.

Untuk menguji kesamaan dua Nattys, kita akan perlu untuk membuat penggunaan fakta bahwa jika dua angka adalah sama, maka penerus mereka juga sama ( :~:adalah kongruen lebih S):

congSuc :: (n :~: m) -> (S n :~: S m)
congSuc Refl = Refl

Pencocokan pola Refldi sebelah kiri membuat GHC mengetahui hal itu n ~ m. Dengan pengetahuan itu, itu sepele S n ~ S m, jadi GHC memungkinkan kita segera mengembalikan yang baru Refl.

Sekarang kita dapat menulis contoh TestEqualitydengan rekursi langsung. Jika kedua angka tersebut nol, keduanya sama. Jika kedua nomor memiliki pendahulu, mereka sama jika pendahulunya sama. (Jika mereka tidak sama, kembalilah Nothing.)

instance TestEquality Natty where
    -- testEquality :: Natty n -> Natty m -> Maybe (n :~: m)
    testEquality Zy Zy = Just Refl
    testEquality (Sy n) (Sy m) = fmap congSuc (testEquality n m)  -- check whether the predecessors are equal, then make use of congruence
    testEquality Zy _ = Nothing
    testEquality _ Zy = Nothing

Sekarang kita dapat menempatkan potongan untuk dotsepasang AVecs panjang tidak diketahui.

dot' :: Num a => AVec a -> AVec a -> Maybe a
dot' (AVec n u) (AVec m v) = fmap (\proof -> gcastWith proof (dot u v)) (testEquality n m)

Pertama, pencocokan pola pada AVeckonstruktor untuk mengeluarkan representasi runtime dari panjang vektor. Sekarang gunakan testEqualityuntuk menentukan apakah panjangnya sama. Jika ya, kita harus Just Refl; gcastWithakan menggunakan bukti kesetaraan untuk memastikan bahwa dot u vdiketik dengan baik dengan menggunakan n ~ masumsi implisitnya .

ghci> let v1 = fromList [1,2,3]
ghci> let v2 = fromList [4,5,6]
ghci> let v3 = fromList [7,8]
ghci> dot' v1 v2
Just 32
ghci> dot' v1 v3
Nothing  -- they weren't the same length

Perhatikan bahwa, karena vektor tanpa pengetahuan statis panjangnya pada dasarnya adalah sebuah daftar, kami telah secara efektif mengimplementasikan kembali versi daftar dot :: Num a => [a] -> [a] -> Maybe a. Perbedaannya adalah bahwa versi ini diimplementasikan dalam hal vektor dot. Inilah intinya: sebelum pemeriksa tipe memungkinkan Anda menelepon dot, Anda harus menguji apakah daftar input memiliki panjang yang sama testEquality. Saya cenderung mendapatkan- ifpernyataan yang salah, tetapi tidak dalam pengaturan yang diketik secara dependen!

Anda tidak dapat menghindari menggunakan pembungkus eksistensial di tepi sistem Anda, ketika Anda berurusan dengan data runtime, tetapi Anda dapat menggunakan tipe dependen di mana saja di dalam sistem Anda dan menyimpan pembungkus eksistensial di tepi, ketika Anda melakukan validasi input.

Karena Nothingtidak terlalu informatif, Anda dapat lebih lanjut memperbaiki jenis dot'untuk mengembalikan bukti bahwa panjangnya tidak sama (dalam bentuk bukti bahwa perbedaannya tidak 0) dalam kasus kegagalan. Ini sangat mirip dengan teknik standar Haskell menggunakan Either String auntuk mungkin mengembalikan pesan kesalahan, meskipun istilah bukti jauh lebih bermanfaat secara komputasi daripada string!

Dengan demikian mengakhiri tur peluit berhenti ini dari beberapa teknik yang umum dalam pemrograman Haskell yang diketik secara dependen. Pemrograman dengan tipe seperti ini di Haskell benar-benar keren, tetapi benar-benar canggung pada saat yang sama. Memecah semua data dependen Anda menjadi banyak representasi yang berarti hal yang sama - Natjenis, Natjenis, Natty nsingleton - benar-benar sangat rumit, meskipun ada pembuat kode untuk membantu dengan pelat boiler. Saat ini juga ada batasan pada apa yang dapat dipromosikan ke tingkat tipe. Ini menggiurkan! Pikiran boggles pada kemungkinan - dalam literatur ada contoh dalam Haskell sangat diketik printf, antarmuka database, mesin tata letak UI ...

Jika Anda ingin membaca lebih lanjut, ada banyak literatur tentang Haskell yang diketik secara dependen, baik yang diterbitkan maupun di situs-situs seperti Stack Overflow. Sebuah titik awal yang baik adalah yang Hasochism kertas - kertas melewati sangat contoh ini (antara lain), membahas bagian yang menyakitkan dalam beberapa detail. The lajang kertas menunjukkan teknik nilai tunggal (seperti Natty). Untuk informasi lebih lanjut tentang mengetik secara umum, tutorial Agda adalah tempat yang baik untuk memulai; juga, Idris adalah bahasa dalam pengembangan yang (secara kasar) dirancang untuk menjadi "Haskell dengan tipe bergantung".

Itu disebut pengetikan dependen . Setelah Anda tahu namanya, Anda dapat menemukan lebih banyak informasi tentang itu daripada yang Anda harapkan. Ada juga bahasa haskell seperti menarik yang disebut Idris yang menggunakannya secara asli. Penulisnya telah melakukan beberapa presentasi yang sangat bagus tentang topik yang dapat Anda temukan di youtube.