Haskell'in cebirsel veri türleri

SORU

19 AĞUSTOS 2008, Salı

Haskell'in cebirsel veri türleri

Tam Haskell'ın kavramları anlamaya çalışıyorum.

C cebirsel veri türleri genel türler benzer, örneğin,# ve Java? Ve nasıl farklılar? Onlar hakkında çok cebirsel nedir?

Evrensel cebir ve yüzük ve alanları biliyorum, ama ben sadece Haskell bu tür işler nasıl belirsiz bir fikir.

CEVAP

6 Mayıs 2011, Cuma

Haskellcebirsel veri türleriböyle beri adında bir karşılıkilk Cebirkategori teori, bize Bazı Kanun vererek, bazı işlemler ve bazı işlemek için simgeler. Hatta düzenli veri yapıları tanımlamak için cebirsel gösterimi kullanabiliriz:

sum türleri (ayrık sendikalar, Either vs.) temsil eder.
• ürün türleri (örneğin yapılar ya da dizilerini temsil eder
Singleton türü (örneğin data X a = X a X
Birim türü için 1 ()
veμen azından sabit noktası (özyinelemeli türleri gibi), genellikle örtülü.

bazı ek gösterim: ile

X•X X²

Aslında, belki de aşağıdaki Brent Yorgey) bir Haskell veri türü için düzenli olarak bunu ifade edebilir bakımından 1, X, , •, ve en az bir sabit nokta.

Bu yazımda kısaca çok düzenli veri yapıları tanımlayabiliriz:

Birimler: data () = ()

1
Seçenekler: data Maybe a = Nothing | Just a

1 X
Listeler: data [a] = [] | a : [a]

L = 1 X•L
İkili ağaçlar: data BTree a = Empty | Node a (BTree a) (BTree a)

B = 1 X•B²

Diğer işlemler tutun (Brent Yorgey kağıt, başvuruları listelenen alınan):

Genişleme: düzeltme noktayı gözler önüne serilen listeleri hakkında düşünmek için yararlı olabilir. 22* *(yani, listeler ya boş, ya da bir eleman veya elemanlar iki ya da üç, ya da ...)
Kompozisyon ◦ belirli türleri F G kompozisyon F ◦ G bir tür olan yapılar “F-yapılar yapılmış G-yapıları” (örneğin R = X • (L ◦ R) nereye L listeler, bir gül ağacı.
Bir veri türü D (D') bir tek D-yapıların türü verilen“, yani ayırt edici bir yerde herhangi bir veri içeren.” deliğin türev türev Bu inanılmaz matematik türev kuralları ile aynıdır tatmin:

1′ = 0

X′ = 1

(F G)′ = F' G′

(F • G)′ = F • G′ F′ • G

(F ◦ G)′ = (F′ ◦ G) • G′