Fixpoint mana yang merupakan tipe daftar Haskell?

Katakanlah bahwa daftar didefinisikan sebagai

List a = Nil | Cons a (List a)

Lalu, di Haskell adalah List xfixpoint terbesar atau paling tidak? Saya bertanya karena lfp harus mengecualikan daftar yang tidak terbatas (tetapi Anda dapat membangunnya di Haskell), sedangkan gfp harus mengecualikan daftar yang terbatas.

Yang tepat adalah pengaturan

data ListF a x = Nil | Cons a x

Sekarang kamu bisa menulis

newtype Mu f= Mu (forall a.(f a->a)->a)
data Nu f   = forall a. Nu a (a->f a)

Di Haskell kita bisa mengamati itu Mu ListFdan Nu ListFbertepatan. Jadi, bisa berupa (!). (satu sumber pada klaim ini: http://www.cs.ox.ac.uk/jeremy.gibbons/publications/adt.pdf )

Selain itu, kami dapat membuktikan hal-hal dengan menginduksi pada semua daftar dan mendapatkan bukti yang berfungsi selama kami membatasi diri untuk mengurus yang terbatas, seperti dijelaskan di sini: http://www.cs.ox.ac.uk/jeremy.gibbons/ publikasi / cepat + lepas.pdf

Dua referensi lain tentang ini adalah:

• http://homepages.inf.ed.ac.uk/wadler/papers/free-rectypes/free-rectypes.txt (yang merupakan dokumen penting secara historis)

• http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.1418 (yang merupakan eksposisi yang sangat baik)

Ini adalah titik tetap terbesar, atau bilangan bulat batubara terakhir, tergantung pada bagaimana Anda mengatur segalanya. Dalam Haskell tidak mungkin untuk menentukan tipe data dari daftar hingga karena Haskell tidak memiliki tipe induktif, hanya tipe coinductive. Banyak orang yang menyangkal masalah khusus ini.