CSE399: Advanced ProgrammingHandout 3PolymorphismThe Length Function is Polymorphiclength :: [a] -> Intlength [] = 0length (x:xs) = 1 + length xsThe “a” in the type of leng th is a placeholder that can bereplaced with any typ e when le ngth is applied.length [1,2,3] ⇒ 3length ["a","b","c"] ⇒ 3length [[1],[],[2,3]] ⇒ 3PolymorphismMany of Haskell’s predefined functions are polymorphic(++) :: [a] -> [a] -> [a]id :: a -> ahead :: [a] -> atail :: [a] -> [a][] :: [a] -- interesting!Quick check: what is the type of tag1 ?tag1 x = (1,x)Polymorphic Data StructuresPolymorphic functions — functions that can operate on anytype of data — are often associated w ith polymorphic datastructures — structures that can contain any type of data.The previous examples involved lists and tuples. In particular,here are the types of the list and tuple constructors:(:) :: a -> [a] -> [a](,) :: a -> b -> (a,b)Note the way that the tupl ing operator i s identified, whichgeneralizes to (,,), (,,,), etc. When we write (1,2,3,4),we really mean (1,(2,( 3,4))).We can also define new polymorphic data structures...A User-Defined Polymorphic Data StructureThe type variable a on the left-hand-side of the = tellsHaskell that Maybe is a polymorphic data typ e:data Maybe a = Nothing | Just aNote the types of the constructors:Nothing :: Maybe aJust :: a -> Maybe aThus:Just 3 :: Maybe IntJust "x" :: Maybe StringJust (3,True) :: Maybe (Int,Bool)Just (Just 1) :: Maybe (Maybe Int)Maybe May Be UsefulThe most common use of Maybe is with a function that“may” return a useful value, but may also fail.For example, the division operator div in Haskell will cause arun-time error if its second argument is zero. Thus we maywish to define a safe divisi on function, as follows:safeDivide :: Int -> Int -> Maybe IntsafeDivide x 0 = No thingsafeDivide x y = Ju st (x ‘div‘ y)Higher-Order FunctionsAbstraction Over Recursive DefinitionsRecall from Section 4.1:transList :: [Vertex] -> [Point]transList [] = []transList (p:ps) = trans p : transList ps(where trans converts ordinary cartesian coordinates intoscreen coordinates).Also, from Chapter 3:putCharList :: [C har] -> [IO ()]putCharList [] = []putCharList (c:cs) = putChar c : putCharList csThese definitions are very similar. Indeed, the only thingdifferent about them (besides the variable names) is thefunction trans vs. the function putCha r.We can use the abstraction principl e to take advantage ofthis regularity.Abstraction Yields mapSince trans and putChar are the differing elements, theyshould be arguments to the abstraction. In other words, wewould like to define a function — let’s call it map — such thatmap trans behaves like transList and map putChar behaveslike putCharList.No problem:map f [] = []map f (x:xs) = f x : map f xsNow i t is easy to redefine transL ist and p utCharLis t interms of map:transList xs = map tran s xsputCharList cs = map putChar csmap i s PolymorphicThe great thing about map is that it is p olymorphic. Its mostgeneral (or principal) type is:map :: (a->b) -> [a] -> [b]Whatever type is instantiated for the type variable a mustbe the same at both instances of a, and similarly for b.For example, since trans :: Vertex -> Point, we havemap trans :: [Vertex] -> [Poin t]and since putChar :: Char -> IO (),map putChar :: [Char] -> [IO ()]Digression: Arithmetic SequencesHaskell provides a convenient special syntax for lists ofnumbers obeying s imple rules:[1 .. 6] ⇒ [1,2,3,4,5,6][1,3 .. 9] ⇒ [1,3,5,7,9][5,4 .. 1] ⇒ [5,4,3,2,1][2.4, 2.1 .. 0.3] ⇒ [2.4, 2.1, 3.8, 3.5, etc.]Another Example of Mapcircles :: [Shape]circles = map circle [2.4, 2.1 .. 0.3]Now let’s draw them...Digression: zippingAnother useful higher-order function:zip :: [a] -> [b] -> [(a,b)]zip (a:as) (b:bs) = (a,b) : zip as bszip _ _ = []For example:zip [1,2,3] [True,False,False]⇒ [(1,True) , (2,False), (3,False)]Quick check: What does zip [1..3] [1..5] yield?Coloring Our CirclescolCircles :: [(Color,Shape)]colCircles = zip [Red,Blue,Green,Cyan,Red,Magenta,Yellow,White]circlesDrawing Colored ShapesdrawShapes :: Window -> [(Color,Shape)] -> IO ()drawShapes w css =sequence_ (map aux css)where aux (c,s) =drawInWindow w(withColor c(shapeToGraphic s))Recall from Chapter 3 that sequence_ takes a list of IO()actions and returns an IO() action that performs all theactions in the list in sequence.The Main Actiong = do w <- openWin dow "Bulls eye" (600,600)drawShapes w colCirclesk <- getKey wcloseWindow wmain = runGraphics gThe ResultWhen to Define Higher-Order FunctionsRecognizing repeating patterns is the key, as we did for map.As another example, consider:listSum [] = 0listSum (x:xs) = x + listSum xslistProd [] = 1listProd (x:xs) = x * listProd xsNote the similarities. Also note the differences (0 vs. 1 and +vs. *): it is these that will become parameters to theabstracted function.FoldAbstracting out the differences (op and i nit) le aves thiscommon part:fold op init [] = initfold op init (x:xs) = x ‘op‘ fold op init xsWe recover listSum and listProd by instantiating fold withthe appropriate parameters:listSum xs = fold (+) 0 xslistProd xs = fold (*) 1 xsNote that fold is p olymorphic:fold :: (a -> b -> b) -> b -> [a] -> bTwo Folds Are Better Than OneThe fold function is predefined in Haskell, but it is actuallycalled foldr, because it “folds from the right.” That is:foldr op init (x1 : x2 : ... : xn : [] )⇒ x1 ‘op‘ (x2 ‘op‘ (...(xn ‘op‘ init)...))There is another predefined function foldl that “folds fromthe left”:foldl op init (x1 : x2 : ... : xn : [] )⇒ (...((ini t ‘op‘ x1) ‘op‘ x2)...) ‘op‘ xnTwo Folds Are Better Than OneWhy two folds? Because sometimes using one can be moreefficient than the other. For example:foldr (++) [] [x,y,z] ⇒ x ++ (y ++ z)foldl (++) [] [x,y,z] ⇒ (x ++ y) ++ zThe former is considerably more efficient than the latter (asdiscussed in the book); but this is not always the case —sometimes foldl is more efficient than foldr. Choose wisely!Another Application of Fol dWe have seen the function sequen ce_, which takes a l ist ofactions of type IO() and produces a single action of typeIO().We can define sequence_ in terms of >> and foldl as follows:sequence_ :: [IO ()] -> IO ()sequence_ acts = foldl (>>) (return ()) actsReversing a ListObvious but inefficient (why?):reverse [] = []reverse (x::xs) = revers e xs ++ [x]Much better (why?):reverse xs = rev [] xswhere rev acc [] = accrev acc (x:xs) = rev (x:acc)