Kapan tipe yang lebih tinggi berguna?

Saya telah melakukan dev di F # untuk sementara waktu dan saya menyukainya. Namun satu kata kunci yang saya tahu tidak ada di F # adalah tipe yang lebih tinggi. Saya telah membaca materi tentang tipe yang lebih baik, dan saya rasa saya memahami definisi mereka. Saya hanya tidak yakin mengapa mereka berguna. Adakah yang bisa memberikan beberapa contoh jenis tipe yang lebih tinggi yang memudahkan di Scala atau Haskell, yang membutuhkan solusi di F #? Juga untuk contoh-contoh ini, apa penyelesaiannya tanpa tipe yang lebih baik (atau sebaliknya di F #)? Mungkin saya sudah terbiasa mengatasinya sehingga saya tidak memperhatikan ketiadaan fitur itu.

(Saya pikir) Saya mengerti bahwa alih-alih myList |> List.map fatau myList |> Seq.map f |> Seq.toListtipe yang lebih tinggi memungkinkan Anda untuk hanya menulis myList |> map fdan itu akan mengembalikan a List. Itu bagus (dengan asumsi itu benar), tetapi tampaknya agak kecil? (Dan tidak bisakah itu dilakukan hanya dengan mengizinkan overloading fungsi?) Saya biasanya mengonversi menjadi Seqdan kemudian saya dapat mengonversi ke apa pun yang saya inginkan sesudahnya. Sekali lagi, mungkin saya terlalu terbiasa mengatasinya. Tapi adakah contoh di mana tipe yang lebih baik benar-benar menyelamatkan Anda baik dalam penekanan tombol atau dalam keamanan tipe?

