### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# FUNCTIONAL LANGUAGES CS 457

PSU

GPA 3.91

### View Full Document

## 21

## 0

## Popular in Course

## Popular in ComputerScienence

This 413 page Class Notes was uploaded by Orrin Rutherford on Wednesday September 2, 2015. The Class Notes belongs to CS 457 at Portland State University taught by Staff in Fall. Since its upload, it has received 21 views. For similar materials see /class/168296/cs-457-portland-state-university in ComputerScienence at Portland State University.

## Reviews for FUNCTIONAL LANGUAGES

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/02/15

CS 457557 Functional Programming Lecture 10 Drawing Regions 102705 PSU CS457557 Fall39OSTolmach Pictures Drawing Pictures Pictures are composed of Regions Regions are composed of shapes Pictures add color and layering data Picture Region Color Region Picture Over Picture EmptyPic deriving Show 0 We need to use SOEGraphics but SOEGraphics has its own Region datatype import SOEGraphics hiding Region import qualified SOEGraphics as G Region 102705 PSU CS457557 Fall39OSTolmach Recall the Region Datatype data Region Shape Shape primitive shape Translate Vector Region translated region Scale Vector Region scaled region Complement Region inverse of a region Region Union Region union of regions Region Intersect Region intersection of regions Empty How do we draw things like the intersection of two regions or the complement of a region These are hard things to do ef ciently Fortunately the GRegion interface uses lowerlevel support to do us rus 102705 PSU CS457557 Fall39OSTolmach GRegi0n The G Region datatype interfaces more directly to the underlying hardware It is essentially a two dimensional array or bit map storing a binary value for each pixel in the window 102705 PSU CS457557 Fall39OSTolmach Ef cient BitMap Operations There is ef cient lowlevel support for combining bitmaps using a variety of operators For example for union These operations are fast but data space intensive and this space needs to be explicitly allocated and deallocated a job that seems easier in a much lowerlevel language 102705 PSU CS457557 Fall39OSTolmach GRegion Interface createRectangle Point gt Point gt GRegion createEllipse Point gt Point gt GRegion createPolygon Point gt GRegion andRegion GRegion gt GRegion gt GRegion orRegion GRegion gt GRegion gt GRegion xorRegion GRegion gt GRegion gt GRegion diffRegion GRegion gt GRegion gt GRegion drawRegion GRegion gt Graphic These functions are de ned in the SOEGraphics library module 102705 PSU CS457557 Fall39OSTolmach Drawing GRegi0n To draw things quickly turn them into a G Region then turn the G Region into a graphic object and then use all the machinery we have built up so far to display the object drawRegionInWindow Window gt Color gt Region gt IO drawRegionInWindow w c r drawInWindow w withColor c drawRegion regionToGRegion r o All we need to de ne then is regionToGRegion But rst let s de ne what it means to draw a picture 102705 PSU CS457557 Fall39OSTolmach Drawing Pictures 0 Pictures combine multiple regions into one big picture They provide a mechanism for placing one subpicture on top of another drawPic Window gt Picture gt IO drawPic w Region c r drawPic w p1 Over p2 drawRegionInWindow w c r do drawPic w p2 drawPic w p1 drawPic w EmptyPic return Note that p2 is drawn before p1 since we want p1 to appear over p2 102705 PSU CS457557 Fall39OSTolmach Summary 0 We have a rich calculus of Shapes which we can draw take the perimeter of and tell if a point lies within 0 We de ned a richer data type Region which allows more complex compositions intersection complement etc We gave Region a mathematical semantics as a set of points in the 2dimensional plane We de ned some interesting operators like containsR which is the characteristic function for a region The rich nature of Region makes it hard to draw efficiently so we use a lower level datatype G Region which relies on features like overwriting and explicit allocation and deallocation of memory We can think of Region as a highlevel interface to G Region that hides lowlevel details We enriched things even further with the Picture type which adds color and layering 102705 PSU CS457557 Fall39OSTolmach Turning a Region into a GRegion Experiment with a subset of task to illustrate an ef ciency problem Just consider rectangular shapes and scaling regToGRegO Region gt GRegion regToGRegO Shape Rectangle sx sy createRectangle trans sx2 sy2 trans sx2sy2 regToGRegO Scale xy r regToGRegO scaleReg xy r where scaleReg xy Shape Rectangle sx sy Shape Rectangle xsx ysy scaleReg xy Scale 3 r Scale 3 scaleReg xy r 102705 PSU CS457557 Fall39O5ToImaCh A Problem 0 Consider Scale x1y1 Scale x2y2 Scale x3y3 Shape Rectangle sx sy H o If the scaling is n levels deep how many traversals does regToGRegl perform over the Region tree 102705 PSU CS457557 FaII39O5TolmaCh We ve Seen This Before 0 Believe it or not we have encountered this problem before Recall the de nition of reverse reverse reverse xzxs reverse xs x where zs zs yzys zs y ys zs How did we solve this We used an extra accumulating parameter reverse xs revhelp xs where revhelp zs revhelp xzxs zs zs revhelp xs x zs 0 We can do the same thing for Regions 102705 PSU CS457557 Fall39OSTolmach Accumulate the Scaling Factor regToGRegl Region gt GRegion regToGRegl r rToNR 11 r where rToGR FloatFloat gt Region gt GRegion rToGR x1y1 Shape Rectangle sx sy createRectangle trans sxxl2 syy12 trans sxx12syyl2 rToGR x1y1 Scale x2y2 r rToGR xlx2yly2 r To solve our original problem repeat this for all the constructors of Region not just Shape and Scale We also need to handle translation as well as scaling 102705 PSU CS457557 FaII39O5TolmaCh Final Version regToGReg2 Vector gt Vector gt Region gt GRegion regToGReg2 loc sca Shape s shapeToGRegion loc sca s regToGReg2 xy sca Translate uv r regToGReg2 xu yv sca r regToGReg2 loc xy Scale uv r regToGReg2 loc xu yv r regToGReg2 loc sca Empty createRectangle 00 00 regToGReg2 loc sca r1 Union r2 let grl regToGReg2 loc sca r1 gr2 regToGReg2 loc sca r2 in orRegion grl gr2 Assuming of course that we can de ne shapeToGRegion Vector gt Vector gt Shape gt GRegion and write rules for Intersect Complement etc 102705 PSU CS457557 Fall39OSTolmach A Matter of Style While the function on the previous page shows how to solve the problem there are several stylistic issues that could make it more readable and understandable The style of de ning a function by patterns becomes cluttered when there are many parameters other than the one which has the patterns The pattern of explicitly allocating and deallocating bitmap G Region s will be repeated in cases for intersection and for complement so we should abstract it and give it a name 102705 PSU CS457557 Fall39OSTolmach Abstract the LowLevel BitMap Details primGReg loc sca r1 r2 op let grl regToGReg loc sca r1 gr2 regToGReg loc sca r2 in op grl gr2 102705 PSU CS457557 Fall39OSTolmach Redo with a Case Expression regToGReg Vector gt Vector gt Region gt GRegion regToGReg locxy scaab shape case shape of mem Shape s gt shapeToGRegion loc sca s mm mg Translate uv r gt regToGReg xu yv sca r Scale uv r gt regToGReg loc au bv r Empty createRectangle 00 00 r1 Union r2 primGReg loc sca r1 r2 orRegion r1 Intersect r2 primGReg loc sca r1 r2 andRegion Complement r gt primGReg loc sca winRect r diffRegion where winRect Region winRect Shape Rectangle pixelToInch xWin pixelToInch yWin regionToGRegion Region gt GRegion regionToGRegion r regToGReg 00 11 r 102705 PSU CS457557 FaII39O5TolmaCh Shape to GRegion Rectangle shapeToGRegionl Vector gt vector gt Shape gt GRegion shapeToGRegionl lxly sxsy Rectangle 51 52 createRectangle trans sl2 522 trans sl2sZ2 where trans xy xWin2 inchToPixel xlxsx yWin2 inchToPixel Ylysy s1 xWin yWin 102705 PSU CS457557 Fall3905Tolmach 18 Ellipse shapeToGRegionl lxly sxsy Ellipse r1 r2 createEllipse trans r1 r2 trans r1 r2 where trans xy xWin2 inchToPixel xlxsx yWin2 inchToPixel ylysy 92 102705 PSU CS457557 Fall39OSTolmach Polygon and RtTriangle shapeToGRegionl lxly sxsy Polygon pts createPolygon map trans pts where trans xy xWin2 inchToPixel xlxsx yWin2 inchToPixel ylysy shapeToGRegionl lxly sxsy RtTriangle 1 2 createPolygon map trans 00s100s2 where trans xy xWin2 inchToPixel xlxsx yWin2 inchToPixel ylysy PSU CS457557 Fall39OSTolmach 102705 A Matter of Style 2 shapeToGRegionl has the same problems as regToGRegl The extra parameters obscure the pattern matching There is a repeated pattern we should give it a name shapeToGRegion lxly sxsy s case s of Rectangle 1 2 gt createRectangle trans s12 sZ2 trans s12 s22 Ellipse r1 r2 gt createEllipse trans r1 r2 trans r1 r2 Polygon pts gt createPolygon map trans pts RtTriangle s1 2 gt createPolygon map trans 00sl00sZ Where trans xy xWin2 inchToPixel xlxsx yWin2 inchToPixel ylysy 102705 PSU CS457557 Fall39OSTolmach Drawing Pictures Sample Regions Picture gt IO p runGraphics do w lt openWindow quotRegion Testquot xWinyWin drawPic w p spaceClose w Rectangle 3 2 Ellipse 1 15 RtTriangle 3 2 Polygon 2525 300 17 10 1102 1520 102705 PSU CS457557 Fall39OSTolmach Sample Pictures regl r3 Union RtTriangle r1 Intersect Rectangle Complement r2 Union Ellipse r4 Polygon i Regmn Yes picl Region Cyan regl Mainl draw picl Recall the precedence of Union and Intersect 102705 F SU CS457557 FaII39O5Tolmach More Pictures let circle Shape Ellipse 05 05 square Shape Rectangle 1 1 in Scale 22 circle Union Translate 21 square Union Translate 20 square immm pic2 Region Yellow reg2 main2 draw pic2 102705 PSU CS457557 Fall39OSTolmach Another Picture pic3 pic2 Over picl main3 draw pic3 102705 PSU 08457557 Fall39OSTolmach 25 Separate Computation From Action oneCircle Shape Ellipse l l manyCircles Translate x0 oneCircle x lt 02 fiveCircles immm foldr Union Empty take 5 manyCircles pic4 Region Magenta Scale 025025 fiveCircles main4 draw pic4 102705 PSU CS457557 Fall3905Tolmach Ordering Pictures pictToList Picture gt ColorRegion pictToList EmptyPic pictToList Region c r cr pictToList p1 Over p2 pictToList p1 pictToList p2 pic6 pic4 Over pic2 Over picl Over pic5 pictToList pic6 gt Magenta YellowCyanCyan Recovers the Regions from top to bottom Possible because Picture is a datatype that can be analyzed 102705 PSU CS457557 FaII39OSTOImaCh Two ways of drawing a picture pictToList EmptyPic pictToList Region c r cr pictToList p1 Over p2 pictToList p1 pictToList p2 drawPic w Region 0 r drawRegionInWindow w c r drawPic w p1 Over p2 do drawPic w p2 drawPic w p1 drawPic w EmptyPic return Something interesting to prove drawPic w sequence map uncurry drawRegionInWindow w reverse pictToList 102705 PSU CS457557 Fall39OSTolmach Pictures that React Find the topmost Region in a Picture that covers the position of the mouse when a left button click appears Search the picture list for the first Region that contains the mouse position Rearrange the list bringing that one to the top adjust ColorRegion gt Vertex gt Maybe ColorRegion ColorRegion adjust p Nothing 1 adjust crregs p if r containsR p then Just cr regs else let hit rs adjust regs p in hit cr rs 102705 PSU CS457557 Fall39OSTolmach Doing it Nonrecursively adjust2 regs p case break r gt r containsR p regs of tophitrest gt Just hit toprest 1 gt Nothing 1 ThisisfronltheIPrethe break a gt Bool gt a gt aa Forexanu e break even 13547612 13547612 102705 PSU CS457557 Fall39OSTolmach Putting it all Together loop Window gt ColorRegion gt IO loop w regs do clearWindow w sequence drawRegionInWindow w c r cr lt reverse regs xy lt getLBP w case adjust regs pixelToInch x xWin2 pixelToInch yWin2 y of Nothing gt closeWindow w Just hit newRegs gt loop w hit newRegs draw2 Picture gt IO draw2 pic runGraphics do w lt openWindow quotPicture demoquot xWinyWin loop w pictToList pic 102705 PSU CS457557 Fall39OSTolmach Try it Out p1p2p3p4 Picture p1 Region Magenta r1 p2 Region Cyan r2 p3 Region Green r3 p4 Region Yellow r4 pic Picture pic foldl Over EmptyPic p1p2p3p4 main draw2 pic 102705 PSU CS457557 Fall39OSTolmach A Matter of Style 3 loop2 w regs do clearWindow w sequence drawRegionInWindow w c r cr lt reverse regs xy lt getLBP w let aux r r containsR pixelToInch x xWin2 pixelToInch yWin2 y case break aux regs of gt closeWindow w tophitbot gt loop w hit topbot draw3 pic runGraphics do w lt openWindow quotPicture demoquot xWinyWin loop2 w pictToList pic 102705 PSU CS457557 Fall39OSTolmach CS 457557 Functional Programming Lecture 3 IO Actions Graphics 092005 PSU CS457557 Fall3905 Tolmach Can we be imperative All the programs we have seen so far have no sideeffects That is programs are executed only for their values But sometimes we want our programs to affect the real world reading printing drawing a picture controlling a robot etc Yet IO operations and other effectful operations don39t mix well with Haskell39s lazy evaluation because evaluation order is very complicated and hard to predict How can we reconcile purity and utility 092005 PSU CS457557 Fall3905 Tolmach Example Using the Trace facility Hugs has a builtin facility for wrapping an expression with a string that is to be printed whenever the expression is evaluated trace 2 String gt a gt a f x trace quotgoodbyenquot x1 a f trace quothellonquot 1 g x x trace quotgoodbyenquot 1 b g trace quothellonquot 1 Even if order of evaluation is not an issue being able to do IO would violate computation by calculation paradigm eg C X X where x trace quothinquot 1 versus c trace quothinquot 1 trace quothinquot 1 092005 PSU CS457557 Fall3905 Tolmach 3 IO Actions In Haskell pure values are separated from worldly actions in two ways Types An expression with type IO a has possible actions associated with its execution while returning a value of type a Syntax The do syntax performs an action and using layout allows one to sequence several actions 0 Example code to read a character echo it and return Boolean value indicating if it was a newline do 0 lt getChar putChar 0 return c 39n39 092005 PSU CS457557 Fall3905 Tolmach 4 092005 Some Prede ned IO Actions get one character from keyboard getChar IO Char write one character to terminal putChar Char gt IO get a whole line from keyboard getLine IO String read a file as a String readFile FilePath gt IO String write a String to a file writeFile FilePath gt String gt IO PSU CS457557 Fall3905 Tolmach The do Syntax Let act be an action with type IO a Then we can perform act retrieve its return value and sequence it with other actions by using the do syntax do val lt act the next action the action following that return x final action may return a value Note that all actions following val lt act can use the variable val The function return takes a value of type a and turns it into an action of type IO a Which does nothing but return the value 092005 PSU CS457557 Fall3905 Tolmach do Typing Details do lt putChar c return c 39n39 092005 PSU CS457557 Fall3905 Tolmach When are IO Actions Performed A value of type IO a is an action but it is still a value it will only have an effect when it is performed In Haskell a program s value is the value of the variable main in the module Main That value must have type IO a The associated action will be performed when the whole program is run In Hugs however you can type any expression to the Hugs prompt If the expression has type IO a it will be performed otherwise its value will be printed on the display There is no other way to perform an action well almost 092005 PSU CS457557 Fall3905 Tolmach Recursive Actions getLine can be de ned recursively in terms of simpler actions getLine IO String getLine do c lt getChar get a character if c 39n39 if it s a newline then return quotquot then return empty string else do 1 lt getLine otherwise get rest of line recursively return czl and return entire line 092005 PSU CS457557 Fall3905 Tolmach Actions are just values Actions are just like other firstclass values they can be passed returned stored etc For example it can be handy to build lists of actions eg putCharList String gt IO 1 putCharList cs putChar c c lt cs There39s a library function to convert this to a single action sequence IO a gt IO putStr String gt IO putStr s sequence putCharList 3 Remember actions are only executed at top level eg main putStr abc 092005 PSU CS457557 Fall3905 Tolmach 10 Example Unix wc Command The uniX wc word count program reads a le and then prints out counts of characters words and lines Reading the le is an action but computing the information is a pure computation Strategy Define a pure function that counts the number of characters words and lines in a string number of lines number of n number of words number of plus number of t Define an action that reads a file into a string applies the above function and then prints out the result 092005 PSU CS457557 Fall3905 Tolmach Implementation wcf IntIntInt gt String gt IntIntInt wcf ccwlc ccwlc wcf ccwlc 39 39 xs wcf cc1wllc xs wcf ccwlc 39t39 xs wcf cc1wllc xs wcf ccwlc 39n39 xs wcf cc1wllc1 xs wcf ccwlc x xs wcf cc1wlc xs wc IO wc do name lt getLine contents lt readFile name let ccwlc wcf 000 contents putStan The file name has putStan show cc characters putStan show w words putStan show lc lines 092005 PSU CS457557 Fall3905 Tolmach 092005 Example Run Maingt wc elegantProsetxt The file elegantProsetxt has 2970 characters 1249 words 141 lines Maingt PSU CS457557 Fall3905 Tolmach Graphics Actions Graphics windows are traditionally programmed using commands ie actions Some graphics actions relate to opening up a graphics window closing it etc Others are associated with drawing lines circles text etc 092005 PSU CS457557 Fall3905 Tolmach Hello World program using Graphics Library FEE1L ll111m This imports a library SOEGraphics which contains many functions import SOEGraphics mainO runGraphics do w lt openWindow quotFirst windowquot 300300 drawInWindow w text 100200 quothello worldquot k lt getKey w closeWindow w 092005 PSU CS457557 Fall3905 Tolmach Graphics Operators openWindow String gt Point gt IO Window Opens a titled Window of a particular size drawInWindow Window gt Graphic gt IO Displays a Draw value in a given Window Note that the return type is IO getKey Window gt IO Char Waits until a key is pressed and then returns the character associated with the key closeWindow Window gt IO Closes the Window runGraphics IO gt IO Required wrapper around graphics operations to initclose graphics system 092005 PSU CS457557 Fall3905 Tolmach 16 Mixing Graphics IO with Terminal IO spaceClose Window gt IO spaceClose w do k lt getKey w if k 39 39 then closeWindow w else spaceClose w mainl runGraphics do w lt openWindow quotSecond Programquot 300300 drawInWindow w text 100200 Hello Againquot spaceClose w 092005 PSU CS457557 Fall3905 Tolmach Drawing Primitive Shapes The Graphics libraries contain simple actions for drawing a few primitive shapes ellipse Point gt Point gt Graphic shearEllipse Point gt Point gt Point gt Graphic line Point gt Point gt Graphic polygon Point gt Graphic polyline Point gt Graphic From these we Will build much more complex drawing programs 092005 PSU CS457557 Fall3905 Tolmach Coordinate System Increasing Xaxis spinK Buysean 111 092005 PSU CS457557 Fall3905 Tolmach Example Program main2 runGraphics do w lt openWindow quotDraw some shapesquot 300300 drawInWindow w ellipse 00 5050 drawInWindow w shearEllipse 060 100120 150200 drawInWindow w withColor Red line 200200 299275 drawInWindow w polygon 100100150100160200 drawInWindow w withColor Green polyline 100200150200 160299100200 spaceClose w 09200g PSU CS457557 Fall3905 Tolmach The Result drawInWindow w ellipse 00 5050 drawInWindow w shearEllipse 060 100120 150200 drawInWindow w withColor Red line 200200 299275 drawInWindow w polygon 100100 150100 160200 drawInWindow w withColor Green polyline 100200150200 160299100200 092005 PSU CS457557 Fall3905 Tolmach More Complex Programs We d like to build bigger programs from these small EMF Warm pieces For example Sierpinski s Triangle a fractal consisting of repeated drawing of a triangle at successively smaller sizes As before a key idea is separating pure computation from graphics actions 092005 PSU CS457557 Fall3905 Tolmach Geometry of One Triangle xysize size2 size2 hyp2 Remember that y increases as we go down the page Xysize2 quot xsize2ysize2 xsizey xsize2y 092005 PSU CS457557 Fall3905 Tolmach Draw 1 Triangle fillTri x y size w drawInWindow w withColor Blue polygon xly 0quot xsizey xy size minSize 092005 PSU CS457557 Fall3905 Tolmach Sierpinski s Triangle sierpinskiTri w x y size if size lt minSize mwmm then fillTri x y size w else let size2 size div 2 xsize2y xsizey in do sierpinskiTri w x y size2 sierpinskiTri w x y size2 size2 sierpinskiTri w x size2 y size2 main3 runGraphics do w lt openWindow quotSierpinski39s Triquot 400400 sierpinskiTri w 50 300 256 spaceClose w 092005 PSU CS457557 Fall3905 Tolmach Questions Whats the largest triangle sierpinskiTri ever draws How do the big triangles appear 092005 PSU CS457557 Fall3905 Tolmach CS 457557 Functional Programming Lecture 7 Trees 101305 PSU CS457557 Fall 3905 Tolmach Trees Trees are important data structures in computer science Trees have interesting properties They usually are nite but statically unbounded in size They often contain other nontrivial types Within They are often polymorphic They may have differing branching factors They may have different kinds of leaf and branching nodes Lots of interesting things can be modeled as trees lists linear branching shapes see text programming language syntax trees In a lazy language it is possible to have infinite trees 101305 PSU CS457557 Fall 3905 Tolmach 101305 Examples List a Nil MkList a List a Tree a Leaf a Branch Tree a IntegerTree IntLeaf Integer IntBranch IntegerTree IntegerTree SimpleTree SLeaf SBranch SimpleTree SimpleTree ITree a ILeaf Tree a IBranch a ITree a FLeaf a FBranch b FancyTree a b FancyTree a b ITree a FancyTree a b PSU CS457557 Fall 3905 Tolmach Match up the Trees b 6a 6 9 IntegerTree a Tree I SimpleTree gt List a ITree o FancyTree a a 4 101305 PSU CS457557 Fall 3905 Tolmach Functions on Trees Transforming one kind of tree into another mapTree a gtb gt Tree a gt Tree b mapTree f Leaf x Leaf f x mapTree f Branch t1 t2 Branch mapTree f t1 mapTree f t2 Collecting the items in a tree fringe Tree a gt a fringe Leaf x x fringe Branch t1 t2 fringe t1 fringe t2 0 What kind of information is lost using fringe 101305 PSU CS457557 Fall 3905 Tolmach More Functions on Trees treeSize Tree a gt Integer treeSize Leaf x 1 treeSize Branch t1 t2 treeSize t1 treeSize t2 treeHeight Tree a gt Integer treeHeight Leaf x O treeHeight Branch t1 t2 1 max treeHeight t1 treeHeight t2 101305 PSU CS457557 Fall 3905 Tolmach Binary Search Trees InternalTrees values at internal nodes in sorted order Used for ef cient implementation of sets dictionaries etc Logarithmic access update in average case data ITree a ILeaf IBranch a ITree a ITree a elemTreezz Ord a gt a gt ITree a gt Bool elemTree v ILeaf False elemTree v IBranch w l r v w True I v lt w elemTree v 1 elemTree v r v gt w 101305 PSU CS457557 Fall 3905 Tolmach Building Search Trees insertTreeOrd a gt a gt ITree a gt ITree a insertTree v ILeaf IBranch v ILeaf ILeaf insertTree v IBranch w l r v lt w IBranch w insertTree v 1 r v gt w IBranch w l insertTree v r listToTree xs foldr insertTree ILeaf xs 3 listToTree 1435298 IBranch 8 IBranch 2 IBranch 1 ILeaf ILeaf IBranch 5 IBranch 3 ILeaf IBranch 4 ILeaf ILeaf ILeaf IBranch 9 ILeaf ILeaf 101305 PSU CS457557 Fall 3905 Tolmach Deleting Elements deleteTree Ord a gt a gt ITree a gt ITree a deleteTree v ILeaf ILeaf deleteTree v IBranch w l r v w glue 1 r v lt w IBranch w deleteTree v l r v gt w IBranch w l deleteTree v r glue ITree a gt ITree a gt ITree a glue ILeaf r r glue 1 r IBranch big 139 r where bigl39 largest 1 largest ITree a gt aITree a largest elem rest largest IBranch w l ILeaf wl largest IBranch w l r bigIBranch w l r39 where bigr39 largest r 10M3m5 Psucs45W557Fmro5Tmnmch 9 Arithmetic Expressons data Expr C Float Add Expr2 Expr2 Sub Expr2 Expr2 Mul Expr2 Expr2 Div Expr2 Expr2 Or using in x constructor names InfiX constructors begin with a colon z Whereas ordinary data Expr constructor functions begin with an uppercase character Expr Expr Expr 101305 PSU CS457557 Fall 3905 Tolmach Example c10 C8 c2 C7z C4 evaluate Expr gt Float evaluate C x x evaluate e1 e2 evaluate e1 evaluate evaluate e1 e2 evaluate e1 evaluate evaluate e1 e2 evaluate e1 evaluate evaluate e1 e2 evaluate e1 evaluate Maingt evaluate e1 420 101305 PSU CS457557 Fall 3905 Tolmach CS 457557 Functional Programming Lecture 12 Qualified Types and Type Classes 110805 PSU CS457 557 Fall3905 Tolmach The Haskell Class System Think of a qualified type as a type with extra requirements Types which meet those requirements have quotextraquot functionality A class definition defines the function signatures for the quotextraquot functionality An instance declaration defines the quotextraquot functionality for a particular type 110805 PSU CS457 557 Fall3905 Tolmach Why type classes Consider the elem function for searching a list elem X False elem X yzys X 22 y True otherwise X elem ys What should its type be Something like elem a gt a gt Bool But this is too general since elem only makes sense on lists whose members can be compared for equality What things can39t be Functions new data types for which 2 hasn39t been written Want the type of elem to re ect this restriction Solution define type classes and use them to describe restrictions 110805 PSU CS457 557 Fall3905 Tolmach Prototypical type class Eq 0 Class definitions specify which methods functions must be defined on the type for it to be a member of the class class Eq a where a gt a gt BOOl Qualified types include class constraints on type variables elem Eq a gt a gt a gt Bool and types like this will be automatically infered for function definitions that us 0 Type qualifiers on functions propagate with use elemAll Eq a gt a gt a gt Bool elemAll X yss all elem X yss find Eq aShow a gt a gt a gt String find X Xs X elem X 2 Found show X otherwise Can39t find show X 110805 PSU CS457 557 Fall3905 Tolmach 4 Instance Declarations Instance declarations allow us to add new types to a class data Color Red Green Blue instance Eq Color where Red Red True Green Green True Blue Blue True False Now we can use on Color values Blue Red False hasRed Color gt Bool hasRed cs Red elem cs 110805 PSU CS457 557 Fall3905 Tolmach Fancier instance definitions What about parameterized types Can they be instances Yes if properly qualified instance Eq a gt Eq Maybe a where Nothing Nothing True Just X Just y X y False Note that use of in body is at type a not Maybe a So instance definition must be qualified too we can only compare two Maybe a values if we can compare two a values The same idea works for lists and other container 110805 PSU CS457 557 Fall3905 Tolmach Fancier Class declarations A class can specify multiple methods and give default definitions for these methods class Eq a where x y Now we can use on any values of a type belonging to class Eq Instance declarations don39t have to define assuming that the default implementation is ok allDifferent allDifferent X y z a gt a gt Bool a gt a gt Bool not X y Eq a gt a gt a gt a gt Bool X y ampamp X z ampamp y z In fact Eq also contains a default method for 2 not X y Must define at least one of 2 or to avoid infinite loops Xzzy 110805 PSU CS457 557 Fall3905 Tolmach 7 Inheritance in Class Definitions We may want to use a class method when defining default operations for another class class Eq a gt Ord a where ltltgtgt a gt a gt Bool XltyxltyXy XgtyxgtyXy These definitions for lt and gt only make sense if is defined on type a This is what the Eq a gt qualifier means We say Ord a inherits from Eq a Think of classes as collections of types since any type belonging to Ord must belong to Eq we say that Ord is a subclass of Eq or Eq is a superclass of Ord Somewhat similar to obj ectoriented ideas but not quite the same 110805 PSU CS457 557 Fall3905 Tolmach 8 Parts of Some Prelude Classes Eq Ord Enumerable types class Enum a where toEnum Int gt a fromEnum a gt Int enumFromTo a gt a gt a gtgta bBjuusynum csugm brenumFromTo a b Viewable types class Show a where show a gt String Parseable types class Read a where read String gt a Type inferencer must rely on context to determine result type a 110805 PSU CS457 557 Fall3905 Tolmach Predefined and Derived Instances The Prelude already has appropriate instance definitions for the types and classes defined there Almost all types except IO gt belong to Eq Ord Show Read To put newly defined types into standard classes requires an instance declaration Writing these is typically straightforward but tedious For certain Prelude classes Haskell allows us to derive the instance definition for a new type automatically Eq Ord Enum Show Read Bounded Ix Example Uses of deriving classes data Color Red Green Blue deriving Eq data Exp 2 Int Int Plus Exp Exp Minus Exp Exp deriving EqShow 110805 PSU CS457 557 Fall3905 Tolmach Some numeric Classes slightly wrong class Eq a Show a gt Num a where a gta gta negate abs signum a gt a fromInteger Integer gt a class Num a gt Fractional a where agtagta recip a gt a fromRational Rational gt a class Num a Ord a gt Integral a where div mod a gt a gt a toInteger a gt Integer 110805 PSU CS457 557 Fall3905 Tolmach Numeric Types and Literals Classes form a hierarchy Omitting some intermediate Classes we have Int fixedprecision integers belongs to Integral Integer arbitraryprecision integers belongs to Integral Integral a gt Ratio a bdongSUFractional Rational Ratio Integer Float Doublelx ongtOFractional Literals have very general types for maximum exibility 3 EsyHUm csugar n fromInteger 3 314 EsyHUm csugar n fromRational 3l4lOO 110805 PSU CS457 557 Fall3905 Tolmach 12 Defining your own Classes 0 You can define your own Classes and add new or existing types to them Eg we had containsS Shape gt Point gt Bool containsR Region gt Point gt Bool Can abstract class PC t where point containment contains t gt Point gt Bool instance PC Shape where contains containsS instance PC Region where contains containsR 0 Now can write Rectangle 2 3 contains p uses containsS r1 union r2 contains p uses containsR 110805 PSU CS457 557 Fall3905 Tolmach 13 Implicit invariants of Type Classes When we define a type class especially those with multiple methods we often want some things to be true about the way the methods interact In Haskell we can t make these invariants explicit class Eq a where a gt a gt Bool X y not Xy Desirable invariants a ltgt b a a b ampamp b c gt a c But this is perfectly legal instance Eq Color where Red False Blue True 110805 PSU CS457 557 Fall3905 Tolmach CS 457557 Functional Programming Lecture 2 Haskell Basics Data Types Shapes 092005 PSU CS457557 Fall3905 Tolmach Booleans Type Boolean has constructors values True and False Relational operators return booleans lt gt lt gt Combinators on booleans ampamp not Examples Preludegt 5 gt 7 False Preludegt 1 False Preludegt 5 lt 7 ampamp 1 4 True 092005 PSU CS457557 Fall3905 Tolmach De nition by Cases File contents absolute x x lt O x gt 0 Session Maingt absolute 3 3 Maingt absolute 5 5 Maingt 092005 PSU CS457557 Fall3905 Tolmach Definition By Patterns Example on booleans myand True False False myand True True True myand False False False myand False True False The order of de nition matters Variables in Patterns match anything myand2 True True True myand2 x y False What happens if we reverse the order of the two equations above 092005 PSU CS457557 Fall3905 Tolmach Patterns On Lists File Contents hd xzxs x tl xzxs xs firstOf3 xyz x Hugs Session Maingt hd 123 1 Maingt firstOf3 123 1 Maingt firstOf3 l234 Program error firstOf3 1 2 3 4 owzmos PSLJCS45W557FaWOSTdnmch Rules for Patterns All the patterns on the left must have compatible types The cases should but are not required to be exhaustive There should usually be no ambiguity as to which case applies Ordering resolves ambiguity if there is any A Pattern is A variable A constructor applied to patterns A constant like 3 or A tuple of patterns 092005 PSU CS457557 Fall3905 Tolmach Recursion To obtain universal computing power we need a way to repeat computations Most languages support loops eg while b do 5 These are completely useless in a purely functional program Why Functional programs use recursion instead of iteration Each recursive activation of function has new set of formal parameters Function can compute something different each time it is called 092005 PSU CS457557 Fall3905 Tolmach Some Recursive Functions plus Int gt Int gt Int plus x y if x 0 then y else 1 plus x l y len a gt Int len O len xzxs 1 len xs even odd Int gt Bool even 0 True even n oddn l odd 0 False odd n evenn l 092005 PSU CS457557 Fall3905 Tolmach Local De nitions Local Definitions Where len2 O The orderoflocal len2 xzxs one z definitions does not matter even if they Where 2 19112 XS depend on each other one1 Indentation matters where f x y Functions 9 and h are local h W ere to the definition of f The 9 a function k is at the same habnn levelasf k u v w Rule of thumb De nitions at the same scope level should be indented equally far 092005 PSU 03457557 Fall3905 Tolmach Larger example Sorting Insertion sort sort sort hzt insert h sort t where insert x x insert x hzt x lt h xzhzt otherwise hinsert x t 092005 PSU CS457557 Fall3905 Tolmach Types of Errors Syntax errors use of symbols in unexpected places f x x0 x Maingt r Reading file quotlect01hsquot ERROR quotlect01hsquot line 36 Syntax error in input unexpected 39 Maingt Unde ned variables lastone2 head rev Maingt r Reading script file quotlect01hsquot ERROR quotlect01hsquot line 38 Undefined variable quotrevquot Maingt 092005 PSU CS457557 Fall3905 Tolmach Types of Errors cont Type errors plusone Int gt Int Maingt plusone 12 ERROR Type error in application expression plusone 12 term 12 type Int does not match Int 092005 PSU CS457557 Fall3905 Tolmach Types of Errors cont More type errors Preludegt t head head a gt a Preludegt head True ERROR Type error in application expression hd True term True type Bool does not match a Preludegt head 1 ERROR Illegal Haskell 98 class constraint in inferred type Expression head 1 Type Num a gt a 092005 PSU CS457557 Fall3905 Tolmach Overloading and Classes If we omitted the type contraint 0n difference difference x y if xgty then x y else y x Maingt type difference difference Ord a Num a gt a gt a gt a Maingt difference 3 4 1 Maingt difference 45 78 33 Maingt The classes 0rd and Num represent sets of types 092005 PSU CS457557 Fall3905 Tolmach De ning New Datatypes Ability to add new datatypes in a programming language is important Some important kinds of datatypes enumerated types records or products variant records or sums Haskell s data declaration provides many of these kinds of types in a uniform way which abstracts from their implementation details The data declaration defines a new type and a set of constructors for that type Constructors can be used to create new instances of the type and to patternmatch against existing instances 092005 PSU CS457557 Fall3905 Tolmach Records Example Complex Numbers Complex numbers in rectangular format data Complex Complex Float Float deriving Eq add Complex r1 i1 Complex r2 i2 Complex rlr2 ili2 mul Complex r1 i1 Complex r2 i2 Complex rlr2ili2 rli2r2il Note that Complex is used both to construct new values and to patternmatch existing ones Deriving clause automatically generates a structural equality operator Complex 20 30 Complex 20 30 gt True 092005 PSU CS457557 Fall3905 Tolmach Enumerations Example data Month Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec deriving EqEnumShow daysInMonth Sep 30 daysInMonth Apr 30 daysInMonth Jun 30 daysInMonth Nov 30 daysInMonth Feb 28 daysInMonth 31 Maingt Jun Sep JunJulAugSep 092005 PSU CS457557 Fall3905 Tolmach 17 data Temp freezing freezing freezing freezing kelvenize kelvenize kelvenize kelvenize 092005 F Float C Float K Float t t t K t C t F t Temp Variant Records Temp Fahrenheit Celsius Kelvin gt Bool t lt 320 t lt 00 t lt 2730 gt Temp K t K 2730 t kelvenize C t3209050 PSU CS457557 Fall3905 Tolmach Maybe is another useful variant data Maybe a Just a Nothing lookup a gt ab gt Maybe b lookup k lookup k k39vrest k kI Just v otherwise lookup k rest Nothing 092005 PSU CS457557 Fall3905 Tolmach 19 Shape types from the Text data Shape Rectangle Float Float Ellipse Float Float RtTriangle Float Float Polygon FloatFloat deriving Show Deriving Show tells the system to build a show function for the type Shape Using Shape Functions returning shape objects circle radius Ellipse radius radius square side Rectangle side side Is there anything unsatisfactory about this definition 092005 PSU CS457557 Fall3905 Tolmach 20 Functions over Shape Functions over Shape can be de ned using pattern matching area Shape gt Float area Rectangle 1 2 1 32 area Ellipse r1 r2 pi r1 r2 area RtTriangle 1 2 1 2 2 area Polygon v1pts polyArea pts where polyArea FloatFloat gt Float polyArea v2 v3 vs triArea v1 v2 v3 polyArea v3vs polyArea 0 Note use of prototypes Note use of nested patterns Note use of Wild card pattern matches anything 092005 PSU CS457557 Fall3905 Tolmach Poly ABCDEF Area AreaTriangle ABC AreaPolyACDEF B D 092005 PSU CS457557 Fall3905 Tolmach Calculating areas area Polygon ABCDEF polyArea BCDEF where v1 A triArea A B C polyArea CDEF where v1 A triArea A B C triArea A C D polyArea DEF where v1 A triArea A B C triArea A C D triArea A D E polyArea EF where v1 A triArea A B C triArea A C D triArea A D E triArea A E F polyArea F where v1 A triArea A B C triArea A C D triArea A D E triArea A E F 0 092005 PSU CS457557 Fall3905 Tolmach 23 TriArea v1 v2 v3 distBetween v1 v2 distBetween v2 v3 distBetween v3 v1 05abc in sqrt ss as bs c distBetween x1y1 x2y2 sqrt xl x2 2 yl y2 2 092005 PSU CS457557 Fall3905 Tolmach CS 457557 Functional Languages An Introduction to ControIParae Mark P Jones Portland State University A Silly Slow Program gtfibO O gt fib l l gt fib n fib n l fib n 2 gt nfib O l gt nfib l l gt nfib n l nfib n l nfib n 2 gt diffib n nfib n fib n gt main print diffib 38 Why is it Slow prompt ghc make parlhs 0 par prompt par RTS s 87403802 prompt cat parstat l6759034836 bytes allocated in the heap 11625744 bytes copied during GC scavenged 2884616 bytes copied during GC not scavenged 24576 bytes maximum residency 2 samples C INIT time OOs 003s elapsed MUT time 1705s 1725s elapsed GC time 021s 028s elapsed EXIT time 000s Total time l726s 000s elapsed 1756s elapsed prompt Introducing ControlParallel par a gt b gt b par 2 y is semantically just y but hints to the compiler that it might be useful to start evaluating x pseq a gt b gt b pseq x y is semantically just y but will evaluate 2 before returning a result A Silly Parallel Program gt fib O gt nfib O m gt diffib n let 1 nfib n gt r fib n gt in par 1 l r gt main print diffib 38 Does this Run Better prompt ghc make threaded parlalhs o parla prompt parla RTS s 87403802 prompt cat parlastat l6759034836 bytes allocated in the heap 11625760 bytes copied during GC scavenged 2884616 bytes copied during GC not scavenged 24576 bytes maximum residency 2 samples INIT time Q 00s 000s elapsed MUT time 1643s 1663s elapsed GC time 021s 028s elapsed EXIT time 000s Total time l664s 000s elapsed 169ls elapsed prompt On Multiple Cores prompt par1a RTS s N2 87403802 prompt cat parlastat 16759034636 bytes allocated in the heap 11618096 bytes copied during GC scavenged 2878584 bytes copied during GC not scavenged 24576 bytes maximum residency 2 samples C INIT time OOs 000s elapsed MUT time 1647s 1689s elapsed GC time 25s 033s elapsed CDC EXIT time OOs Total time 1673s 000s elapsed 1723s elapsed prompt A Different Silly Program gt fib O gt nfib O m gt diffib n let 1 nfib n gt r fib n gt in par r l r gt main print diffib 38 At Last a Speedup prompt ghc make threaded parlblhs o parlb prompt parlb RTS s N2 cat parlbstat 87403802 l6759227260 bytes allocated in the heap 12463976 bytes copied during GC scavenged 3158992 bytes copied during GC not scavenged 28672 bytes maximum residency 2 samples Total time 1675s INIT time 000s 000s elapsed MUT time 1654s 930s elapsed GC time 021s 025s elapsed EXIT time 000s 000s elapsed 9 56s elapsed prompt A More Robust Silly Program gt fib O gt nfib O m gt diffib n let 1 nfib n gt r fib n gt in par 1 pseq r 1 r gt main print diffib 38 10 A More Robust Silly Program gt fib O gt nfib O m gt diffib n let 1 nfib n gt r fib n gt in 1 par r pseq lr gt main print diffib 38 11 Consistent Speedup prompt par2 RTS s N2 cat par2stat 87403802 l6759225356 bytes allocated in the heap 12494824 bytes copied during GC scavenged 3179576 bytes copied during GC not scavenged 24576 bytes maximum residency 2 samples INIT time 000s 003s elapsed MUT time 1653s 966s elapsed GC time 021s 027s elapsed EXIT time 000s 000s elapsed Total time 1674s 995s elapsed prompt 12 Back to Fractals Leveraging Parallelism gt sample Grid Point gt gt Image color gt gt Grid color gt sample points image gt map map image points This looks like a good candidate for parallelization But how 14 ControlParallelStrategies type Strategy a a gt The result of a strategy is always except that it may do some work to evaluate the argument first using a gt Strategy a gt a e using 8 is semantically just the same as e except that it applies the strategy 8 15 ControlParallelStrategies class NFData a where rnf Strategy a rnf is a strategy for reducing values to normal form instance NFData Int where m instance NFData Bool where m instance NFData a gt NFData a where m 16 ControlParallelStrategies parList Strategy a gt Strategy a Evaluate a list in parallel using the argument strategy for each element parMap Strategy b gt a gt b gt a gt b parMap s f XS map f xs using parList s 17 Adopting a Strategy gt sample NFData color gt gt Grid Point gt gt Image color gt gt Grid color gt sample points image gt parMap rnf map image points also need to add an NFData color context to the type of draw 18 Adopting a Strategy gt sample NFData color gt gt Grid Point gt gt Image color gt gt Grid color gt sample points image gt map map image points gt using parList rnf also need to add an NFData color context to the type of draw 19 Adopting a Strategy gt sample Grid Point gt gt Image color gt gt Grid color gt sample points image gt map map image points draw pal grid render render sample grid fraoImage pal gt using parList rnf 20 Before prompt ghc make threaded parfraclhs o parfrac prompt parfrac RTS s N1 cat parfracstat 8746623328 bytes allocated in the heap 113302744 bytes copied during GC scavenged 14617944 bytes copied during GC not scavenged 192512 bytes maximum residency 120 samples INIT time 000s 000s elapsed MUT time 838s 888s elapsed GC time 065s 069s elapsed EXIT time 000s 000s elapsed Total time 903s 957s elapsed prompt 21 After prompt ghc make threaded parfraclhs o parfrac prompt parfrac RTS s Nl cat parfracstat 8863473948 bytes allocated in the heap 180756008 bytes copied during GC scavenged 14648536 bytes copied during GC not scavenged 352256 bytes maximum residency l95 samples INIT time 000s 000s elapsed MUT time 904s 956s elapsed GC time l05s 110s elapsed EXIT time 000s 000s elapsed Total time 1008s 1066s elapsed prompt 22 After N2 prompt ghc make threaded parfraclhs o parfrac prompt parfrac RTS s N2 cat parfracstat 9593542412 bytes allocated in the heap 355170160 bytes copied during GC scavenged 14272640 bytes copied during GC not scavenged 1351680 bytes maximum residency 335 samp1es INIT time 000s 000s elapsed MUT time 972s 557s elapsed GC time 171s 177s elapsed EXIT time 000s 000s elapsed Total time 1143s 734s elapsed prompt 23 Conclusions ltgt ControParalle provides simple mechanisms that can be used to annotate code with hints for parallel execution and potential speedup on multiprocessormulticore machines ltgt Experimentation may be required to determine best uses for annotations ltgt Algorithm Strategy Parallelism lt gt Further reading RWH Chapter 24 24 CS 457557 Functional Languages IO Actions in Haskell Mark P Jones Portland State University Question If functional programs don t have any sideeffects then how can we ever do anything useful 10 A quick overview Computing by calculating 1 3 ltgt take 32 iterate 2 1 lt gt color red translate 12 circle 3 lt9 leftTree beside rightTree Q getChar gtgt putChar Demo of Mac OS X Automator IO Actions action ID a ltgt An IO action is a value of type IO T ltgtgt T is the type of values that it produces 5 IO Actions action a function I a gt b If action IO a and function a gt IO b then action gtgt function IO b The New Haskell Logo Building Blocks gtgt IO a gt IO b gt IO b p gtgt q is an IO action in which the output of p is ignored by q pgtgtq pgtgt Xgtq where X does not appear in q Building Blocks return a gt IO a An IO action that returns its input with no actual IO behavior Building Blocks inIO a gt b gt a gt IO b An action inIO f applies the function fto each input of type a and produces outputs of type b as its results 10 Building Blocks mapM a gt IO b gt a gt IO b An action mapM ftakes a list of inputs of type a as its input runs the action fon each element in turn and produces a list of outputs of type b 11 Building Blocks mapM a gt IO b gt a gt IO An action mapM f takes a list of inputs of type a as its input runs the action f on each element in turn and produces a result of type as output 12 Terminal Output putStr String gt IO putStan String gt IO An action putStr stakes a String input and outputs it on the terminal producing a result of type putStan s does the same thing but adds a trailing new line 13 Terminal Output print Show a gt a gt IO A print action takes a value whose type is in Show and outputs a corresponding String on the terminal 14 Special Treatment of IO lt gt The main function in every Haskell program is expected to have type IO If you write an expression of type IO t at the Hugs prompt it will be evaluated as a program and the result discarded If you write an expression of some other type at the Hugs prompt it will be turned in to an IO program using print Show a gt a gt IO print putStan show If you write an expression e of type IO t at the GHCi prompt It Will treat It as e gtgt print 15 Web Actions The WebActions module provides the following IO actions getText URL gt IO String getByteString 39 URL gt IO ByteString writeByteString String gt ByteString gt IO downloadTo 39 FilePath gt URL gt IO getTags 39 URL gt IO Tag getHrefs 39 URL gt IO URL getHTML 39 URL gt IO TagTree getXML 39 URL gt IO Content 16 Viewing a Webpage gtgt getText gtgt putStr 17 Counting Characters return url gtgt getText gtgt inIO length gtgt print 18 Counting Lines return url gtgt getText gtgt inIO length lines gtgt print 19 Viewing a Webpage as Tags return url gtgt getTags gtgt inIO unlines map Show gtgt putStr 20 Extracting Hyperreferences getHrefs URL gt IO URL getHrefs url getTags url gtgt ts gt return link TagOpen a attrs lt ts quothrefquot link lt attrs 21 Downloading From a Webpage return url gtgt getHrefs gtgt inIO filter isSuffixOf quothsquot gtgt mapM downloadTo quotsourcequot 22 Implementing downloadTo downloadTo FilePath gt URL gt IO downloadTo dir url getByteString url gtgt writeByteString dir ltgt urlName url urlName String gt String urlName reverse takeWhile 3939 reverse 23 Visualizing a Webpage return url gtgt getTags gtgt inIO tagTree gtgt inIO listToDot quotrootquot gtgt writeFile quottreedotquot 24 IOActions Primitives putChar putStr putStan print getChar getLine getContents readFile writeFile Char gt String gt String gt Show a gt IO Char IO String IO String String gt String gt IO String IO 25 quotcon nued getDirectoryContents getDirectoryPaths getCurrentDirectory getHomeDirectory doesFileExist doesDirectoryExist createDirectory getFiles getDirectories getArgs getProgName getEnv runCommand String gt FiIePath gt FiIePath gt IO FilePath IO FilePath FiIePath gt FiIePath gt FiIePath gt FiIePath gt FiIePath gt IO String IO String IO IO IO IO IO IO IO FiIePath FiIePath B001 B001 FiIePath FiIePath String gt IO String FiIePath gt IO ExitCode 26 Exercises ltgt Load up IOActionshs and write IO Actions to answer the following How many Haskell source files are there in the current directory How many lines of Haskell source code are in the current directory What is the largest Haskell source file in the current directory Copy the largest Haskell source file in the current directory into Largesths 27 Visualizing a File System data FileSystem File FilePath Folder FilePath FileSystem Foldep FilePath deriving Show instance Tree FileSystem where m Instance LabeledTree FileSystem where m 28 quotcon nued getFileSystemDir Int gt FilePath gt FilePath gt IO FileSystem getFileSystemDir n path name n lt 1 return Foldep name otherwise getDirectoryContents path gtgt inIO filter not dotFile gtgt mapM getFileSystemIn n l path gtgt inIO Folder name getFileSystemln Int gt FilePath gt FilePath gt IO FileSystem getFileSystemln n parent child doesDirectoryEXist path gtgt b gt case b of True gt getFileSystemDir n path child False gt return File child where path parent ltgt child 29 Visualizing a FiIeSystem return quothaskore Vintage Olquot gtgt getFileSystem 4 gtgt inIO toDot gtgt writeFile quottreedot Alternative Notation The pipelined style for writing IO Actions isn t always so convenient Need to refer to an input at multiple stages of a pipeline Nonlinear flow error handling Recursion Loops Shorter lines 31 donotation Syntactic sugar for writing IO actions do p1 P2 Pn is equivalent to p1 gtgt p2 gtgt gtgt pn and can also be written do I01 I02 on or do I31 I32 Ion 32 Extending donotation We can bind the results produced by IO actions variables using an extended form of donotation For example all eneratorsquot should have do x1 lt pa 9 the same indentation Xn lt pn q last item must be an expression is equivalent to p1 gtgt X1 gt variables introduced in a generator are in scope for the rest of the expression p gt gt Xn gt The v ltquot portion of a Cl generator is optional and defaults to ltquot if 33 Defining mapM and mapM mapM mapM mapM mapM mapM f mapM f f f 1 Xsz 1 Xsz a gt IO b gt return f X gtgt mapM f XS a gt IO a gtIO b gt return f X mapM f XS yzys a gtIO b gtgt y gt gtgt ys gt return 34 Defining mapM and mapM mapM a gt IO b gt a gt IO mapM f return mapM f Xsz do f X mapM f XS mapM a gtIO b gt a gtIO b mapM f return mapM f Xsz do y lt f X ys lt mapM f Xs return yzys 35 More examples getChar ltgt A simple primitive for reading a single character getChar IO Char ltOgt A simple example echo IO a echo do c lt getChar putChar c echo 36 Reading a Complete Line getLine IO String getLine do c lt getChar if c39n39 then return else do cs lt getLine return ccs 37 Alternative getLine IO String getLine loop loop String gt IO String loop cs do c lt getChar case c of 39n39 gt return reverse cs 39b39 gt case cs of gt loop cs ccs gt loop cs c gt loop ccs 38 There is No Escape There are plenty of ways to construct expressions of type IO t ltgt Once a program is tainted with IO there is no way to shake it of quot lt9 For example there is no primitive of type IO t gt t that runs a program and returns its result 39 The Real Primitives Many of the IO functions that we ve introduced can be defined in terms of other IO functions The fundamental primitives are return a gt IO a gtgt IO a gt a gt IO b gt IO b putChar Char gt IO getChar IO Char 40 Generalizing lt gt We can define versions of return and gtgt for other types return a gt List a return X X gtgt List a gt a gt List b gt List b xs gtgtf yxltxsyltfx ltOgt I can feel a type class coming on 41 Further Reading Tackling the Awkward Squad monadic inputoutput concurrency exceptions and foreignlanguage calls in Haskellquot Simon Peyton Jones 2005 Imperative Functional Programmingquot Simon Peyton Jones and Philip Wadler POPL 1993 42 CS 457557 Functional Programming Lecture 8 Regions 101305 PSU CS457557 Fall3905 Tolmach The Region Data Type A region represents an area on the twodimensional Cartesian plane It is represented by a treelike data structure data Region Shape Shape primitive shape Translate Vector Region translated region Scale Vector Region scaled region Complement Region inverse of region Region Union Region union of regions Region Intersect Region intersection of regions Empty deriving Show type Vector Float Float 101305 PSU CS457557 Fall3905 Tolmach Questions about Regions Why is Region treelike What is the strategy for writing functions over regions Is there a foldfunction for regions How many parameters does it have What is its type Can one define infinite regions What does a region mean 101305 PSU CS457557 Fall3905 Tolmach Sets and Characteristic Functions How can we represent an in nite set in Haskell Eg the set of all even numbers the set of all prime numbers We could use an in nite list but then searching it might take a very long time Membership becomes semidecidable The characteristic function for a set containing elements of type 2 is a function of type 2 gt Bool that indicates Whether or not a given element is in the set Since that information completely characterizes a set we can use it to represent a set type Set a a gt Bool For example even Set Integer Integer gt Bool even x x mod 2 101305 PSU CS457557 Fall3905 Tolmach Combining Sets 0 If sets are represented by characteristic functions then how do we represent the union of two sets intersection of two sets complement of a set Inclass exercise de ne the following Haskell functions sl union 2 1 intersect 2 complement s We will use these later to de ne similar operations on regions PSU CS457557 Fall3905 Tolmach 5 101305 Why Regions Regions as de ned in the text are interesting because They allow us to build complex shapes from simpler ones They illustrate the use of treelike data structures They solve the problem of having rectangles and ellipses centered about the origin Their meaning can be given as characteristic functions since a region denotes the set of points contained within it 101305 PSU CS457557 Fall3905 Tolmach Characteristic Functions for Regions We de ne the meaning of regions by a function containsR Region gt Coordinate gt Bool Here type coordinate Float Float Note that containsR r Coordinate gt Bool which is a characteristic function So containsR gives meaning to regions Another way to see this containsR Region gt Set Coordinate We can de ne containsR recursively using pattern matching over the structure of a Region Since the base cases of the recursion are primitive shapes we also need a function that gives meaning to primitive shapes we will call this function containsS 101305 PSU CS457557 Fall3905 Tolmach Rectangle Rectangle 1 2 containsS xy let t1 312 t2 322 in t1ltx ampamp xltt1 ampamp t2lty ampamp yltt2 sl lt 101305 PSU CS457557 Fall3905 Tolmach Ellipse Ellipse r1 r2 containsS xy xrl quot2 yr2quot2 lt 101305 PSU CS457557 Fall3905 Tolmach The Left Side of a Line For a ray directed from point a to point b a point p is to the left of the ray facing from a to b When p 101305 0 px py isLeftOf px py Coordinate gt Ray gt Bool isLeftOf axay bxby let st px ax py ay uv pxbx pyby in sv gt tu type Ray Coordinate Coordinate PSU CS457557 Fall3905 Tolmach 1O Polygon A point p is contained Within a convex polygon if it is to the left of every side When they are followed in counterclockwise order Polygon pts containsS p let shiftpts tail pts head pts leftOfList map isLeftOfp p zip pts shiftpts in foldr ampamp True leftOfList 101305 PSU CS457557 Fall3905 Tolmach Right Triangle RtTriangle 1 2 containsS p Polygon 00sl0032 containsS p 052 101305 PSU CS457557 Fall3905 Tolmach Putting it all Together containsS Shape gt Coordinate gt Bool Rectangle 1 2 containsS xy let t1 312 t2 s22 in t1ltx ampamp xltt1 ampamp t2lty ampamp yltt2 Ellipse r1 r2 containsS xy xrl 2 yr2 2 lt 1 Polygon pts containsS p let shiftpts tail pts head pts leftOfList map isLeftOfp p zip pts shiftpts in foldr ampamp True leftOfList RtTriangle 1 2 containsS p Polygon 00sl0032 containsS p 101305 PSU CS457557 Fall3905 Tolmach De ning containsR using Recursion containsR Region gt Coordinate gt Bool Shape s containsR p s containsS p Translate uv r containsR xy r containsR x uy v Scale uv r containsR xy r containsR xuyv Complement r containsR p not r containsR p r1 Union r2 containsR p r1 containsR p r2 containsR p r1 Intersect r2 containsR p r1 containsR p ampamp r2 containsR p Empty containsR p False 101305 PSU CS457557 Fall3905 Tolmach An Algebra of Regions Note that for any r1 r2 and r3 r1 Union r2 Union r3 containsR p if and only if r1 Union r2 Union r3 containsR p which we can abbreviate as r1 Union r2 Union r3 E rl Union r2 Union r3 In other words Union is associative We can prove this fact Via calculation 101305 PSU CS457557 Fall3905 Tolmach Proof of Associativity r1 Union r2 Union r3 containsR p r1 containsR p r2 Union r3 containsR p r1 containsR p r2 containsR p r3 containsR p rl containsR p r2 containsR p r3 containsR p rl Union r2 containsR p r3 containsR p rl Union r2 Union r3 containsR p Note that the proof depends on the associativity of which can also be proved by calculation but we take as given 101305 PSU CS457557 Fall3905 Tolmach 16 More Axioms There are many useful axioms for regions 1 Union and Intersect are associative 2 Union and Intersect are commutative 3 Union and Intersect are distributive 4 Empty and univ Complement Empty are zeros for Union and Intersect respectively r Union Complement r E univ and r Intersect Complement r Empty This set of axioms captures What is called a boolean algebra 101305 PSU CS457557 Fall3905 Tolmach CS 457557 Functional Programming Lecture 6 Perimeters of Shapes 100605 PSU CS457557 Fall3905 Tolmach The Perimeter of a Shape s2 To compute the perimeter we need a function with four equations 1 for each Shape constructor The rst three are easy perimeter Shape gt Float perimeter Rectangle 1 2 perimeter RtTriangle 1 2 1 2 sqrt slA232 2 perimeter Polygon pts foldl 0 sides pts 0 This assumes that we can compute the lengths of the sides of a polygon This shouldn t be too dif cult since we can compute the distance between two points with distBetween 2sl32 100605 PSU CS457557 Fall3905 Tolmach Recursive Def n of Sides sides vertex gt Side sides 1 sides vzvs aux v vs where aux v1 v2vs distBetween v1 v2 aux v2 vs aux vn distBetween vn v aux vn distBetween vn v 0 But can we do better Can we remove the direct recursion as a seasoned functional programmer might 100605 PSU CS457557 Fall3905 Tolmach Visualize What s Happening B D The list ofvertices is vs ABCDE We need to compute the distances between the pairs of points AB BC CD DE and EA Can we compute these pairs as a list AB BC CD DE EA Yes by zipping the two lists ABCDE and BCDEA as follows zip vs tail vs head vs 100605 PSU CS457557 Fall3905 Tolmach Zipping Lists The zip function already in the library can be written zip a gt b gt ab zip xzxs yzys xy zip xs ys zip l What happens if the lists are of unequal length This leads to a new version of sides sides Vertex gt Side sides vs map d zip vs tail vs head vs where d v1v2 distBetween v1 v2 This is more elegant than the explicit recursion but still verbose in particular the need to de ne d is sad We can avoid this in at least two ways 100605 PSU CS457557 Fall3905 Tolmach 5 More variants of sides I The prede ned uncurry function converts any curried binary function or operator to a singleargument version on pairs uncurry a gt b gt c gt ab gt c uncurry f xy f x y allowing us to write sides vs map uncurry distBetween zip vs tail vs head vs II There is a predefined function zipWith that is just like zip except that it applies its rst argument a curried function to each pair of values For example zipWith 123 456 579 So we can write sides vs zipWith distBetween vs tail vs head vs 100605 PSU CS457557 Fall3905 Tolmach Perimeter of an Ellipse There is one remaining case the ellipse The perimeter of an ellipse is given by the summation of an in nite series For an ellipse with radii r1 gt r2 p 27t1 11 2 si where s1 14 e2 si si1 2i12i3 e2 for i gt 1 4i2 e sqrt r12 r22 r1 leen si 1t 1s easy to compute sm 100605 PSU CS457557 Fall3905 Tolmach Computing the Series nextEl Float gt Float gt Float gt Float nextEl e s i s2i 12i 3e 2 4iA2 Now we want to compute s1 s2 s3 S 1 S 2i12i3 f2 1 1 To x e let s de ne 4i2 aux s i nextEl e s i So we would like to compute Can we capture 81 I this pattern f 31 2 fs 4fff812 3 3 100605 PSU CS457557 Fall3905 Tolmach Scanl scan from the left 0 Yesungthe1nede nedfhnc on scanl scanl a gt b gt a gt a gt b gt a scanl f seed seed scanl f seed xzxs seed scanl f newseed xs where newseed f seed x Forexanu e scanl 0 123 I O o 1 1 1 2 3 3 3 6 0 ll 3 6 Using scanl the result we want is s scanl aux s1 2 100605 PSU CS457557 Fall3905 Tolmach Sample Series Values i Dlawlng Ellunse 122449 0112453 00229495 000614721 000189685 Note how quickly the values in the series get smaller 100605 How far to go It may seem worrisome that s scanl aux sl 2 is an infinite list because 2 is But that39s no problem so long as we only ever examine a finite prefix of the list How many should we take Only as many as contribute signi cantly to the answer eg only as long as they pass the signi cance test significant Float gt Bool significant x x gt 00001 for example Can use this handy prede ned function takeWhile a gt Bool gt a gt a takeWhile p takeWhile p xzxs p x x takeWhile p xs otherwise 100605 PSU cs457557 Fall3905 Tolmach 11 Putting it all Together perimeter Ellipse r1 r2 r1 gt r2 ellipsePerim r1 r2 otherwise ellipsePerim r2 r1 where ellipsePerim r1 r2 let e sqrt r1 2 r2 2 r1 s scanl aux O25e 2 2 aux s i nextEl e s i significant x x gt epsilon sSum sum takeWhile significant s in 2r1pi1 sSum 100605 PSU CS457557 Fall3905 Tolmach CS 457557 Functional Languages From Trees to Type Classes Mark P Jones Portland State University Trees ltgt There are many kinds of tree data structure ltgt For example data BinTree a Leaf a BinTree a A BinTree a deriving Show ltgt The deriving Show part makes it possible for us to print out tree values Definition example BinTree Int example l A r where l p A q s A t Leaf l A t s A Leaf 2 Leaf 3 A Leaf 4 Leaf 5 A Leaf 6 FFUJIQ39UH lt gt At the prompt Maingt example Leaf 1 z Leaf 5 z Leaf 6 z Leaf 3 z Leaf 4 z Leaf 2 Leaf 3 z Leaf 4 z Leaf 5 z Leaf 6 Maingt Wouldn t it be nice If we could view these trees in a graphical form Mapping on Trees ltgt We can define a mapping operation on trees mapTree a gt b gt BinTree a gt BinTree b mapTree f Leaf x Leaf f x mapTree f l A r mapTree f l A mapTree f r ltgt This is an analog of the map function on lists it applies the function fto each leaf value stored in the tree ltgt Example convert every leaf value into a string Maingt mapTree Show example Leaf quotlquot A Leaf quot5quot A Leaf quot6quot A Leaf quot3quot A Leaf quot4 z Leaf quot2quot A Leaf quot3quot A Leaf quot4quot A Leaf quot5quot A Leaf quot6quot Maingt ltgt Example add one to every leaf value Maingt mapTree 1 example Leaf 2 z Leaf 6 z Leaf 7 z Leaf 4 z Leaf 5 z Leaf 3 Leaf 4 z Leaf 5 z Leaf 6 z Leaf 7 Maingt ltgt Still not very pretty 6 Visualizing the Results If we could view these trees in a graphical form Visualizing the Results If we could view these trees in a graphical form Visualizing the Results we could see that mapTree preserves shape Gives insight to the laws mapTree id id mapTree f g mapTree f mapTree g Graphviz amp Dot Graphviz is a set of tools for visualizing graph and tree structures Dot is the language that Graphviz uses for describing the treegraph structures to be visualized Q Usage clot Tpng filedot gt filepng 10 Example Q To describe Leaf quotaquot A Leaf digraph tree 1quot u 1quot quot2quot quot2quot quot3quot quot2quot u 4quot u 1quot quot5quot A Leaf quotcquot labelquotquot gt quot2quot labelquotquot gt quot3quot labelquotaquot gt quot4quot labelquotbquot o o gt quot5quot labelquotcquot General Form A dot file contains a description of the form digraph name stmts where each stmt is either nodeid abequottextquot constructs a node with the specified id and label nodeid gt nodeid constructs an edge between the specified pair of nodes Actually there are many more options than this 12 From BinTree to clot How can we convert a BinTree value into a dot file For simplicity assume a BinTree String input Labels ltgt Label leaf nodes with the corresponding strings ltgt Label internal nodes with the empty string Nodeids What should we use for node ids 13 Paths Every node can be identified by a unique path The root node of a tree has path ltgt The nth child of a node with path p has path np type Path Int type NodeId String showPath Path gt NodeId ShOWPath p quotquotquot Show p quotnn Add quotes to avoid confusing 14 Graphviz tools Example 15 Actual clot code To describe Leaf quotaquot A Leaf quotbquot A Leaf quotcquot digraph tree quotquot labelquotquot quot Jquot 7gt quot1quot 1quot labelquotquot 11quot labelquotaquot 1quot 7gt quot21quot 2 2 1quot labelquotbquot o o Capturing Tree ness subtrees BinTree a gt BinTree a subtrees Leaf X subtrees l A r 1 r nodeLabel BinTree String gt String nodeLabel Leaf x nodeLabel l A r quotquot X 17 Trees gt clot Statements nodeTree Path gt BinTree String gt String nodeTree p t showPath p quot labelquotquot nodeLabel t quotquotquot concat ZipWith edgeTree p l subtrees t edgeTree Path gt Int gt BinTree String gt String edgeTree p n c showPath p quot gt quot showPath p39 nodeTree p39 c where p39 n p 18 A Toplevel Converter toDot BinTree String gt IO toDot t writeFile quottreedotquot quotdigraph tree nquot semi nodeTree t quotnquot where semi foldr l is gt 1 quotnquot ls quot Now we can generate clot code for our example tree Maingt toDot mapTree Show example Maingt ldot Tpng treedot gt expng Maingt 19 What About Other Tree Types data LabTree l a data STree a data RoseTree a data Expr Tip a LFork l LabTree l a LabTree l a Empty Split a STree a STree a Node a RoseTree a Var String IntLit Int Plus Expr Expr Mult Expr Expr Can I also visualize these using Graphviz 20 HigherOrder Functions Essential tree structure is captured using the subtrees anc nodeLabeI functions What if we abstract these out as parameters nodeTree39 t gt String gt t gt t gt Path gt t gt String edgeTree39 t gt String gt t gt t gt Path gt Int gt t gt String 21 Adding the Parameters nodeTree39 lab sub p t Z ShOWPath 9 quot labelquotquot lab t quotquotquot concat ZipWith edgeTree39 lab sub p 1 sub t edgeTree39 lab sub p n c showPath p quot gt quot showPath p39 nodeTree39 lab sub p39 c where p39 n p toDot39 t gt String gt t gt t gt t gt IO toDot39 lab sub t writeFile quottreedot quotdigraph tree n semi nodeTree39 lab sub t quotnquot where semi foldr l is gt 1 quotnquot ls quotquot 22 Alternative Local Definitions toDotquot t gt String gt t gt t toDotquot lab sub t writeFile quottreedotquot gt t gt IO 0 quotdigraph tree nquot semi nodeTree39 t quotnquot where semi foldr l ls gt 1 quotnquot ls quot nodeTree39 p t ShOWPath p quot labelquotquot lab t quotquotquot edgeTree39 p 1 concat zipWith sub t edgeTree39 p n c showPath p quot gt quot showPath p39 where p39 n nodeTree39 p39 c p 23 Specializing to Tree Types toDotBihTree toDot39 lab sub where lab Leaf x x lab 1 A r quotquot sub Leaf x sub 1 A r 1 r toDotLabTree toDot39 lab sub where lab Tip a a lab LFork s l r s sub Tip a sub LFork s l r 1 r toDotRoseTree toDot39 lab sub where lab Node x cs x sub Node x cs cs 24 quotcon nued toDotSTree toDot39 lab sub where lab Empty quotquot lab Split s l r s sub Empty sub Split s l r l r toDotExpr toDot39 lab sub where lab Var s s lab lntLit n show n lab Plus l r quotquot lab Mult l r quotquot sub Var s sub lntLit n sub Plus l r l r sub Mult l r l r 25 Example toDotRoseTree Node quot3quot Node quotbquot 7 Node quotcquot 7 Node quotdquot Node quotequot Example toDotExpr Plus Mult Var quotXquot IntLit 3 Mult Var quotyquot IntLit 5 Good and Bad Good lt gt It works ltgt It is general applies to multiple tree types It provides some reuse lt9 It reveals important role for subtreeslabeINode Bad ltgt It s ugly and verbose ltgt For any given tree type there s really only one sensible way to define the subtrees function 28 Type Classes What distinguishes quottree typesquot from other types a value of a tree type can have zero or more subtrees And for any given tree type there39s really only one sensible way to do this class Tree t where subtrees t gt t 29 For Instances instance Tree BinTree a where subtrees Leaf X subtrees 1 A r 1 r instance Tree LabTree 1 a where subtrees Tip a subtrees LFork s 1 r 1 r instance Tree STree a where subtrees Empty subtrees Split s 1 r 1 r 30 quotcon nued instance Tree RoseTree a where subtrees Node X cs cs instance Tree Expr where subtrees Var s subtrees IntLit n subtrees Plus 1 r 1 r subtrees Mult 1 r l r So What 31 Generic Operations on Trees depth t gt Iht depth 1 foldl max 0 map depth subtrees size t gt Iht size 1 sum map size subtrees t gt w paths t hull br t otherwise tp b lt br p lt paths b where br subtrees t t gt m dfs t t concat map dfs subtrees t Tree t gt means any type t so long as it is a Tree 32 type Ie so long as It has a subtrees function Implicit Parameterization ltgt An operation with a type Tree t gt is implicitly parameterized by the definition of a subtrees function of type t gt t ltgt The implementation doesn t have to work this way ltgt Because there is at most one such function for any given type t there is no need for us to write the subtrees parameter explicitly ltgt That s good because it can mean less clutter more clarity 33 Labeled Trees ltgt To be able to convert trees into dot format we need the nodes to be labeled with strings ltgt Not all trees are labeled in this way so we create a subclass class Tree t gt LabeledTree t where label t gt String ltgt Is this an appropriate use of overloading 34 LabeledTree Instances instance LabeledTree BinTree String where label Leaf x x label l A r quotquot instance LabeledTree LabTree String String where label Tip a a label LFork s l r s instance LabeledTree STree String where label Empty quotquot label Split 5 l r s Needs hugs 98 for example 35 quotcon nued instance LabeledTree RoseTree String where label Node x cs x instance LabeledTree Expr where label Var s s label IntLit n 2 Show n label Plus l r quotquot label Mult l r quotn 36 Generic Tree gt clot LabeledTree t gt t gt IO toDot toDot t writeFile quottreedotquot quotdigraph tree nquot semi nodeTree t quotnquot where semi foldr l ls gt 1 quotnquot ls quot gt t gt String nodeTree LabeledTree t gt Path nodeTree p t quot labelquotquot label t llnn subtrees t showPath p concat zipWith edgeTree p l edgeTree LabeledTree t gt Path gt Int gt t gt String edgeTree p n c showPath p quot gt quot showPath p39 nodeTree p39 c n p where p39 37 Example toDot Node quot3quot Node quotbquot Node quotcquot Node quotdquot Node quotequot Example toDot Plus Mult Var quotXquot IntLit 3 Mult Var quotyquot IntLit 5 Example Maingt toDot example ERROR Unresolved overloading Type LabeledTree BinTree Int gt IO Expression toDot example Maingt We need trees labeled with strings 40 Example Maingt toDot example ERROR Unresolved overloading Type LabeledTree BinTree Int gt IO Expression toDot example Maingt toDot mapTree show example Maingt mapTree a gt b gt BinTree a gt BinTree b mapTree f Leaf X Leaf f X mapTree f I A r mapTree fl A mapTree f r 41 The Functor Class class Functor f where fmap a gt b gt f a gt f b instance Functor where instance Functor Maybe where fmap id id fmap f g fmap f fmap g 42 Tree instance fmap f fmap f instance fmap f fmap f instance fmap f fmap f instance fmap f Instances Functor BinTree where Leaf x Leaf f x l A r fmap f l A fmap f r Functor LabTree l where Tip a Tip f a LFork s l r LFork s fmap f l fmap f r Functor STree where Empty Empty Split s l r Split f s fmap f l fmap f r Functor RoseTree where Node x cs Node f x map fmap f cs 43 Why no instance for Expr Example Maingt toDot fmap show example 39A39 example Maingt depth example 39A39 example 6 Maingt O O O O O O O O O O O 44 Type Classes ltgt We ve been exploring one of the most novel features that was introduced in the design of Haskell ltgt Similar ideas are now filtering in to other popular languages eg concepts in C We ll spend the rest of our time in this lecture looking at the original motivation for type classes 45 Between One and All ltgt Haskell allows us to define monomorphic functions that have just one possible instantiation not Bool gt Bool Ancl polymorphic functions that work for all instantiations id agta ltgt But not all functions fit comfortably into these two categories 46 Addition Q What type should we use for the addition operator Picking a monomorphic type like Int gt Int gt Int is too limiting because this can t be applied to other numeric types lt gt Picking a polymorphic type like a gt a gt a is too general because addition only works for numeric types 47 Equality Q What type should we use for the equality operator Picking a monomorphic type like Int gt Int gt Bool is too limiting because this can t be applied to other numeric types lt gt Picking a polymorphic type like a gt a gt Bool is too general because there is no computable equality on function types 48 Numeric Literals Q What type should we use for the type of the numeric literal O lt Picking a monomorphic type like Int is too limiting because then it can t be used for other numeric types And functions like sum foldl O inherit the same restriction and can only be used on limited types lt gt Picking a polymorphic type like a is too general because there is no meaningful interpretation for zero at all types 49 Workarounds 1 We could use different names for the different versions of an operator at different types Int gt Int gt Int Float gt Float gt Float Integer gt Integer gt Integer ltgt Apart from the fact that this is really ugly it prevents us from defining general functions that use addition again sum foldl O 50 Workarounds 2 We could just define the unsupported cases with dummy values O Int produces an integer zero O Float produces a floating point zero O Int gt Bool produces some undefined value eg sends the program into an infinite loop Attitude More fool you programmer for using zero with an inappropriate type 51 Workarounds 3 Q We could inspect the values of arguments that are passed in to each function to determine which interpretation is required Works for and although still requires that we assign a polymorphic type so those problems remain But it won t work for 0 There are no arguments here from which to infer the type of zero that is required that information can only be determined from the context in which it is used 52 Workarounds 4 ltgt Miranda and Orwell two predecessors of Haskell included a type called Num that included both floating point numbers and integers in the same type data Num In Integer Fl Float Now can be treated as a function of type Num gt Num gt Num and applied to either integers or floats or even mixed argument types ltgt But we ve lost a lot types don t tell us as much and basic arithmetic operations are more expensive to implement 53 Between a rock In these examples monomorphic types are too restrictive but polymorphic types are too general ltgt In designing the language the Haskell Committee had planned to take a fairly conservative approach consolidating the good ideas from other languages that were in use at the time ltgt But the existing languages used a range of awkward and adhoc techniques and nobody had a good general solution to this problem 54 How to make adhoc polymorphism less adhoc lt gt In 1989 Philip Wadler and Stephen Blott proposed an elegant general solution to these problems ltgt Their approach was to introduce a way of talking about sets of types Type Classes and their elements Instances ltgt The Haskell committee decided to incorporate this innocent and attractive idea into the first version of Haskell 55 Type Classes A age class is a set of types ltgt Haskell provides several builtin type classes including Eq types whose elements can be compared for equality Num numeric types Show types whose values can be printed as strings Integral types corresponding to integer values Enum types whose values can be enumerated and hence used in mn notation 56 A NotWell Kept Secret ltgt Users can define their own type classes ltgt This can sometimes be very useful lt9 It can also be abused ltgt For now we ll just focus on understanding and using the builtin type classes 57 Instances ltgt The elements of a type class are known as the instances of the class If C is a class and t is a type then we write Ct to indicate that t is an elementinstance of C Maybe we should have used tEC but the E symbol wasn t available in the character sets or on the keyboards of last century s computers 58 Instance Declarations lt The instances of a class are specified by a collection of instance declarations instance Eq Int instance Eq Integer instance Eq Float instance Eq Double instance Eq Bool instance Eq a gt Eq a instance Eq a gt Eq Maybe a instance Eq a Eq b gt Eq ab 59 quotcondnued ltgt In set notation this is equivalent to saying that Eq Int Integer Float Double Bool U t tE Eq UMaybet tEEq Ut1t2 I tleEthZEEq lt9 Eq is an infinite set of types but it doesn t include all types eg types like Int gt Int and Int gt Bool are not included 60 Derived Instances 1 ltgt The prelude provides a number of types with instance declarations that include those types in the appropriate classes ltgt Classes can also be extended with definitions for new types by using a deriving clause data T deriving Show data S deriving Show Ord Eq ltgt The compiler will check that the types are appropriate to be included in the specified classes 61 Operations The prelude also provides a range of functions with restricted polymorphic types Eqagtagtagt Bool Numagta gta gta min Ordagtagtagta show Show a gt a gt String fromInteger Num a gt Integer gt a ltgt A type of the form C a gt Ta represents all types of the form Tt for any type t that is an instance of the class C 62 Terminology ltgt An expression of the form C t is often referred to as a constraint a class constraint or a predicate A type of the form C t gt is often referred to as a restricted type or as a gualified ype A collection of predicates C t D t is often referred to as a context The parentheses can be dropped if there is only one element 63 Type Inference ltgt Type Inference works just as before except that now we also track constraints Example null X5 xs D Assume xs a Pick b gt b gt Bool with the constraint Eq b Pick instance c From xs we infer a b c with result type of Bool Thus null Eq c gt c gt Bool null Eq c gt c gt Bool 64 quotconUnued Note In this case it would probably be better to use the following definition null a gt Bool null True null XXs False The type a gt Bool is more general than Eq a gt a gt Bool because the latter only works with equality types 65 Examples lt9 We can treat the integer literal O as sugar for fromInteger O and hence use this as a value of y numeric type Strictly speaking its type is Num a gt a which means any type so long as it s numeric lt gt We can use on integers booleans floats or lists of any of these types but not on function types We can use on integers or on floating point numbers but not on Booleans 66 Inheriting Predicates Predicates in the type of a function fcan infect the type of a function that calls f ltgt The functions member xs X any X xs subset xs ys all member ys xs have types member Eq a gt a gt a gt Bool subset Eq a gt a gt a gt Bool 67 quotconUnued For example now we can define data Day SunlMoanuelWelehulFriSat deriving Eq Show And then apply member and subset to this new type Maingt member MonTueWedThuFri Wed True Maingt subset MonSun MonTueWedThuFri False Maingt 68 Eliminating Predicates ltgt Predicates can be eliminated when they are known to hold Given the standard prelude function sum Num a gt a gt a and a definition gauss sum 110Integer we could infer a type gauss Num Integer gt Integer But then simplify this to gauss Integer 69 Detecting Errors Errors can be raised when predicates are known not to hold Preludegt 39a39 l ERROR Cannot infer instance Instance Num Char Expression 39a39 l Preludegt x gt X ERROR Cannot find quotshowquot function for Expression X gt X Of type a gt a Preludegt 70 Derived Instances 2 ltgt What if you define a new type and you can t use a derived instance Example data Set a Set a deriving Num What does it mean to do arithmetic on sets How could the compiler figure this out from the definition above lt9 What if you define a new type and the derived equality is not what you want Example data Set a Set a We d like to think of Set 12 and Set 21 and Set 1112212 as equivalent sets 71 Example Derived Equality The derived equality for Set gives us Set xs Set ys xs ys lt gt And the equality on lists gives us True xrxs yrys x y ampamp xs ys False ltgt A derived equality function tests for structural equality what we need for Set is not a structural equality 72 Class Declarations ltgt Before we can define an instance we need to look at the class declaration class Eq a where a gt a gt Bool members Minimal complete definition or x y 0t XY x Y n0t XY ltgt To define an instance of equality we will need to provide an implementation for at least one of the operators or defaults 73 Member Functions ltgt In a class declaration class C a where f g h Ta ltgt member functions receive types of the form f g h Ca gtTa ltgt From a user s perspective just like any other type qualified by a predicate ltgt From an implementer s perspective these are the operations that we have to code to define an instance 74 Instance Declarations ltgt We can define a nonstructural equality on the Set datatype using the following instance Eq a gt Eq Set a where Set xs Set ys xs subset ys ampamp ys subset xs ltgt This works as we d like Maingt Set 1112212 Set 12 True Maingt Set 12 Set 34 False Maingt Set 21 Set 1112212 True Maingt 75 Overloading ltgt Type classes support the definition of overloaded functions ltgt Overloading because a single identifier can be overloaded with multiple interpretations But just because you can it doesn t mean you should lt9 Use judiciously where appropriate where there is a coherent unifying view of each overloaded function should do 76 Defining New Classes I define new type classes in my program or library I YES Should I define new type classes in my program or library Yes if it makes sense to do so What common properties would the instances to share and how should this be reflected in the choice of the operators Does it make sense for the meaning of a symbol to be uniquely determined by the types of the values that are involved 77 Beware of Ambiguity ltgt What if there isn t enough information to resolve overloading Early versions of Hugs would report an error if you tried to evaluate show The system infers a type Show a gt String and doesn t know what type to pick for the ambiguous variable a It could make a difference show Int quotquot but show Char quotquotquotquot Recent versions use defaulting to pick a default choice but the results there are also less than ideal 78 Summary Type classes provide a way to describe sets of types and related families of operations that are defined on their instances Q A range of useful type classes are builtin to the prelude ltvgt Classes can be extended by deriving new instances or defining your own ltgt New classes can also be defined ltgt Once you ve experienced programming with type classes it s hard to go without 79 CS 457557 Functional Programming Lecture 9 More on Higherorder Functions 102005 PSU CS457557 Fall3905 Tolmach Currying eta reduction Recall from Ch 1 the function simple n a b n ab Note that simple n a b is really simple n a b in fully parenthesized notation simple Float gt Float gt Float gt Float simple n Float gt Float gt Float simple n a Float gt Float simple n a b Float Therefore multSumByFive a b simple 5 a b is the same as multSumByFive simple 5 102005 PSU CS457557 Fall3905 Tolmach Use of Eta Reduction li xs xs listSum listSum listProd i listSum listProd and or and xs or XS i stProd Integer gt Integer foldr 0 XS foldr 1 xs foldr 0 foldr 1 Bool gt Bool foldr ampamp True xs foldr False xs foldr ampamp True foldr False 102005 PSU CS457557 Fall3905 Tolmach Be Careful Though Consider o fxg x2 yx This is not equal to f g x2 Y because we lose the binding for x In general o f x e x is equal to o f e only if x does not appear free in e 102005 PSU CS457557 Fall3905 Tolmach Simplify Definitions Recall reverse xs foldl revOp xs where revOp acc x x acc In the prelude we have flip f x y f y x Thus revOp acc x flip acc x or even better revOp flip 2 And thus reverse xs foldl flip xs or even better reverse foldl flip 102005 PSU CS457557 Fall3905 Tolmach Anonymous Functions So far all of our functions have been de ned using an equation such as the function succ de ned by succ x x1 This raises the question Is it possible to de ne a value that behaves just like succ but has no name Much in the same way that 3 14159 is a value that behaves like pi The answer is yes and it is written x gt x1 Indeed we could rewrite the previous de nition of succ as succ x gt x1 The backslash is meant to look like and is read as the Greek letter lambda Anonymous functions gure prominently in the lambda calculus an important foundational formalism for computation 102005 PSU CS457557 Fall3905 Tolmach Sections Sections are like currying for infix operators For example 5 x gt x 5 4 y gt 4 Y So in fact succ x x 1 can be written more simply as 1 Sections also permit specifying the righthand argument to an operator Although convenient sections are less expressive than anonymous functions For example it s hard to represent x gt x1 2 as a section You can also pattern match using an anonymous function as in xzxs gt x which is the head function 102005 PSU CS457557 Fall3905 Tolmach Function Composition Very often we would like to combine the effects of one function with that of another Function composition accomplishes this for us and is simply de ned as the infix operator f g xf gx So fg isthesameas x gt f g x Function composition can be used to simplify previous definitions totalSquareArea sides sumList map squareArea sides sumList map squareArea sides Combining this With eta reduction yields totalSquareArea sumList map squareArea 102005 PSU CS457557 Fall3905 Tolmach CS 457557 Functional Programming Lecture 5 Polymorphism Higherorder functions 100605 PSU CS457557 Spr3905 Tolmach Polymorphic Length a is a type variable It is lowercase to distinguish it from types which are u ercase len a gt Int len len xzxs 1 len xs Polymorphic functions don t look at their polymorphic arguments They use the same code now matter What the type of their polymorphic arguments 100605 PSU CS457557 Spr3905 Tolmach Polymorphism Consider tagl x 1x gt type tagl tagl a gt Inta Other functions have types like this consider type a gt a gt a What are some other polymorphic functions and their types id reverse head tail 100605 PSU CS457557 Spr3905 Tolmach Polymorphic data structures demmpano gnw s mndmasuudums mt don t care What kind of data they store id a gt a The ultimate polymorphic function reverse a gt a lists tail a gt a head a gt a z a gt a gt a fst ab gt a tuples swap ab gt ba Ihwdowe mnmwd a n mmsw f dw that can be polymorphic 100605 PSU CS457557 Spr3905 Tolmach Maybe is polymorphic data Maybe a Just a Nothing Note the types of the constructors Nothing Maybe a Just a gt Maybe a Thus Just 3 Maybe Int Just x Maybe String Just 3True Maybe IntBool Just Just 1 Maybe Maybe Int Example of its use lookup a gt ab gt Maybe b lookup k lookup k k39vrest k kI Nothing Just v otherwise lookup k rest 100605 PSU CS457557 Spr3905 Tolmach Polymorphism from functions as arguments Another source of polymorphism comes from functions which take functions as arguments applyTwice f x ff x Maingt t applyTwice applyTwice a gt a gt a gt a What39s the type of the following useful function flip f x y f y x 100605 PSU CS457557 Spr3905 Tolmach Polymorphism Functions returned as values Consider const x f where f y x Maingt const 3 5 3 What s the type of cons t Another Example compose f g x f g x VVhafsthetype0fcompose Note Prelude de nes compose as an infiX operator fgxf gx 100605 PSU CS457557 Spr3905 Tolmach Abstraction Over Recursive De nitions Recall some de nitions from previous chapters Section 41 translist transList pzps trans p translist ps Section 31 putCharList putCharList czcs putChar c putCharList cs There is something strongly similar about these de nitions Indeed the only thing different about them besides the variable names is the function trans vs the function putChar 0 We can use the abstraction principle to take advantage of this 100605 PSU CS457557 Spr3905 Tolmach 8 Abstraction Yields map trans and putChar are What s different so they should be arguments to the abstracted function In other words we would like to de ne a function called map say such that map trans behaves like transList and map putChar behaves like putCharList No problem map f 1 map f xzxs f x map f xs Given this it is not hard to see that we can rede ne transList and putCharList as transList xs putCharList cs map trans xs map putChar cs 100605 PSU CS457557 Spr3905 Tolmach map is Polymorphic o The key thing about map is that it is polymorphic Its most general principal type is map a gtb gt a gt b Every use of map has a type that is an instance of the principal type obtained by substituting for a and b For example since trans Vertex gt Point then map trans vertex gt Point and this use of map has type map vertex gt Point gt Vertex gt Point 100605 PSU CS457557 Spr3905 Tolmach Another Pattern Filtering Consider extracting the even numbers from a list evens Int gt Int evens 1 evens xzxs even x xevens xs otherwise evens xs Or removing the Whitespace from a string nowhite String gt String nowhite II II nowhite czcs not whitesp c x nowhite cs otherwise nowhite cs where whitesp 39 39 True whitesp ItI True whitesp False 100605 PSU CS457557 Spr3905 Tolmach Abstracting to f i 1 t e r Can de ne a common function filter a gt Bool gt a gt a filter p filter p xzxs p x xfilter p xs otherwise filter p xs Now can rewrite evens xs filter even xs orjust evens filter even And nowhite filter not whitesp Recall that represents function composition 100605 PSU CS457557 Spr3905 Tolmach List comprehensions revisited Recall some uses of the list comprehension notation putCharList cs putChar c c lt cs evens xs y y lt xs even y Observe that this notation incorporates both map and f i l ter e g putNonWhiteChars cs putChar c c lt cs not whitesp c Can easily define map and filter in terms of list comprehenion try it Actually list comprension is de ned in terms of map and filter and a few other things 100605 PSU CS457557 Spr3905 Tolmach 13 When to De ne HigherOrder Functions Recognizing repeating patterns is the key as we did for map As another example consider sum Int gt Int sum xzxs CZgt sum xs and Bool gt B001 and O and xzxs xand xs myminimum Int gt Int mymnimum n myminimum xzxs x myminimum xs Note the similarities Also note the differences circled which need to become parameters to the abstracted function 100605 PSU CS457557 Spr3905 Tolmach When to De ne HigherOrder Functions Recognizing repeating patterns is the key as we did for map As another example consider sum Int gt Int sum 6 Initial and Bool gt Bo and and xzxs xand xs myminimum Int gt Int myminimum myminimum xzxs Note the similarities Also note the differences circled which need to become parameters to the abstracted function 100605 PSU CS457557 Spr3905 Tolmach Abstracting to f o 1 dr This leads to foldr op init init foldr op init xzxs x op foldr op init xs Note that foldr is also polymorphic foldr a gt b gt b gt b gt a gt b We39ll see the full power of this polymorphism shortly Previous functions can now be rede ned sum xs foldr 0 XS and xs foldr ampamp True xs myminimum xs foldr min maxBound xs 100605 PSU CS457557 Spr3905 Tolmach Visualizing the effect of f oldr One useful way to think about What foldr does is to observe What it does on an arbitrary list written using explicit constructors foldr op init xlx2xn foldr op init x1 x2 xn x1 op x2 op xn op init So we can think of foldr as taking a list and replacing each by op and the final by i it foldr 0 2g 3 16 2 3 The r in foldr is because it folds from the right 100605 PSU CS457557 Spr3905 Tolmach 17 Mystery folds Consider these functions mysteryl xs foldr 1 XS mystery2 xs foldr k 0 xs where k a b b l mystery3 q xs foldr k False xs where k x b q x b mystery4 foldr z 1 What are their types What do they do 100605 PSU CS457557 Spr3905 Tolmach Two Folds are Better than One In addition to foldr the Haskell Prelude de nes another function foldl which folds from the left foldl op init x1 x2 xn 1 init op x1 op x2 op xn Exercise de ne foldl using recursion Why two folds Often they are equivalent but sometimes using one can be more ef cient than the other For example foldr xyz x y z foldl xyz x y z The former is more ef cient than the latter see textbook In general one or the other of foldl and foldr may be more ef cient andor lazier in any given circumstance Choosing between them is nontrivial 100605 PSU CS457557 Spr3905 Tolmach Reversing a List Obvious but inef cient Why reverse xs x reverse reverse xzzxs Much better Why reverse xs rev xs where rev acc acc rev acc xzxs rev xzacc xs This looks a lot like foldl we can rede ne reverse as reverse xs foldl revOp xs where revOp a b b a Or just as reverse foldl flip 2 100605 PSU CS457557 Spr3905 Tolmach CS 457557 Functional Languages Lecture 4 Lists and Algebraic Datatypes Mark P Jones Portland State University Why Lists Q Lists are a heavily used data structure in many functional programs Special syntax is provided to make programming with lists more convenient Lists are a special case an example of An algebraic datatVDe coming soon A parameterized datatVDe coming soon A monad coming but a little later Naming Convention We often use a simple naming convention If a typical value in a list is called X then a typical list of such values might be called xs ie the plural of X and a list of lists of values called X might be called xss A simple convention minimal clutter and a useful mnemonic too 3 Prelude Functions reverse take drop takeWhiIe dropWhiIe replicate iterate repeat a gt a gt a a gt a Int gt a gt a Int gt a gt a a gt Bool gt a gt a a gt Bool gt a gt a Int gt a gt a a gt a gt a gt a a gt a Constructor Functions lt9 What if you can t find a function in the prelude that will do what you want to do ltgt Every list takes the form an empty list xxs a nonempty list whose first element is x and whose tail is xs ltgt Equivalently the list type has two constructor functions The constant a u The operator a gt a gt a ltgt Using pattern matching we can also take lists apart 5 Functions on Lists null a gt Bool null True nu xxs False head a gt a head xxs X tail a gt a tail xxs xs Recursive Functions last a gt a last x X last xyxs last yxs init a gt a init x init xyxs X init yxs map a gt b gt a gt b map f map f xXs fX map fxs quotconUnued inits a gt a in List inits library inits xXs map X inits xs subsets a gt a subsets defiunseecg subsets xXs subsets xs map x subsets xs Why Does This Work ltgt What does it mean to say that ancl are the constructor functions for lists lt gt No Junk every list value is equal either to or else to a list of the form xxs ignoring nontermination for now lt1 No Confusion if X y or XS yS then xxs yys ltgt A pair of equations f f xxs defines a unique function on list values 9 Algebraic Datatypes 10 Algebraic Datatypes Booleans and Lists are both examples of algebraic datatypes No Junk Every Boolean value can be constructed using either False or True Every list can be described using a combination of and No Confusion True False xxs and if xxsyys then xy and xsys 11 In Haskell Notation data Bool False True introduces A type Bool A constructor function False Bool A constructor function True Bool data List a Nil Cons a List a introduces A type List t for each type t A constructor function Nil List a A constructor function Cons a gt List a gt List a 12 More Enumerations data Rainbow Red Orange Yellow Green Blue Indigo Violet introduces A type Rainbow A constructor function Red Rainbow A constructor function Violet Rainbow No Junk Every value of type Rainbow is one of the above seven colors No Confusion The seven colors above are distinct values of type Rainbow 13 More Recursive Types data Shape Circle Radius Polygon Point Transform Transform Shape data Transform Translate Point Rotate Angle Compose Transform Transform introduces Two types Shape and Transform Circle Radius gt Shape Polygon Point gt Shape Transform Transform gt Shape gt Shape I 14 More Parameterized Types data Maybe a Nothing Just a introduces A type Maybe t for each type t A constructor function Nothing Maybe a A constructor function Just a gt Maybe a data Pair a b Pair a b introduces A type Pair t s for any types t and s A constructor function Pair a gt b gt Pair a b 15 General Form Algebraic datatypes are introduced by toplevel definitions of the form data Ta1 an c1 cm where T is the type name must start with a capital letter a1 an are distinct type argumentsparameters variables must start with lower case letter n20 Each of the ci is an expression Fi t1 tk where o t1 t are type expressions that optionally mention the arguments a1 an o Fi is a new constructor function Fi t1 gt gt tp gt T a1 an 0 The any of Fi k20 Quite a lot for a single definition 16 No Junk and Confusion The key properties that are shared by all algebraic datatypes No Junk Every value of type T a1 an can be written in the form Fi e1 ek for some choice of constructor Fi and appropriately typed arguments e1 ek No Confusion Distinct constructors or distinct arguments produce distinct results ltgt These are fundamental assumptions that we make when we write andor reason about functional programs 17 Pattern Matching In addition to introducing a new type and a collection of constructor functions each data definition also adds the ability to pattern match over values of the new type ltgt For example given data Maybe a Nothing Just a then we can define functions like the following orElse Maybe a gt a gt a Just x orElse y X Nothing orElse y y 18 Pattern Matching amp Substitution The result of a pattern match is either A failure A success accompanied by a substitution that provides a value for each of the values in the pattern Examples does not match the pattern xxs 123 matches the pattern xxs with X1 ancl xs23 19 Patterns More formally a pattern is either An identifier Matches any value binds result to the identifier ltgt An underscore a wildcard Matches any value discards the result A constructed pattern of the form C p1 pn where C is a constructor of arity n and p1 pn are patterns of the appropriate type Matches any value of the form C e1 en provided that each of the ei values matches the corresponding pi pattern 20 Other Pattern Forms For completeness ltgt Sugared constructor patterns Tuple patterns p1p2 List patterns p1 p2 p3 Strings for example quothiquot h i ltgt Labeled patterns Numeric Literals Can be considered as constructor patterns but the implementation uses equality to test for matches ltgt as patterns idpat Lazy patterns pat nk patterns 21 Function Definitions ltgt In general a function definition is written as a list of adjacent equations of the form fp1 pn rhs where f is the name of the function that is being de ned p1 pn are patterns and rhs is an expression All equations in the definition off must have the same number of arguments the any of f 22 quotconUnued ltgt Given a function definition with m equa ons fpll1 pn1 rhs1 f p12 pn2 rth f p1m pnlm rhsm The value of f e1 en is S rhsi where i is the smallest integer such that the expressions eJ match the patterns pJIi and S is the corresponding substitution 23 Guards Guards ltgt A function definition may also include guards Boolean expressions fpl pn 91 rhsl I92 rhsz I93 rhs393 An expression f e1 en will only match an equation like this if all of the ei match the corresponding pi and in addition at least one of the guards gj is True lt gt In that case the value is S rhs where j is the smallest index such that gj is rue The prelude defines otherwise True Bool for use in guards 24 Where Clauses A function definition may also a where clause fp1 pn rhs where decls ltgt Behaves like a let expression fp1 pn let decls in rhs ltgt Except that where clauses can scope across guards fpl pn 91 rhsl I 92 rhsz I 93 rhs3 where decls Variables bound here in decls can be used in any of the gi or rhsi 25 Example filter filter a gt Bool gt a gt a filter p filter p xXs p x X rest otherwise rest where rest filter p X5 26 Example Binary Search Trees data Tree Leaf Fork Tree Int Tree insert Int gt Tree gt Tree insert n Leaf Fork Leaf n Leaf insert n Fork m r n lt m Fork insert n I m r otherwise Fork m insert n r ookup Int gt Tree gt Bool ookup n Leaf False ookup n Fork m r nltm ookupn ngtm ookupnr otherwise True 27 Case Expressions ltgt Case expressions can be used for pattern matching case e of p1 39gt e1 P2 39gt 92 pn gt en ltgt Equivalent to letfp1e1 fpzez fpnen infe 28 quotcon nued Guards and where clauses can also be used in case expressions filter p X5 case xs of gt XXs p X gt Xys otherwise gt ys where ys filter p X5 29 If Expressions If expressions can be used to test Boolean values if e then e1 else e2 ltgt Equivalent to case e of True gt e1 False gt e2 30 Extended Example The Zipper 31 General Trees lt gt A forest is a list of tree nodes each of which has a value and a forest of children type Forest a Node a data Node a Node a Forest a ltgt A simple example myForest Forest String myForest Node quot1quot Node quot11quot Node quot111quot Node quot12quot Node quot2quot 32 Operations on Forests Q forestEIems enumerates the values in a forest in depthfirst order forestEIems Forest a gt a forestEIems concat map nodeEIems where nodeEIems Node x cs x forestEIems cs ltgt depthMap annotates a forest using depth information depthMap Int gt a gt b gt Int gt Forest a gt Forest b depthMap f d map depthNode where depthNode Node x cs Node f d x depthMap f d1 cs 33 Displaying Forests ltgt Displaying a forest showForest Forest String gt String showForest unlines forestEIems depthMap indent 1 where indent d X5 replicate 2d 39SP39 xs lt gt Note from the Prelude unlines String gt String unlines concat map quotnquot 34 Positions in a Tree E DEEDS EDD DE DE How can you identify a particular position in a tree without pointers 35 Positions in a Tree E DEEDS EDD 93 Q R S Split the row containing the current node into a left and right portion 36 Positions in a Tree E QEQQQ Egg gnaw Add the layers on top Positions in a Tree V D g Q Q QQQSE Where each layer contains a left portion a single element and a right portion 38 Positions in a Tree V D QQ QQQSE data Position a Pos Node a Level a Node a type Level a Node a a Node a 39 Forests and Positions Converting between forests and positions rootPosition Forest a gt Position a rootPosition f Pos f reconstruct Position a gt Forest a reconstruct Pos Is us rs foldl recon reverse Is rs us where recon fs Isxrs reverse Is Node x fs rs Note reconstruct looses information reconstruct rootPosition id rootPosition reconstruct id 40 Moving Around a Forest moveLeft moveRight Position a gt Maybe Position a moveLeft Pos Is us rs case Is of gt Nothing nns gt Just Pos ns us nrs moveRight Pos Is us rs case rs of gt Nothing nns gt Just Pos ns us ns 41 Identifying a Recurring Pattern repos b gt b gt b gt a gt Maybe a repos xs f case xs of gt Nothing nns gt Just f n ns moveLeft Pos Is us r5 repos ls n ns gt Pos ns us nrS moveRight Pos Is us rs repos rs n ns gt Pos ns us ns moveDown Pos Is us rs repos rs Node X cs ns gt Pos Isgtltnsus cs 42 Other Operations lt gt Modifying the tree insertNode a gt Position a gt Position a insertNode X Pos ls us rs Pos ls us Node X rs deleteNode Position a gt Maybe Position a deleteNode Pos ls us rs repos rs ns gt Pos ls us ns ltgt Reflecting the tree reflect Position a gt Position a reflect Pos ls us rs Pos rs us Is 43 For Further Information A simple interactive tree editor Mark P Jones Functional Pearl The Zipper G ra rd Huet 44 Summary Algebraic datatypes can support Enumeration types Parameterized types Recursive types Products compositeaggregate values and Sums alternatives ltgt Type constructors Constructor functions Pattern matching lt gt Unifying features No junk no confusion 45 CS 457557 Functional Languages Leveraging Laziness Mark P Jones Portland State University Lazy Evaluation With a lazy evaluation strategy Don t evaluate until you have to When you do evaluate save the result so that you can use it again next time Why use lazy evaluation Avoids redundant computation Eliminates special cases eg ampamp and H Facilitates reasoning Lazy evaluation encourages Programming in a compositional style Working with infinite data structuresquot Computing with circular programsquot Compositional Style Separate aspects of program behavior separated into independent components fact n product 1n suqurs n sum map X gt XX 1n minimum head sort Infinite Data Structures Data structures are evaluated lazily so we can specify infinite data structures in which only the parts that are actually needed are evaluated powersOfTwo iterate 2 1 twoPow n powersOfTwo n fibs O 1 zipWith fibs tail fibs fib n fibs n Circular Programs An example due to Richard Bird Using circular programs to eliminate multiple traversals of dataO Consider a tree datatype data Tree Leaf Fork Int Tree Tree Define a function repMin Tree gt Tree that will produce an output tree with the same shape as the input but replacing each integer with the minimum value in the original tree Example Same shape values replaced with minimum Example Obvious implementation repMin t mapTree n gt m t where m minTree t Example Can we do this with only one traversal A Slightly Easier Problem 4 gt lWFV In a single traversal Calculate the minimum value in the tree 0 Replace each entry with some given n A Single Traversal We can code this algorithm fairly easily repMin Int gt Tree gt Int Tree repMin n Leaf maXInt Leaf repMin n Fork m l r min nl nr Fork n l 0 where nl D repMin n nr r3 repMin n r Tying the knot Now a call repMin mt will produce a pair n t where n is the minimum value of all the integers int t is a tree with the same shape as t but with each integer replaced by m 0 We can implement repMin by creating a cyclic structure that passes the minimum value that is returned by repMin as its first argument repMin t t where n tb repMin r11 t I Aligning Separators a more realistic example Mark is Fussy about Layout Have you noticed how I get fussy about code like map a gt b gt a gt b mapf map f Xsz f X map f XS filter a gt Bool gt a gt a filter p 1 filter p Xsz p X X filter p Xs otherwise filter p XS 0 O A Mark is Fussy about Layout and try to line up the separators like this map map f map f Xsz filter filter p filter p Xsz IpX otherwise a gt b gt a gt b l f X map f Xs a gt Bool gt a gt a l X filter p XS filter p XS 0 O V Can we do this Automatically map a gt b gt a gt b map a gt b gt a gt b map f 1 1 map f 1 1 map f xzxs f x map f xs map f xzxs f x map f xs filter 2 a gt Bool gt a gt a filter a gt Bool gt a gt a filter p 1 1 filter p 1 1 filter p xzxs filter p xzxs pxxfilterpxs Ipx xfilterpxs otherwise filter p xs otherwise filter p xs 00 OO Some Preliminaries separators String separators quotquot quotquot pad Int gt String gt String pad n s take n s repeat 39 39 Tying the Knot again main main align align S where 39 IO getEnv quotTMSELECTEDTEXTquot gtgt putStr align 39 String gt String unlines map snd ps w foldr max 0 map fst ps ps map patchLine w lines 5 An Editor Plugin Edit COMM Uno an unnum39 SM linking 3 mm IguawnamaW wt MLlllllnlll mun umnmp mart tauthx wmrm can calm 39mmcrmvvrxt39 n mam any mumquot 39u39 239 1 amp 2 sum gt mun any mum In ad pt mun Volw w 0 Iv 3931 m a In Main v 11m 2 2 Int gt sum gt ung plain wgnu mquotn Mumn Int 1 sum gtl 1m mung amoun n u rum Imam 0 an Me My t m l tum 5 mil unw as pm n I 4 on I m in c an mm up mm a s moms amp 391P l0quotbs 3 but quotmquot V 7 iii Agar f m 39 an cum Gum quot W 3976 mam f m 3139 3 Van 59090 Mar wum huh nau auhnhu Combining Techniques of Lazy Programming Escape That39s the goal Rush Hour is a premier sliding block puzzle designed to challenge your sequential thinking skills and perhaps your trafficofficer aspirations as well A Rush Hour Solver Uses lazy evaluation in three important ways Written in compositional style Natural use of an infinite data structure a search tree that is subsequently pruned to a finite tree that eliminates duplicate puzzle positions Cyclic programming techniques used to implement breadthfirst pruning of the search tree Representing the Board type Position Coord Coord type Coord Int maxw maxh Coord maxw 6 maxh 6 Representing the Pieces type Vehicle Color Type data Color Red m Emerald deriving Eq Show data Type Car Truck deriving Eq Show len Type gt Int len Car 2 3 len Truck Representing Puzzles type Puzzle Piece type Piece Vehicle Position Orientation data Orientation W H vehicle Piece gt Vehicle vehicle v p o v solved Piece gt Bool solved p p Red Car 43 W puzzlel puzzlel Puzzle E EEEV From Moves to Trees Checking for Obstructions puzzleObstructs Puzzle gt Position gt Bool puzzleObstructs puzzle pos or pieceObstructs p pos plt puzzle pieceObstructs Piece gt Position gt Bool pieceObstructs ct xy W UIV yv ampamp xltu ampamp ultxlen t pieceObstructs ct xy H UIV xu ampamp yltv ampamp vltylen t Calculating Moves moves moves puzzle piece where back back xy W xgtO ampamp free p v free step step dir p Puzzle gt Piece gt Piece step back piece step forw piece Piece gt Maybe Piece Just v p W where p X1 y not puzzleObstructs puzzle a gt Maybe a case dir p of gt a gt a Nothing gt Just p gt p39 step dir p39 Forests and Trees type Forest a Tree a data Tree a Node a Tree a mapTree a gt b gt Tree a gt Tree b mapTree f Node x cs Node f x map mapTree f cs pathsTree Tree a gt Tree a pathsTree descend where descend xs where xs39 Node xs39 Node x cs map descend xs39 cs XIXS Making Trees forest forest splits splits eg pS XS Puzzle gt Forest Piece l as p bs Node m qs forest qs m lt moves asbs p let qs as m bs a gt a a a m exercise to the reader m splits quotdogquot ldllllogquot lldll lollllgquot lldoll lgl quotH lt splits ps Puzzle nquot Pruning the Tree We want to avoid puzzle solutions in which the same piece is moved in two successive turns The generated tree may contain many instances of this pattern We can prune away repetition using trimRel a gt a gt Bool gt Tree a gt Tree a trimRel rel Node x cs Node x filter Node y gt rel x y cs Eliminating Duplicate Puzzles We don t want to explore any single puzzle configuration more than once We want to find shortest possible solutions requires breadthfirst search of the forest C o o o q agaaplaa ms wa dogta xsi distinct positions that have been found by the end of the ith level trimDups Eq b gt a gt b gt Forest a gt Forest a trimDups val f f39 where f39 xss prune f zxss knottymg prune xss xss prune Node v cs ts xss 1 t 1 39 e X V V m A InflnlteIIst 1f x elem head xss then prune ts xss else let cs39 xssl prune cs tail xss ts39 xss2 prune ts xzhead xssxssl in Node v cs39 ts39 xss2 CS 457557 Functional Programming Lecture 13 Animations 111005 PSU CS457 557 Fall3905 Tolmach Animations An animation is a moving graphic Sometimes we say a timedependent graphic since where it moves to is dependent upon time To create the illusion of movement we need draw frames with a different picture each frame A frame rate of about 30 frames a second is optimal less than 1520 appears to icker greater than 30 gives no apparent improvement To draw a frame we need to erase the old frame before drawing the new frame All our drawings have been accumulative we never erase anything just draw over what s already there There eXist several strategies for frame drawing 111005 PSU CS457 557 Fall3905 Tolmach Buffered graphics 0 Display devices display the information stored in the Video memory o Buffered graphics use two sets of memory instantaneously switching from one memory to the other so quickly that the icker effect is unobservable This video memory free for writing while the other is displayed 111005 PSU CS457 557 Fall3905 Tolmach Haskell interface to buffered graphics Usual tick rate 30 I ti d 0 getW1ndoleck Wlndow gt IO mespersecon Every window has an internal timer getWindowTick waits for the next tick since the last call to getWindowTick before it returns If the next tick has already occurred it returns immediately o getTime IO Integer Returns the current time measured in milliseconds counting from some arbitrary point By itself means nothing but the difference between successive calls accurately measures elapsed time o setGraphic Window gt Graphic gt IO Writes the graphic into the free Video graphic buffer At the next frame tick What s in the free Video buffer Will be drawn and the current buffer will become the free buffer 111005 PSU CS457 557 Fall3905 Tolmach Interface to the richer window interface Old interface openWindow String gt Point gt IO Window eg openWindow title widthheight Richer interface openWindowEX String gt Maybe Point gt Maybe Point gt Graphic gt DrawFun gt Maybe Word32 gt IO Window openWindowEX title Justxy upper left corner Justwidthheight drawBufferedGraphic drawing mode Just 30 refresh rate 111005 PSU CS457 557 Fall3905 Tolmach Animations in Haskell type Animation a Time gt a type Time Float blueRubberBall Animation Graphic blueRubberBall t WithColorBlue shapeToGraphic Ellipse sin t cos t animate String gt Animation Graphic gt IO mainl animate quotAnimation of a Shapequot blueRubberBall 111005 PSU CS457 557 Fall3905 Tolmach Shape pulses from this 3 Q i Animation of a Shape to this to this 0 111005 PSU CS457 557 Fall3905 Tolmach The animate function animate String gt Animation Graphic gt IO animate title anim runGraphics do w lt openWindowEX title Just 00 JustxWinyWin drawBufferedGraphic Just 30 to lt getTime let loop do t lt getTime let ft fromInteger t tO lOOO setGraphic w anim ft getWindowTick w loop 111005 PSU CS457 557 Fall3905 Tolmach Alternative Definition We made animation a polymorphic type constructor so that we could describe timevarying behaviors of types other than Graphic 0 Could rewrite example like this rubberBall Animation Shape rubberBall t Ellipse sin t cos t mainl IO mainl animate Animation of a Shape withColor Blue shapeToGraphic rubberBall Note convenience of composition here 111005 PSU CS457 557 Fall3905 Tolmach Complex Animations revolvingBall Animation Region revolvingBall t let ball 2 Shape Ellipse 02 02 in Translate sin t cos t ball planets Animation Picture planets t let pl Region Red Shape rubberBall t p2 2 Region Yellow revolvingBall t in pl Over p2 tellTime Animation String tellTime t quotThe time is quot show t 111005 PSU CS457 557 Fall3905 Tolmach Telling Time main2 animate quotAnimated Text text 100200 tellTime The time changes as time advances he time is 99499 111005 PSU CS457557 Fall3905 Tolmach Revolving Circle regionToGraphic Region gt Graphic regionToGraphic drawRegion regionToGRegion main3 animate quotAnimated Regionquot withColor Yellow regionToGraphic revolvingBall PSU CS457 557 Fall3905 Tolmach 12 111005 Animating Pictures Case analysis over schUueoprUHe picToGraphic Picture gt Graphic Ike mpnmnww overGraphkf 84 withColor c regionToGraphic r em Gm MC picToGraphic Region 0 r picToGraphic pl Over p2 picToGraphic pl overGraphic picToGraphic p2 picToGraphic EmptyPic emptyGraphic main4 animate quotAnimated Picturequot picToGraphic planets 111005 PSU CS457 557 Fall3905 Tolmach Lifting primitives to animations 0 It39s useful to define time varying primitives e g type Anim Animation Picture 0 First an Anim which doesn t really vary emptyA Anim Recall em t A t Em t Pic Alum p y p y Animation Picture Time gt Picture hence the time Comblmng t1me varymg plctures parametert overA Anim gt Anim gt Anim overA al a2 t a1 t Over a2 t overManyA Anim gt Anim overManyA foldr overA emptyA 111005 PSU CS457 557 Fall3905 Tolmach Time Translation timeTransA Time gt Time gt Animation a gt Animation a or timeTransA Animation Time gt Animation a gt Animation a timeTransA f a t a f t or timeTransA f a a timeTransA 2 anim runs twice as fast timeTransA 5 anim runs 5 seconds ahead 111005 PSU CS457 557 Fall3905 Tolmach

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.