CS 345 slide 193 Spring 200510 March 2005Algebraic types with Field LabelsAs an alternative to the positional notation shownabove, algebraic types’ fields can be assigned labels(as in C and Pascal).For example,> data Time> = HMS { hr, min :: Int, sec :: Float }The field labels serve as selector functions; theirtypes arehr, min :: Time -> Intsec :: Time -> Floatso toSeconds could be defined thus:> toSeconds :: Time -> Float> toSeconds t> = fromInt (60 * (60 * hr t + min t)) + sec t(the first definition of toSeconds would also work).Compare with C:struct Time { int hr; int min; float sec; };float toSeconds( Time t ) {return (60 * (6 0 * t.hr + t.min) ) + t.sec;}Field labels are better than positional notation for typesthat have numerous fields —especially when softwaremodifications require changes in the type’s definition.CS 345 slide 194 Spring 200510 March 2005Algebraic types defined using field labels can havemultiple constructors. An example:> data Shape = Point { loc :: (Int,Int) }> | Square { loc :: (Int,Int),> size :: Int }> | Ellipse { loc :: (Int,Int),> size :: Int,> eccentricity :: Float> }> pt :: Shape> pt = Point { loc = (3,4) }> sq :: Shape> sq = Square { loc = (7,8), size = 25 }> el :: Shape> el = Ellipse { size = 10, eccentricity = 0.2 }Applying field-label functions:Main> loc pt(3,4)Main> size sq25Main> size ptProgram error: {Shape_Square_size pt}Main> loc elProgram error: Ellipse data constructor built missinga labelled fieldCS 345 slide 195 Spring 200510 March 2005Pattern-matching can simultaneously• distinguish between subtypes• bind parameter names to values of labeled fields> area :: Shape -> Float> area (Point {}) = 0> area (Square {size = s}) = fromInt s ^ 2> area (Ellipse {size = a, eccentricity = e})> = pi * fromInt a^2 * sqrt( 1 - e^2)Main> area pt0.0Main> area sq625.0Main> area el307.812If the same labeled field appears in all of an algebraictype’s subtypes, a function can access it withoutpattern-matching:> setLoc :: Shape -> (Int,Int) -> Shape> setLoc s xy = s { loc = xy }(This is not assignment: setLoc s xy creates a newShape identical to s except that its loc is xy.)> el' :: Shape> el' = setLoc el (40, 50)Main> loc el'(40,50)Main> area el'307.812CS 345 slide 196 Spring 200510 March 2005In Pascal and C/C++, the same flexibility can beobtained using variant records (in C they’re calledunions), which permit the number and kind of fieldsto differ among records of the same type:type ShapeKind = (Point, Square, Ellipse)type Shape = recordcase kind : ShapeKind ofPoint:Square:(size : int)Ellipse: (size: int, eccentricity: real)end;locX, locY : int endThe discriminator field is supposed to be tested incode that refers to variant fields:function area( s : Shape ) : realbegincase s.kind ofPoint: area := 0.0;Square: area := real(s.size)^2Ellipse: area := pi * real(s.size)^2 * sqrt( 1 – s.eccentricity^2)endendbut the matching is not checked by the compiler.It is obvious that this flexibility … gives rise toprogramming errors that are difficult to detect.In particular, it is now possible to assume insome part of a program that a variable is of acertain variant, whereas it actually is of anothervariant. This facility is therefore to be used withgreat caution. —N. Wirth.CS 345 slide 197 Spring 200510 March 2005Haskell’s sum-of-product types have no such loop-hole: The case identifiers are not mere data values,but constructor functions whose arguments’ typesare part of their definitions.(The concepts of algebraic types and pattern-matching have been ported into Pizza, anexperimental superset of Java.)Recursive Algebraic TypesExample: An expression is one of• a literal integer• a combination of two expressions with an operator(+ or –)This can be modeled by a recursive algebraic type:> data Expr = Lit Int> | Add Expr Expr > | Sub Expr Expr Examples:2 Lit 22+3 Add (Lit 2) (Lit 3)(3-1)+3 Add (Sub (Lit 3) (Lit 1)) (Lit 3)CS 345 slide 198 Spring 200510 March 2005Some functions on expressions• evaluate• show (i.e., produce a String representation)An evaluate function:> eval :: Expr -> Int> eval (Lit n) = n> eval (Add e1 e2) = eval e1 + eval e2> eval (Sub e1 e2) = eval e1 - eval e2A show function:> showExpr :: Expr -> String> showExpr (Lit n) = show n> showExpr (Add e1 e2)> = "(" ++ showExpr e1 ++> "+" ++ showExpr e2 ++ ")"> showExpr (Sub e1 e2)> = "(" ++ showExpr e1 ++> "-" ++ showExpr e2 ++ ")"Are recursive types something new?Not really— lists are a recursive algebraic type. Ifthey weren’t “built-in”, we could invent them:> data IntList = Empty | Cons Int IntListLike the built-in lists, algebraic types can bepolymorphic:> data List a = Empty | Cons a (List a )CS 345 slide 199 Spring 200510 March 2005Example: Binary Trees> data Tree a = Nil | Node a (Tree a) (Tree a)Some familiar functions for polymorphic Trees:> countTree, depth :: Tree a -> Int> countTree Nil = 0> countTree (Node _ t1 t2)> = 1 + countTree t1 + countTree t2> depth Nil = 0> depth (Node _ t1 t2)> = 1 + max (depth t1) (depth t2)Some Tree functions work only for certain types oftrees:> occurs :: Tree String -> String -> Int> occurs Nil p = 0> occurs (Node n t1 t2) p> = oneIf (n==p) + occurs t1 p + occurs t2 p> sumTree :: Tree Int -> Int> sumTree Nil = 0> sumTree (Node n t1 t2)> = n + sumTree t1 + sumTree t2> oneIf :: Num a => Bool -> a> oneIf True = 1> oneIf _ = 0CS 345 slide 200 Spring 200510 March 2005Recursive product types in Pascal and CHow can a Pascal or C programmer define a recursivetype?Suppose we want a Pascal type analogous to theHaskell type> data Expr = Lit Int> | Add Expr Expr> | Sub Expr ExprOur first attempt uses variant records.type ExpKind = (Lit, Add, Sub)type Expr = recordcase kind: ExpKind ofLit:(value: integer)Add:(op1,op2: Expr)Sub:(op1,op2: Expr)endend Every record of type Expr contains a record of typeExpr. Hence its size is infinite.A C example:struct tree { int label; tree left; tree right; };Every tree contains two trees, and hence is