Jadi jenis jenisnya adalah jenisnya yang sederhana. Misalnya Intmemiliki jenis *yang berarti itu adalah tipe dasar dan dapat dipakai oleh nilai. Dengan beberapa definisi longgar dari tipe yang lebih tinggi (dan saya tidak yakin di mana F # menarik garis, jadi mari kita sertakan saja) wadah polimorfik adalah contoh yang bagus dari jenis yang lebih tinggi.

data List a = Cons a (List a) | Nil

Konstruktor tipe Listmemiliki jenis * -> *yang artinya harus melewati jenis beton agar dapat menghasilkan jenis beton: List Intdapat mempunyai penghuni suka [1,2,3]tetapi Listtidak bisa sendiri.

Saya akan berasumsi bahwa manfaat wadah polimorfik sudah jelas, tetapi jenis * -> *jenis yang lebih berguna ada daripada hanya wadahnya. Misalnya, relasi

data Rel a = Rel (a -> a -> Bool)

atau pengurai

data Parser a = Parser (String -> [(a, String)])

keduanya juga punya kebaikan * -> *.

Kita dapat mengambil ini lebih jauh di Haskell, bagaimanapun, dengan memiliki tipe dengan jenis yang lebih tinggi. Misalnya kita bisa mencari tipe dengan kind (* -> *) -> *. Contoh sederhananya adalah Shapeyang mencoba mengisi semacam wadah * -> *.

data Shape f = Shape (f ())

[(), (), ()] :: Shape List

Ini berguna untuk mengkarakterisasi Traversables di Haskell, misalnya, karena selalu dapat dibagi menjadi bentuk dan isinya.

split :: Traversable t => t a -> (Shape t, [a])

Sebagai contoh lain, mari pertimbangkan pohon yang diparameterisasi pada jenis cabang yang dimilikinya. Misalnya, pohon normal mungkin

data Tree a = Branch (Tree a) a (Tree a) | Leaf

Tapi kita bisa melihat bahwa tipe cabang mengandung a Pairof Tree as dan jadi kita bisa mengekstrak potongan itu dari tipe secara parametrik

data TreeG f a = Branch a (f (TreeG f a)) | Leaf

data Pair a = Pair a a
type Tree a = TreeG Pair a

TreeGKonstruktor tipe ini memiliki jenis (* -> *) -> * -> *. Kita dapat menggunakannya untuk membuat variasi lain yang menarik seperti aRoseTree

type RoseTree a = TreeG [] a

rose :: RoseTree Int
rose = Branch 3 [Branch 2 [Leaf, Leaf], Leaf, Branch 4 [Branch 4 []]]

Atau yang patologis seperti a MaybeTree

data Empty a = Empty
type MaybeTree a = TreeG Empty a

nothing :: MaybeTree a
nothing = Leaf

just :: a -> MaybeTree a
just a = Branch a Empty

Atau a TreeTree

type TreeTree a = TreeG Tree a

treetree :: TreeTree Int
treetree = Branch 3 (Branch Leaf (Pair Leaf Leaf))

Tempat lain yang muncul adalah di "algebras of functors". Jika kita melepaskan beberapa lapisan abstrak, ini mungkin lebih baik dianggap sebagai lipatan, seperti sum :: [Int] -> Int. Aljabar diberi parameter di atas functor dan carrier . The functor memiliki jenis * -> *dan operator jenis *sehingga sama sekali

data Alg f a = Alg (f a -> a)

memiliki kebaikan (* -> *) -> * -> *. Algberguna karena hubungannya dengan tipe data dan skema rekursi yang dibangun di atasnya.

-- | The "single-layer of an expression" functor has kind `(* -> *)`
data ExpF x = Lit Int
            | Add x x
            | Sub x x
            | Mult x x

-- | The fixed point of a functor has kind `(* -> *) -> *`
data Fix f = Fix (f (Fix f))

type Exp = Fix ExpF

exp :: Exp
exp = Fix (Add (Fix (Lit 3)) (Fix (Lit 4))) -- 3 + 4

fold :: Functor f => Alg f a -> Fix f -> a
fold (Alg phi) (Fix f) = phi (fmap (fold (Alg phi)) f)

Akhirnya, meskipun mereka secara teoritis mungkin, saya tidak pernah melihat bahkan tipe konstruktor tinggi-kinded. Kita kadang-kadang melihat fungsi jenis itu seperti mask :: ((forall a. IO a -> IO a) -> IO b) -> IO b, tapi saya pikir Anda harus menggali prolog jenis atau literatur yang diketik secara bergantung untuk melihat tingkat kerumitan dalam jenis.

Pertimbangkan Functorkelas tipe di Haskell, di mana fvariabel tipe tipe lebih tinggi:

class Functor f where
    fmap :: (a -> b) -> f a -> f b

Apa yang dikatakan oleh tanda tangan tipe ini adalah bahwa fmap mengubah parameter tipe fdari amenjadi b, tetapi membiarkannya fapa adanya. Jadi jika Anda menggunakan fmaplebih dari daftar Anda mendapatkan daftar, jika Anda menggunakannya di atas parser Anda mendapatkan parser, dan seterusnya. Dan ini adalah jaminan statis , waktu kompilasi.

Saya tidak tahu F #, tapi mari kita pertimbangkan apa yang terjadi jika kita mencoba mengekspresikan Functorabstraksi dalam bahasa seperti Java atau C #, dengan pewarisan dan generik, tetapi tidak ada generik yang lebih tinggi jenisnya. Percobaan pertama:

interface Functor<A> {
    Functor<B> map(Function<A, B> f);
}

Masalah dengan percobaan pertama ini adalah bahwa implementasi antarmuka diizinkan untuk mengembalikan kelas apa pun yang mengimplementasikan Functor. Seseorang dapat menulis FunnyList<A> implements Functor<A>yang mapmetodenya mengembalikan jenis koleksi yang berbeda, atau bahkan sesuatu yang lain yang sama sekali bukan koleksi tetapi masih a Functor. Selain itu, ketika Anda menggunakan mapmetode ini, Anda tidak dapat memanggil metode khusus subtipe apa pun pada hasil kecuali Anda menurunkannya ke tipe yang sebenarnya Anda harapkan. Jadi kita punya dua masalah:

1. Sistem tipe tidak mengizinkan kita untuk mengekspresikan invarian yang mapselalu mengembalikan Functorsubkelas yang sama dengan penerima.
2. Oleh karena itu, tidak ada cara aman tipe statis untuk memanggil Functormetode non- pada hasil map.

Ada cara lain yang lebih rumit yang dapat Anda coba, tetapi tidak ada yang benar-benar berhasil. Misalnya, Anda dapat mencoba menambah percobaan pertama dengan menentukan subtipe Functoryang membatasi jenis hasil:

interface Collection<A> extends Functor<A> {
    Collection<B> map(Function<A, B> f);
}

interface List<A> extends Collection<A> {
    List<B> map(Function<A, B> f);
}

interface Set<A> extends Collection<A> {
    Set<B> map(Function<A, B> f);
}

interface Parser<A> extends Functor<A> {
    Parser<B> map(Function<A, B> f);
}

// …

Hal ini membantu untuk melarang pelaksana antarmuka yang lebih sempit tersebut mengembalikan jenis yang salah Functordari mapmetode, tetapi karena tidak ada batasan berapa banyak Functorimplementasi yang dapat Anda miliki, tidak ada batasan berapa banyak antarmuka sempit yang Anda perlukan.

( EDIT: Dan perhatikan bahwa ini hanya berfungsi karena Functor<B>muncul sebagai jenis hasil, sehingga antarmuka anak dapat mempersempitnya. Jadi AFAIK kami tidak dapat mempersempit kedua penggunaan Monad<B>dalam antarmuka berikut:

interface Monad<A> {
    <B> Monad<B> flatMap(Function<? super A, ? extends Monad<? extends B>> f);
}

Di Haskell, dengan variabel tipe peringkat lebih tinggi, ini adalah (>>=) :: Monad m => m a -> (a -> m b) -> m b.)

Namun percobaan lain adalah menggunakan generik rekursif untuk mencoba dan membuat antarmuka membatasi jenis hasil dari subtipe ke subtipe itu sendiri. Contoh mainan:

/**
 * A semigroup is a type with a binary associative operation.  Law:
 *
 * > x.append(y).append(z) = x.append(y.append(z))
 */
interface Semigroup<T extends Semigroup<T>> {
    T append(T arg);
}

class Foo implements Semigroup<Foo> {
    // Since this implements Semigroup<Foo>, now this method must accept 
    // a Foo argument and return a Foo result. 
    Foo append(Foo arg);
}

class Bar implements Semigroup<Bar> {
    // Any of these is a compilation error:

    Semigroup<Bar> append(Semigroup<Bar> arg);

    Semigroup<Foo> append(Bar arg);

    Semigroup append(Bar arg);

    Foo append(Bar arg);

}

Tetapi teknik semacam ini (yang agak misterius bagi pengembang OOP run-of-the-mill Anda, heck ke pengembang fungsional run-of-the-mill Anda juga) masih tidak dapat mengungkapkan Functorkendala yang diinginkan juga:

interface Functor<FA extends Functor<FA, A>, A> {
    <FB extends Functor<FB, B>, B> FB map(Function<A, B> f);
}

Masalahnya di sini adalah ini tidak membatasi FBuntuk memiliki yang sama Fdengan FA—sehingga ketika Anda mendeklarasikan sebuah tipe List<A> implements Functor<List<A>, A>, mapmetode tersebut masih dapat mengembalikan NotAList<B> implements Functor<NotAList<B>, B>.

Percobaan terakhir, di Java, menggunakan tipe mentah (kontainer tanpa parameter):

interface FunctorStrategy<F> {
    F map(Function f, F arg);
} 

Di sini Fakan dipakai untuk jenis yang tidak diparameterisasi seperti hanya Listatau Map. Ini menjamin bahwa a FunctorStrategy<List>hanya dapat mengembalikan a List—tetapi Anda telah mengabaikan penggunaan variabel jenis untuk melacak jenis elemen daftar.

Inti dari masalah di sini adalah bahwa bahasa seperti Java dan C # tidak mengizinkan parameter tipe memiliki parameter. Di Java, jika Tmerupakan variabel tipe, Anda dapat menulis Tdan List<T>, tetapi tidak T<String>. Tipe yang lebih baik hati menghapus batasan ini, sehingga Anda bisa mendapatkan sesuatu seperti ini (tidak sepenuhnya dipikirkan):

interface Functor<F, A> {
    <B> F<B> map(Function<A, B> f);
}

class List<A> implements Functor<List, A> {

    // Since F := List, F<B> := List<B>
    <B> List<B> map(Function<A, B> f) {
        // ...
    }

}

Dan membahas bagian ini secara khusus:

(Saya pikir) Saya mengerti bahwa alih-alih myList |> List.map fatau myList |> Seq.map f |> Seq.toListtipe yang lebih tinggi memungkinkan Anda untuk hanya menulis myList |> map fdan itu akan mengembalikan a List. Itu bagus (dengan asumsi itu benar), tetapi tampaknya agak kecil? (Dan tidak bisakah itu dilakukan hanya dengan mengizinkan overloading fungsi?) Saya biasanya mengubahnya menjadi Seqtetap dan kemudian saya dapat mengonversi ke apa pun yang saya inginkan sesudahnya.

Ada banyak bahasa yang menggeneralisasi gagasan mapfungsi dengan cara ini, dengan memodelkannya seolah-olah, pada intinya, pemetaan adalah tentang urutan. Komentar Anda ini ada dalam semangat itu: jika Anda memiliki tipe yang mendukung konversi ke dan dari Seq, Anda mendapatkan operasi peta "gratis" dengan menggunakan kembali Seq.map.

Di Haskell, bagaimanapun, Functorkelasnya lebih umum dari itu; itu tidak terkait dengan gagasan tentang urutan. Anda dapat menerapkan fmapuntuk jenis yang tidak memiliki pemetaan yang baik untuk urutan, seperti IOtindakan, kombinator parser, fungsi, dll .:

instance Functor IO where
    fmap f action =
        do x <- action
           return (f x)

 -- This declaration is just to make things easier to read for non-Haskellers 
newtype Function a b = Function (a -> b)

instance Functor (Function a) where
    fmap f (Function g) = Function (f . g)  -- `.` is function composition

Konsep "pemetaan" sebenarnya tidak terikat pada urutan. Yang terbaik adalah memahami hukum functor:

(1) fmap id xs == xs
(2) fmap f (fmap g xs) = fmap (f . g) xs

Sangat informal:

1. Hukum pertama mengatakan bahwa pemetaan dengan fungsi identitas / noop sama dengan tidak melakukan apa-apa.
2. Hukum kedua mengatakan bahwa hasil apa pun yang dapat Anda hasilkan dengan pemetaan dua kali, Anda juga dapat menghasilkan dengan pemetaan sekali.

Inilah mengapa Anda ingin fmapmempertahankan jenisnya — karena segera setelah Anda mendapatkan mapoperasi yang menghasilkan jenis hasil yang berbeda, akan jauh lebih sulit untuk membuat jaminan seperti ini.

Saya tidak ingin mengulang informasi dalam beberapa jawaban bagus yang sudah ada di sini, tetapi ada poin penting yang ingin saya tambahkan.

Anda biasanya tidak memerlukan tipe yang lebih tinggi untuk mengimplementasikan satu monad tertentu, atau functor (atau functor aplikatif, atau panah, atau ...). Tetapi melakukan hal itu sebagian besar kehilangan intinya.

Secara umum saya telah menemukan bahwa ketika orang tidak melihat kegunaan dari functors / monads / whatevers, seringkali karena mereka memikirkan hal-hal ini satu per satu . Operasi Functor / monad / etc benar-benar tidak menambahkan apa-apa ke satu instance (daripada memanggil bind, fmap, dll. Saya bisa memanggil operasi apa pun yang saya gunakan untuk mengimplementasikan bind, fmap, dll). Apa yang Anda benar-benar ingin abstraksi ini adalah sehingga Anda dapat memiliki kode yang bekerja secara umum dengan setiap functor / monad / etc.

Dalam konteks di mana kode generik seperti itu banyak digunakan, ini berarti setiap kali Anda menulis instance monad baru, tipe Anda segera mendapatkan akses ke sejumlah besar operasi berguna yang telah ditulis untuk Anda . Itulah tujuan melihat monad (dan functor, dan ...) di mana-mana; bukan agar saya dapat menggunakan binddaripada concatdan mapuntuk mengimplementasikan myFunkyListOperation(yang tidak menghasilkan apa-apa bagi saya sendiri), melainkan agar ketika saya membutuhkan myFunkyParserOperationdan myFunkyIOOperationsaya dapat menggunakan kembali kode yang semula saya lihat dalam daftar karena sebenarnya monad-generik .

Tetapi untuk mengabstraksi tipe berparameter seperti monad dengan keamanan tipe , Anda memerlukan tipe tipe yang lebih tinggi (seperti yang dijelaskan dalam jawaban lain di sini).

Untuk perspektif yang lebih spesifik .NET, saya menulis posting blog tentang ini beberapa waktu yang lalu. Intinya adalah, dengan tipe tipe yang lebih tinggi, Anda berpotensi dapat menggunakan kembali blok LINQ yang sama antara IEnumerablesdan IObservables, tetapi tanpa tipe yang lebih tinggi, hal ini tidak mungkin.

Yang paling dekat Anda bisa mendapatkan (aku tahu setelah posting blog) adalah untuk membuat Anda sendiri IEnumerable<T>dan IObservable<T>dan diperpanjang mereka berdua dari IMonad<T>. Ini akan memungkinkan Anda untuk menggunakan kembali blok LINQ Anda jika dilambangkan IMonad<T>, tetapi kemudian itu tidak lagi aman untuk mengetik karena memungkinkan Anda untuk mencampur-dan-mencocokkan IObservablesdan IEnumerablesdalam blok yang sama, yang mungkin terdengar menarik untuk mengaktifkan ini, Anda akan pada dasarnya hanya mendapatkan beberapa perilaku yang tidak terdefinisi.

Saya menulis posting selanjutnya tentang bagaimana Haskell membuat ini mudah. (A no-op, sungguh - membatasi blok ke jenis monad tertentu membutuhkan kode; mengaktifkan penggunaan kembali adalah defaultnya).

Contoh yang paling banyak digunakan dari polimorfisme tipe lebih tinggi di Haskell adalah Monadantarmuka. Functordan Applicativejenisnya lebih tinggi dengan cara yang sama, jadi saya akan menunjukkannya Functoruntuk menunjukkan sesuatu yang ringkas.

class Functor f where
    fmap :: (a -> b) -> f a -> f b

Sekarang, periksa definisi itu, lihat bagaimana variabel tipe fdigunakan. Anda akan melihat itu ftidak berarti tipe yang memiliki nilai. Anda dapat mengidentifikasi nilai dalam tanda tangan tipe itu karena merupakan argumen dan hasil dari suatu fungsi. Jadi tipe variabel adan bmerupakan tipe yang dapat memiliki nilai. Begitu juga dengan tipe ekspresi f adan f b. Tapi tidak fsendiri. fadalah contoh variabel tipe yang lebih disukai. Mengingat *jenis jenis yang dapat memiliki nilai, fpasti jenis * -> *. Artinya, dibutuhkan tipe yang bisa memiliki nilai, karena kita tahu dari pemeriksaan sebelumnya bahwa adan bharus punya nilai. Dan kami juga tahu itu f adanf b harus memiliki nilai, sehingga mengembalikan tipe yang harus memiliki nilai.

Ini membuat yang fdigunakan dalam definisi Functorvariabel tipe yang lebih baik.

The Applicativedan Monadinterface menambahkan lebih banyak, tapi mereka kompatibel. Ini berarti bahwa mereka mengerjakan variabel tipe dengan jenis * -> *juga.

Mengerjakan tipe yang lebih tinggi jenisnya memperkenalkan level abstraksi tambahan - Anda tidak dibatasi hanya membuat abstraksi di atas tipe dasar. Anda juga dapat membuat abstraksi atas jenis yang mengubah jenis lain.