Programare declarativa1
Tipuri de date algebrice
Traian Florin S, erbanut,aIoana Leus, tean
Departamentul de Informatica, FMI, [email protected]
1bazat pe cursul Informatics 1: Functional Programming de la University of EdinburghTraian Florin S, erbanut,a Ioana Leus, tean (UB) PD—Tipuri date algebrice 1 / 22
Ce este un tip de date algebric?
Orice!
data Bool = False | Truedata Season = Winter | Spr ing | Summer | F a l ldata Shape = C i r c l e Float | Rectangle Float Floatdata Lis t a = N i l | Cons a ( List a )data Nat = Zero | Succ Natdata Exp = L i t I n t | Add Exp Exp | Mul Exp Expdata Tree a = Empty | Leaf a | Branch ( Tree a ) ( Tree a )data Maybe a = Nothing | Just adata Pai r a b = Pa i r a bdata Either a b = Left a | Right b
Traian Florin S, erbanut,a Ioana Leus, tean (UB) PD—Tipuri date algebrice 2 / 22
Ce este un tip de date algebric?
Orice!
data Bool = False | Truedata Season = Winter | Spr ing | Summer | F a l ldata Shape = C i r c l e Float | Rectangle Float Floatdata Lis t a = N i l | Cons a ( List a )data Nat = Zero | Succ Natdata Exp = L i t I n t | Add Exp Exp | Mul Exp Expdata Tree a = Empty | Leaf a | Branch ( Tree a ) ( Tree a )data Maybe a = Nothing | Just adata Pai r a b = Pa i r a bdata Either a b = Left a | Right b
Traian Florin S, erbanut,a Ioana Leus, tean (UB) PD—Tipuri date algebrice 2 / 22
Tipul de date Boolean
Tipul de date Boolean
data Bool = False | True
not : : Bool −> Boolnot False = Truenot True = False
(&&) : : Bool −> Bool −> BoolFalse && q = FalseTrue && q = q
( | | ) : : Bool −> Bool −> BoolFalse | | q = qTrue | | q = True
Traian Florin S, erbanut,a Ioana Leus, tean (UB) PD—Tipuri date algebrice 3 / 22
Tipul de date Boolean
Definirea egalitat, ii s, i a reprezentariiEq s, i Show
Eq
eqBool : : Bool −> Bool −> Bool
eqBool False False = TrueeqBool True True = TrueeqBool _ _ = False
Show
showBool : : Bool −> String
showBool False = " False "showBool True = " True "
Traian Florin S, erbanut,a Ioana Leus, tean (UB) PD—Tipuri date algebrice 4 / 22
Tipul de date Boolean
Definirea egalitat, ii s, i a reprezentariiEq s, i Show
Eq
eqBool : : Bool −> Bool −> BooleqBool False False = TrueeqBool True True = TrueeqBool _ _ = False
Show
showBool : : Bool −> StringshowBool False = " False "showBool True = " True "
Traian Florin S, erbanut,a Ioana Leus, tean (UB) PD—Tipuri date algebrice 4 / 22
Anotimpuri
Anotimpuri
data Season = Spring | Summer | Autumn | Winter
next : : Season −> Seasonnext Spring = Summernext Summer = Autumnnext Autumn = Winternext Winter = Spr ing
Traian Florin S, erbanut,a Ioana Leus, tean (UB) PD—Tipuri date algebrice 5 / 22
Anotimpuri
Definirea egalitat, ii s, i a reprezentariiEq s, i Show
eqSeason : : Season −> Season −> BooleqSeason Spr ing Spr ing = TrueeqSeason Summer Summer = TrueeqSeason Autumn Autumn = TrueeqSeason Winter Winter = TrueeqSeason _ _ = False
showSeason : : Season −> StringshowSeason Spr ing = " Spr ing "showSeason Summer = "Summer"showSeason Autumn = " Autumn "showSeason Winter = " Winter "
Traian Florin S, erbanut,a Ioana Leus, tean (UB) PD—Tipuri date algebrice 6 / 22
Anotimpuri
Enumerari s, i indici
data Season = Winter | Spr ing | Summer | F a l lto In t : : Season −> I n tto In t Winter = 0to In t Spring = 1to In t Summer = 2to In t F a l l = 3
fromInt : : I n t −> SeasonfromInt 0 = WinterfromInt 1 = SpringfromInt 2 = SummerfromInt 3 = F a l l
next : : Season −> Season
next x = fromInt ( ( to In t x + 1) ‘mod‘ 4)
eqSeason : : Season −> Season −> Bool
eqSeason x y = ( to In t x == to In t y )
Traian Florin S, erbanut,a Ioana Leus, tean (UB) PD—Tipuri date algebrice 7 / 22
Anotimpuri
Enumerari s, i indici
data Season = Winter | Spr ing | Summer | F a l lto In t : : Season −> I n tto In t Winter = 0to In t Spring = 1to In t Summer = 2to In t F a l l = 3
fromInt : : I n t −> SeasonfromInt 0 = WinterfromInt 1 = SpringfromInt 2 = SummerfromInt 3 = F a l l
next : : Season −> Seasonnext x = fromInt ( ( to In t x + 1) ‘mod‘ 4)
eqSeason : : Season −> Season −> BooleqSeason x y = ( to In t x == to In t y )
Traian Florin S, erbanut,a Ioana Leus, tean (UB) PD—Tipuri date algebrice 7 / 22
Forme geometrice
Cercuri s, i dreptunghiuri
type Radius = Floattype Width = Floattype Height = Float
data Shape = C i r c l e Radius| Rectangle Width Height
area : : Shape −> Floatarea ( C i r c l e r ) = pi * r ^2area ( Rectangle w h ) = w * h
Traian Florin S, erbanut,a Ioana Leus, tean (UB) PD—Tipuri date algebrice 8 / 22
Forme geometrice
Definirea egalitat, ii s, i a reprezentariiEq s, i Show
eqShape : : Shape −> Shape −> Bool
eqShape ( C i r c l e r ) ( C i r c l e r ’ ) = ( r == r ’ )eqShape ( Rectangle w h ) ( Rectangle w’ h ’ ) = (w == w ’ ) && (
h == h ’ )eqShape _ _ = False
showShape : : Shape −> String
showShape ( C i r c l e r ) = " C i r c l e " ++ showF rshowShape ( Rectangle w h ) = " Rectangle " ++ showF w
++ " " ++ showF h
showF : : Float −> StringshowF x | x >= 0 = show x
| otherwise = " ( " ++ show x ++ " ) "
Traian Florin S, erbanut,a Ioana Leus, tean (UB) PD—Tipuri date algebrice 9 / 22
Forme geometrice
Definirea egalitat, ii s, i a reprezentariiEq s, i Show
eqShape : : Shape −> Shape −> BooleqShape ( C i r c l e r ) ( C i r c l e r ’ ) = ( r == r ’ )eqShape ( Rectangle w h ) ( Rectangle w’ h ’ ) = (w == w ’ ) && (
h == h ’ )eqShape _ _ = False
showShape : : Shape −> StringshowShape ( C i r c l e r ) = " C i r c l e " ++ showF rshowShape ( Rectangle w h ) = " Rectangle " ++ showF w
++ " " ++ showF h
showF : : Float −> StringshowF x | x >= 0 = show x
| otherwise = " ( " ++ show x ++ " ) "
Traian Florin S, erbanut,a Ioana Leus, tean (UB) PD—Tipuri date algebrice 9 / 22
Forme geometrice
Teste s, i operatori de proiect, ie
i s C i r c l e : : Shape −> Booli s C i r c l e ( C i r c l e r ) = Truei s C i r c l e _ = False
i sRectang le : : Shape −> Booli sRectang le ( Rectangle w h ) = Truei sRectang le _ = False
rad ius : : Shape −> Floatrad ius ( C i r c l e r ) = r
width : : Shape −> Floatwidth ( Rectangle w h ) = w
he igh t : : Shape −> Floathe igh t ( Rectangle w h ) = h
Traian Florin S, erbanut,a Ioana Leus, tean (UB) PD—Tipuri date algebrice 10 / 22
Forme geometrice
Pattern-matching
area : : Shape −> Floatarea ( C i r c l e r ) = pi * r ^2area ( Rectangle w h ) = w * h
area : : Shape −> Floatarea s =
i f i s C i r c l e s thenl e t
r = rad ius sin
pi * r ^2else i f i sRectang le s then
l e tw = width sh = he igh t s
inw * h
else error " imposs ib le "Traian Florin S, erbanut,a Ioana Leus, tean (UB) PD—Tipuri date algebrice 11 / 22
Liste
Pattern-matching
Declarat,ie ca tip de date algebric
data Lis t a = N i l| Cons a ( List a )
append : : List a −> List a −> List aappend N i l ys = ysappend ( Cons x xs ) ys = Cons x ( append xs ys )
Traian Florin S, erbanut,a Ioana Leus, tean (UB) PD—Tipuri date algebrice 12 / 22
Liste
Constructori simboluri
Declarat,ie ca tip de date algebric cu simboluri
data Lis t a = N i l| a : : : List a
deriving (Show)i n f i x r 5 : : :
(+++) : : List a −> List a −> List ai n f i x r 5 +++N i l +++ ys = ys( x : : : xs ) +++ ys = x : : : ( xs +++ ys )
Comparat,i cu versiunea folosind notat,ia predefinita
(++) : : [ a ] −> [ a ] −> [ a ][ ] ++ ys = ys( x : xs ) ++ ys = x : ( xs ++ ys )
Traian Florin S, erbanut,a Ioana Leus, tean (UB) PD—Tipuri date algebrice 13 / 22
Liste
Definirea egalitat, ii s, i a reprezentariiEq s, i Show
eqL i s t : : Eq a => Lis t a −> List a −> BooleqL i s t N i l N i l = TrueeqL i s t ( x : : : xs ) ( y : : : ys ) = x == y && eqL is t xs yseqL i s t _ _ = False
showList : : Show a => Lis t a −> StringshowList N i l = " N i l "showList ( x : : : xs ) = show x ++ " : : : " ++ showList xs
Traian Florin S, erbanut,a Ioana Leus, tean (UB) PD—Tipuri date algebrice 14 / 22
Numere naturale
Numerele Naturale (Peano)
Declarat,ie ca tip de date algebric
data Nat = Zero| Succ Nat
( ^ ^ ^ ) : : Float −> Nat −> Floatx ^^^ Zero = 1.0x ^^^ ( Succ n ) = x * x ^^^ n
Comparat,i cu versiunea folosind notat,ia predefinita
( ^ ^ ) : : Float −> I n t −> Floatx ^^ 0 = 1.0x ^^ n = x * ( x ^^ ( n−1) )
Traian Florin S, erbanut,a Ioana Leus, tean (UB) PD—Tipuri date algebrice 15 / 22
Numere naturale
Adunare s, i înmult, ire
Definit,ie pe tipul de date algebric(+++) : : Nat −> Nat −> Natm +++ Zero = mm +++ ( Succ n ) = Succ (m +++ n )
( * * * ) : : Nat −> Nat −> Natm * * * Zero = Zerom * * * ( Succ n ) = (m * * * n ) +++ m
Comparat,i cu versiunea folosind notat,ia predefinita(+ ) : : I n t −> I n t −> I n tm + 0 = mm + n = (m + ( n−1) ) + 1
( * ) : : I n t −> I n t −> I n tm * 0 = 0m * n = (m * ( n−1) ) + m
Traian Florin S, erbanut,a Ioana Leus, tean (UB) PD—Tipuri date algebrice 16 / 22
Numere naturale
Tipuri de date algebrice
data Typename = Cons1 t11 . . . t1k1
|Cons2 t21 . . . t2k2
| . . .
|Consn tn1 . . . tnkn
unde k1, . . . , kn ≥ 0
Se pot defini tipuri parametrizate.
Se pot folosi definit,ii recursive.
Traian Florin S, erbanut,a Ioana Leus, tean (UB) PD—Tipuri date algebrice 17 / 22
Numere naturale
Date personale
type FirstName = Stringtype LastName = Stringtype Age = I n ttype Height = Floattype PhoneNumber = Stringtype Flavor = String
data Person = Person FirstName LastName Age HeightPhoneNumber F lavor
Traian Florin S, erbanut,a Ioana Leus, tean (UB) PD—Tipuri date algebrice 18 / 22
Numere naturale
Proiect, ii
f i rs tName : : Person −> Stringf i rs tName ( Person f i r s tname _ _ _ _ _ ) = f i r s tname
lastName : : Person −> StringlastName ( Person _ lastname _ _ _ _ ) = lastname
age : : Person −> I n tage ( Person _ _ age _ _ _ ) = age
he igh t : : Person −> Floathe igh t ( Person _ _ _ he igh t _ _ ) = he igh t
phoneNumber : : Person −> StringphoneNumber ( Person _ _ _ _ number _ ) = number
f l a v o r : : Person −> Stringf l a v o r ( Person _ _ _ _ _ f l a v o r ) = f l a v o r
Traian Florin S, erbanut,a Ioana Leus, tean (UB) PD—Tipuri date algebrice 19 / 22
Numere naturale
Utilizare
Main*> l e t i o n e l = Person " Ion " " Ionescu " 20 175.2" 0712334567 " " Caramel "
Main*> f i rs tName i o n e l" Ion "Main*> he igh t i o n e l175.2Main*> f l a v o r i o n e l" Caramel "
Traian Florin S, erbanut,a Ioana Leus, tean (UB) PD—Tipuri date algebrice 20 / 22
Înregistrari
Date personale ca înregistrari
data Person = Person { f i rs tName : : String, lastName : : String, age : : I n t, he igh t : : Float, phoneNumber : : String, f l a v o r : : String}
Traian Florin S, erbanut,a Ioana Leus, tean (UB) PD—Tipuri date algebrice 21 / 22
Înregistrari
Utilizare
Putem folosi atât forma algebrica cât s, i cea de înregistrare
i o n e l = Person " Ion " " Ionescu " 20 175.2" 0712334567 " " Caramel "
g i g e l = Person { f i rs tName = " Gheorghe ", lastName=" Georgescu ", age = 30 , he igh t = 192.3, phoneNumber = " 0798765432 ", f l a v o r = " V a n i l i e " }
Putem folosi s, i pattern-matching
Proiect,iile sunt definite automat; sintaxa specializata pentru actualizari
nextYear : : Person −> PersonnextYear person = person { age = age person + 1 }
Traian Florin S, erbanut,a Ioana Leus, tean (UB) PD—Tipuri date algebrice 22 / 22