Haskell se algebraïese datatipes

StackOverflow https://stackoverflow.com/questions/16770

Vra

Ek probeer om al Haskell se konsepte ten volle te verstaan.

Op watter maniere is algebraïese datatipes soortgelyk aan generiese tipes, bv. in C# en Java?En hoe verskil hulle?Wat is in elk geval so algebraïes aan hulle?

Ek is vertroud met universele algebra en sy ringe en velde, maar ek het net 'n vae idee van hoe Haskell se tipes werk.

Was dit nuttig?

Oplossing

"Algebraïese datatipes" in Haskell-ondersteuning volle parametriese polimorfisme, wat die meer tegnies korrekte naam vir generiese middels is, as 'n eenvoudige voorbeeld die lys datatipe:

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

Is gelykstaande (soveel as moontlik, en ignoreer nie-streng evaluering, ens.) aan

 class List<a> {
     class Cons : List<a> {
         a head;
         List<a> tail;
     }
     class Nil : List<a> {}
 }

Natuurlik laat Haskell se tipe stelsel meer ...interessante gebruik van tipe parameters maar dit is net 'n eenvoudige voorbeeld.Met betrekking tot die "Algebraïese Tipe" naam, ek was eerlikwaar nog nooit heeltemal seker van die presiese rede waarom hulle so genoem word nie, maar het aangeneem dat dit te wyte is aan die wiskundige onderbou van die tipe stelsel.ek glo dat die rede daarop neerkom dat die teoretiese definisie van 'n ADT die "produk van 'n stel konstrukteurs" is, maar dit is 'n paar jaar sedert ek universiteit ontsnap het, so ek kan nie meer die besonderhede onthou nie.

[Wysig:Dankie aan Chris Conway wat my dwase fout uitgewys het, ADT is natuurlik somtipes, die konstrukteurs wat die produk/tuple van velde verskaf]

Ander wenke

Haskell s'n algebraïese datatipes word so genoem aangesien hulle ooreenstem met 'n aanvanklike algebra in kategorie teorie, gee ons 'n paar wette, 'n paar bewerkings en 'n paar simbole om te manipuleer.Ons kan selfs algebraïese notasie gebruik om gereelde datastrukture te beskryf, waar:

  • + verteenwoordig somtipes (onsamehangende unies, bv. Either).
  • • verteenwoordig produktipes (bv.strukture of tupels)
  • X vir die enkelton tipe (bv. data X a = X a)
  • 1 vir die tipe eenheid ()
  • en μ vir die minste vaste punt (bv.rekursiewe tipes), gewoonlik implisiete.

met 'n paar bykomende notasie:

  • X² vir X•X

Trouens, jy kan sê (na aanleiding van Brent Yorgey) dat 'n Haskell-datatipe gereeld is as dit uitgedruk kan word in terme van 1, X, +, •, en 'n minste vaste punt.

Met hierdie notasie kan ons baie gereelde datastrukture bondig beskryf:

  • Eenhede: data () = ()

    1

  • Opsies: data Maybe a = Nothing | Just a

    1 + X

  • Lyste: data [a] = [] | a : [a]

    L = 1+X•L

  • Binêre bome: data BTree a = Empty | Node a (BTree a) (BTree a)

    B = 1 + X•B²

Ander operasies geld (uit Brent Yorgey se referaat, gelys in die verwysings):

  • Uitbreiding:die ontvouing van die fix punt kan nuttig wees om na te dink oor lyste. L = 1 + X + X² + X³ + ... (dit wil sê, lyste is óf leeg, óf hulle het een element, óf twee elemente, óf drie, of ...)

  • samestelling, ◦, gegewe tipes F en G, die samestelling F ◦ G is 'n tipe wat "F-strukture wat uit G-strukture gemaak is" bou (bv. R = X • (L ◦ R) ,waar L is lyste, is 'n roosboom.

  • Differensiasie, die afgeleide van 'n datatipe D (aangegee as D') is die tipe D-strukture met 'n enkele "gat", dit wil sê, 'n onderskeie ligging wat geen data bevat nie.Dit voldoen verbasend aan dieselfde reëls as vir differensiasie in calculus:

    1′ = 0

    X′ = 1

    (F + G)′ = F' + G′

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

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

Verwysings:

In universele algebra 'n algebra bestaan ​​uit enkele stelle elemente (dink aan elke stel as die stel waardes van 'n tipe) en sommige bewerkings, wat elemente op elemente karteer.

Gestel byvoorbeeld dat u 'n tipe "lyselemente" en 'n tipe "lyste" het.As bewerkings het u die 'Empty List', wat 'n 0-Argument-funksie is wat 'n 'lys' teruggee, en 'n 'nadele' -funksie wat twee argumente neem, 'n 'lyselement' en 'n 'lys', en 'n "lys vervaardig ".

Op hierdie punt is daar baie algebras wat by die beskrywing pas, aangesien twee ongewenste dinge kan gebeur:

  • Daar kan elemente in die 'lys' -stel wees wat nie gebou kan word uit die 'leë lys' en die 'Cons-operasie' nie, sogenaamde 'rommel'.Dit kan lyste wees vanaf 'n element wat uit die lug val, of lusse sonder 'n begin, of oneindige lyste.

  • Die resultate van "nadele" wat op verskillende argumente toegepas is, kan gelyk wees, bvDit kan gelyk wees aan die leë lys wat 'n element in 'n nie-leë lys bevat.Dit word soms "verwarring" genoem.

'n Algebra wat nie een van hierdie ongewenste eienskappe het nie, word genoemaanvanklike, en dit is die beoogde betekenis van die abstrakte datatipe.

Die naam Aanvanklik is afkomstig van die eiendom dat daar presies een homomorfisme van die aanvanklike algebra na enige gegewe algebra is.In wese kan u die waarde van 'n lys evalueer deur die bewerkings in die ander algebra toe te pas, en die resultaat is goed gedefinieerd.

Dit raak meer ingewikkeld vir polimorfiese tipes ...

'n Eenvoudige rede waarom hulle algebraïes genoem word;daar is beide som (logiese disjunksie) en produk (logiese voegwoord) tipes.'n Somtipe is 'n gediskrimineerde vakbond, bv.

data Bool = False | True

'n Produktipe is 'n tipe met veelvuldige parameters:

data Pair a b = Pair a b

In O'Caml word "produk" meer eksplisiet gemaak:

type 'a 'b pair = Pair of 'a * 'b

Haskell se datatipes word "algebraïes" genoem vanweë hul verband met kategoriese beginalgebras.Maar so lê waansin.

@olliej:ADT's is eintlik "som" tipes.Tupels is produkte.

@Timbo:

Jy is basies reg dat dit soort van 'n abstrakte Tree-klas is met drie afgeleide klasse (Empty, Leaf en Node), maar jy sal ook die waarborg moet afdwing dat iemand wat jou Tree-klas gebruik, nooit enige nuwe afgeleide klasse kan byvoeg nie. , aangesien die strategie vir die gebruik van die Tree datat-tipe is om kode te skryf wat tydens looptyd verander, gebaseer op die tipe van elke element in die boom (en die toevoeging van nuwe afgeleide tipes sal bestaande kode breek).Jy kan jou soort van voorstel dat dit vieslik word in C# of C++, maar in Haskell, ML en OCaml is dit sentraal tot die taalontwerp en sintaksis, so koderingstyl ondersteun dit op 'n baie geriefliker manier, via patroonpassing.

ADT (som tipes) is ook soort van soos gemerk vakbonde of variant tipes in C of C++.

ou vraag, maar niemand se genoemde nietigheid nie, wat 'n belangrike aspek van Algebraïese Datatipes is, miskien die belangrikste aspek.Aangesien elke waarde die meeste een van alternatiewe is, is volledige saakgebaseerde patroonpassing moontlik.

Vir my het die konsep van Haskell se algebraïese datatipes altyd soos polimorfisme gelyk in OO-tale soos C#.

Kyk na die voorbeeld van http://en.wikipedia.org/wiki/Algebraic_data_types:

data Tree = Empty 
          | Leaf Int 
          | Node Tree Tree

Dit kan in C# geïmplementeer word as 'n TreeNode-basisklas, met 'n afgeleide Leaf-klas en 'n afgeleide TreeNodeWithChildren-klas, en as jy selfs 'n afgeleide EmptyNode-klas wil hê.

(OK, ek weet, niemand sal dit ooit doen nie, maar jy kan dit ten minste doen.)

Gelisensieer onder: CC-BY-SA met toeskrywing
Nie verbonde aan StackOverflow
scroll top