### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Functional Programming COSC 3015

UW

GPA 3.89

### View Full Document

## 34

## 0

## Popular in Course

## Popular in ComputerScienence

This 38 page Class Notes was uploaded by Ashlynn Rau on Tuesday October 27, 2015. The Class Notes belongs to COSC 3015 at University of Wyoming taught by James Caldwell in Fall. Since its upload, it has received 34 views. For similar materials see /class/230332/cosc-3015-university-of-wyoming in ComputerScienence at University of Wyoming.

## Popular in ComputerScienence

## Reviews for Functional Programming

### 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: 10/27/15

COSC 3015 Lecture 6 Lecture given by Prof Caldwell and scribed by Sunil Kothari September 167 2008 1 Recap HW data Day Sunl Mon I Tue I Wedl Thu I Fri ISat deriving Eq 0rdEnum By default7 the enums start from 0 The Enums type class is as follows class Enum a where toEnum Int gt a fromEnum a gt Int We can create an instance for Day type as follows instance Enum Day where toEnum I O Sun I 1 Mon fromEnum I Sat O I Sun 1 ln Bird s book7 the toEnum has it the other way should be that toEnumfromEnum k k fromEnum toEnum k k These laws cannot be checked by type checker but would require theorem proving Since we have derived from Eq type class we can do the following gt Sun Mon gt False with day not declared an instance of the Eq type class gt Sun Mon ERROR Unresolved overloading Type Eq Day gt Bool Expression Sun Mon In general if f is a function fa A b A c then f is an in x version of f For exmaple7 we can de ne dagAfter and dagBefore functions as Maingt t dayAfter dayAfter Enum a Enum b gt b gt a Maingt t dayBefore dayBefore Enum a Enum b gt b gt a Type classes provide an elegant implementation of so called adhoc polymor phism where a simple name returns to many objects which in haskell are distinguished by their type Maingt dayAfter Tue Day Wed Another issue is whether type annotations are needed 2 Extra Dr Caldwell did not do this in the class but asked me to include in the class notes Note that this requires Haskell extensions We can de ne nextEnum for the Day as follows nextEnum 67171131 t0Enum mod fmmEnum 6 1 fromEnum maxBoundDay 1 Note the type of this function is Maingt t nextEnum nextEnum Enum a gt Day gt a This function can be evaluates as follows Maingt nextEnum Sun ERROR Unresolved overloading Type Enum a gt a Expression nextEnum Sun Maingt nextEnum Sun Day Mon We can de ne a generic version of it as follows nextEnuml e toEnum mod fromEnum 9 1 fromEnum k maxBound e 1 where k agt a k x y x Maingt nextEnuml Sun Day Mon Here7 we don7t need a particular type So using it we can de ne another function Which enumerates to a different type The function nexEnum increments the integer value associated With element e1 of an enumerated type then maps that element to the associated element of enumerated type of e2 modulo the size of the type of e2 The element e2 is ANY element of the target type7 it does not matter Which one e2 is used to coerce maxBound to the proper typei nextEnum e1 e2 k toEnum fromEnum el 1 mod fromEnum max 1 92 wherek agtagta kxyx max kmaxBound e2 Here s the interaction With Haskell interpreter for the above function Maingt t nextEnum nextEnum Enum a Enum b Bounded a gt b gt a gt a Maingt nextEnum Wed True False Maingt nextEnum Wed False False Maingt nextEnum Tue False True Maingt nextEnum Tue True True Maingt The function nextEnum defined above can then be defined as nextEnum e nextEnum e e We can use the new function as Maingt nextEnum Tue Wed Maingt nextEnum Wed Thu Maingt COSC 3015 Lecture 4 Lecture given by Prof Caldwell and scribed by Sunil Kothari September 167 2008 1 Recap Somebody asked about What s going on 7 So here is the response Recall functions from dom a to codomain b a A b Where7 a and b are type variables and they can stand for any type Suppose we instantiate b With the type Int A String Then if f z a A Int A String so f maps things of type a to functions of type Int A String That means if z z a fr 2 Int A String The result of applying the function f to the argument 1 Here s a concrete example Example 1 f k m7 gt m Is Here s another equivalent de nition f kmmk So the type off isNuma aH aaa What doesf look like as a set of pairs 9 f m1 f 1 mmm 1 In the last HW notes fwas called plusi ln Haskell7 the default is curriedi gt21 plus xy x y Num a gt aa gt a gt21 plusc x y x Num a gt a gt a gt a input output lt0 ltlt00gtlt11gtlt7171gtgtgt lt1 ltlt01gtlt12gtlt710gtgtgt gt21 plusc 5 Int gt Int gt21 plus 5 splat type error 2 Curry and Uncurry So curry can be de ned as cuTTyf z A y A f zy Here s an alternative de nition curryf z y f zy so the type of f is ab A c A a A b A c Remember arrow associates to the right so a A b A 5 means a A b A 0 Also function application associates to the left So f z y means z y and not f I o By default type checker is gonna get rid of as many paranthesis as it can Normally pairs are written as catesian product but in Haskell both type and terms are represented by the same notation iiei depending on the context ab might be a product type or a pair of terms And uncurry could be written as uncurry f p A f fst p 3nd p th fst Here s an anternative de nition uncurry f x y A f z y Here s another de nition uncurry f zy So the type of uncurry is a A b A c A ab A c Again curry and uncurry are fundamental notionsi By default things are written in curried ormi 3 Function composition Consider three types A B C with f z A A Bg B A C so function composition is de ned as g o The type ofg o f is a A c To make it syntactic valid Haskell we can write backquotes around it For example 707 In Haskell we can write is as gifi So gif zi gt so 7777 is a special in x operator denoting function compositioni There is a Haskell notation for turning in x operator into a pre x operatori If 69 is an arbitrary binary argument taking a and b to c then 69 z a A b A c So what is the type of function composition z b A c A a A b A a 5 C Example 2 addlz z 1 timesZz 2 6 z adstimesZ M y7 gt 2 6 y 1 timesZiadd1Myi gt 2 if y 1 How can we calculate this 7 what is the type of addltimes ltls Int A Into So choose an arbitrary int say X and then calculate with addlitime M addltim6321 M addl 2 96 I M 2 96 z l ow consider shawl One of the types of Show is Int A String Consider length I a A Into So what is lengthishow calculates the length of the string representation of its argument The type of lengthishow is Show a gt a gt Int 31 Reasoning about functions Consider the identity function idz If I 0 z 0 is the right identity for 1 96 z z 1 is the left idenenity for 96 id is the left and right identity for the function composition So7 we are saying flid idlf f Recall that if g 2 a A b then f 9 iff VI df z g If So that the type of flid and idlf is a A b To show f flid show VI df z Choose arbl z z a and show fr Starting on the right z f id 1 f I also7 z id 1 f I What good is knowing What the identity of an operation is 7 Consider sum that sums all elemnets of the list sum 0 sumh t h sumt prod 1 prodh t h prodt campase id campaseh t hlcamposet So composef1f2f3 f1lf21f3 COSC 3015 Lecture 5 Lecture given by Prof Caldwell and scribed by Sunil Kothari September 16 2008 1 Some Notes on Haskell Syntax Function names variable names starts with lowercase letter followed by zero or more digits underscores upper or lowercase letters forward quotes For example zlz zl Iquot Datatype and datatype constructor names start with uppercase letters and are otherwise like functions and variable names For example Baal Stn39ng Int True False Keywords case class data default deriving do else if import in in x in xl in xr instance let module newtype of then type where 11 Layout rule Each function de nition must begin in the same column a b c where 12 Comments Line comments start with 777 and continue to the end of the line For exam p167 fr 1 17 idumbfunction Nested comments are of the form 7 7 13 Local De nition The following code has the same effect as the ex 1 a let b 1 c2 in bc Here s another version of it a bc where NH Meaning of letinc let I t1 in t2 means t2z 2 t1 where7 o z is locally de ned variable 0 t1 is local declaration of z 0 t2 body of the letdeclaration and t2z t1 evaluate expression t where all free occurrences of I get the value of expression tll Note tha 77 77 is a captureavoiding substitution let x 1 in letx2in x v2 we can elaborate on it VI Int7Vz natlz 2 0 Choose arbl y 6 int and show VI Int7Vz natlz 2 0z I y 2V1 natz 2 0 14 if then else A code fragment in an imperative language if x gt 0 then y x else y x In C and C there is a conditional expression y x gt0 x x ie it returns a value ofx or X depending on Whether I gt 0 The type of if thenelse7 for example b t1 t2 if b then t1 else t2 isBoolgtagtagtai Note if True then 0 else 77foo77 is not welltyped Evaluation rules for if then else if True then t1 else t2 2 t1 if False then t1 else t2 M t2 If we evaluate if True ampamp False then 0 else 1 then the interpreter responds With 1 fact k if k 0 then error 77fact of a negative number not de ned77 else if k 0 then 1 else k fact kl gtt fact Num a 0rd a gt a gt a k 1 I k gt0 k fact1k1 gtt Num a 0rd a gt a gt a 15 Standard Prelude It s a default library Which gets loaded When you startupi Haskell supports datatype declarations Enumerated Types ln Haskell7 Bool is de ned as a datatype With two constructor data Baal True l False gt21 True True Bool But in the prelude it is de ned as data Baal True l False deriving E11 0rd Enum Read Show Bounded Here7 deriving tells Haskell to derive all the operations for all the named type classes gt21 Show True Show True String 16 In x operators ampampI I Bool gt Bool gt Bool True ampamp x x False ampamp False True I I x True False I I x x gt False ampamp infinity ln Haskell7 we have lazy evaluation so if we try to evaluate the above expression it evaluates to False But in eager evaluation it Will loop foreveri There is a little bit of asymmetry here In nity and False Will not terminate but evaluate to in nity not 2Bool gt Bool not True false not False True otherwise Bool not otherwise True COSC 3015 Lecture 9 Lecture given by Prof Caldwell and scribed by Sunil Kothari September 237 2008 1 Functions on lists Lists are the bread and butter of functional programming At least they started out that way The rst functional programming language7 LISP List Process ing7 1960 by John McCarthy7 had list as the fundamental datastructure LISP is great at symbolic processing the Al programming language Using the Haskell notation we can write list as data Nat a l aa so we can say Hugsgt t l J a Hugsgt t 2 2 a gt a gt a 11 null function The term cons actually means list constructori null True null2 False 77 is a speci cation that matches any pattern Alternative If we de ne null as nullSz 1H then the type is Maingt 1 null nulll Eq a gt a gt Bool if x then True else False is a really dumb way of de ning the above function if b then e1 else e27 Where 0 b bool 0 6162 both must have the same type Evaluation for if then else if True then e1 else e2 M 61 if False then e1 else e2 M 62 In the book null is de ned as null H TTu6 null I IS Fal36 How is this different from one above nulll L L So null is strict ie if it is applied to L then the result is Li null7 t Num a gt a gt a gt a Maingt But we cannot do so for null7 it generates a type errorl Maingt nu113 RUR Unresolved overloading Type Num a Eq a gt a gt a gt Bool Expression nu113 But7 null and nulll behave differently than nullfi Maingt null2 False Maingt nulll False So nulll and null apply to a Wider class of list types those that are instances of the Eq type class and those that are not 12 Append We want that 12345 123475 If we had some re ection we can do it So how can we do it 7 We are gonna de ne it by recursion on the rst argument ys ys zzsys zzsys So how dowe think about it We have a cons and we want to glue together it with ysi So what is thew rst element of what we wwant 7 The rst element is X So the pattern is almost always same In this case we take out X and recurse down on the smaller structurei llvgl l37475l 1 l37475l 112 345 122 345l 123475 Letls try another recursive de nition 13 length What about length 7 It s de ned as Maingt 1 length length 2 a gt Int Maingt length 0 lengthz IS 1 lengthzs 14 reverse Let7s try reverse Maingt 1 reverse reverse a gt a and is de ned as TEUETSEH H Teve rsezzzs TEUETSEISI 15 concat Lets do concat Maingt t concat concat a gt a concat 12345 l2345 and is de ned as concat concat I 18 l I concat IS How do we compute With the concat function concatl23 Another example concatl 2 3 H 47 5 16 zip Maingt t zi zip a gt b gt ab We de ne it by recursion on the Here s an alternate de nition 2239 llys zip I IS gs zip z 18 y gs 1 2 3 concat 17273l ll 123 123 123 concat 47 5ll l 1 2 3 l concat 47 5 H4 5 Jrcanwt H Hg 45 l 123 1727374754 rst argument ll zheadys zip IS tailys zy zip IS gs Design Choice for zip What is the right length 7 length zip IS gs HQ HQ HQ HQ min length 18 length gs max length 18 length gs if length xs ltgt length ys then error else length xs length 18 07 if length xs gt length ys then error zipl is strict in both argument 22101 H H u zipl I IS H zipl z IS H zipl I 18 y ys z y ziplzsys 2270 H i ll zip L H L zip L L zip7 is not strict in its second argument zip ll 98 H zip 18 H H zip I 18 y ys z y zip IS ys ln Haskll there is intersting notation 0 An in nits list of ints 1H 123 4 i i 0 Partial lists LL 2 12L 3 1221L 0 Finite lists L L the type of lists is a 17 last last error last I IS if null xs then X else last xs last 123 last 2 3 last 3 3 Here s another way of doing it last I last I IS last 18 yet another way is last head reverse Maingt 1 error error String gt a In a way the result of error is like bottomi COSC 3015 Lecture 3 Lecture given by Prof Caldwell and scribed by Sunil Kothari September 16 2008 1 Recap Last time we talked about functions and what they are In Haskell you can write programs which fail to terminate We wrote 1 infinity infinity a One of the features of Haskell program is polymorphism an expression can have many types So in nity has all types Often we want to show functions have similar property 2 Functions QzHow to tell if functions are equal AzExtensionality pointwise equality De nition 1 Extensionalz39ty If fg E A A B f g and only isz z 91 This is introduced in discrete maths COSC 2030 For any type we have three things 1 constructors 2 destructors 3 type notation For functions the constructor is z A b is a function with one argument I here and de ned by the expression bi The destructor for a function is function application write name of the function next to the argument For example A bai The type notation is a A bi The notation in Haskell is If gt z z a7 gt or 21 Tuples The constructor for tuples is 77 77 brackets The destructors for tuples are fstsnd and are de ned as follows fsta7 b a sndab b The type notation is ab ln math7 you use cartesian product of the form a X b 22 B001 The constructors for Bool are True7 False There are no destructors And the type notation is B00 23 List The constructor for list is H Empty list7 and 77z77 called cons The destructors are head and tail and they have the types head a list gt a tail a list gt a 24 Historical Note About 19307 a guy named Alonzo Church invented a notation for a calculus of functions This was called the lambda calculus A z 1 LM l MN varibales abstraction application where M7 N are lambda terms constructed by the above grammar Alan Turing student of Church showed that Turing Machine are equivalent to lambda calculus Church7s thesis says Everything that can in principle be computed can be computed by lambda term Haskell Curry was working on logical systems called combinatory logic turn out closely related to lambda calculus Why was everyone working on it 7 Around 1920 s people were wondering about what can be computed Curry noted that a propositional logic formula is valid true if and only if the type associated with the formula is 77inhabited77 by the Aterm This is called the CurryHoward isomorphism So what s the tgnslaLion gt B A A B B A7 B A ts Dgtltrgt 25 Currying and Uncurrying Curry noticed the following AA B C A B C Currying A B C A AB C uncurrying We can do the translation as follows AAB C A B C AB C AHB C AB A C A A A B A C What is the function that has this type 7 Approach start labelling this argu ments curry AB A C A A A B A C t curry f A gtB gtC Suppose we are given f z A B A C I z A y 2 Bi How can we get something of type C 7 curry f I y f Ivy To do this in Haskell do the following 1 create a le curry7hs 2 put the de nition of the curry function in to the le 37 do th curry This will give the following output 1 Maincurry abgt c gt a gt b gtc Note that arrow associates to the right by default so a A b A 5 means a A b A c This is like looking at a type and guring out the function But you should be wondering how does the compiler looks at a function and gures out the type 7 There is a type inference algorithm that looks at the context and gures out the type So what is uncurry 7 It has the type uncurry a A b A c A a b A c We can de ne uncurry as f p f mp mp We can de ne add as add x y x y gt21 add add Num a gt aa gt a gt21 curry add curry add Num a gt a gt a gta Suppose Haskell only has lntls then gtt add add IntInt gt Int gtt curry add curry add Int gt Int gt Int gtt addc addc Int gt Int gt Int We can de ne curry in a new way as cuTTyf I A y A f Ly WCWTyf P A f fst 0 8nd 0 unamyf ltz y a f z y We can also do the following in Haskell addc 5 Int gt Int addc 5 5 Int COSC 3015 Lecture 11 Lecture given by Prof Caldwell and scribed by Sunil Kothari September 307 2008 1 cons vs append cons is the list constructor7 Whereas append glues two lists Hugsgt t 2 2 a gt a gt a Hugs A slightly pathological case is lei Hugsgt 1 a gt a gt a Hugsgt append glues lists on the right cons can only add things to the left 17273 l4l M 127374 Remeber7 append is de ned as l 13 13 y I ys zs yr yszs 1 13 M 1 z 13 M 1118 Cons can be implemented using append but is less ef cient 1 13 13 2 More list functions We talked about the map function earlier mapfll U mapf113 f1mapf13 The following will not work as a de nition since 7777 is not a constructor for lists map f 18 ys map f 18 map f ysi NoteIIPatternrnatching works on patterns speci ed using datatype con structorsi snd xzyzrn y sum 0 sum 1 IS z sum zs pmd ll 0 prod I IS z prod zs concatl Hconcatl 18 zss ms concat zss All these functions follow the following general pattern flle f I IS 1 0p fzs sum 123 1 sum 23 1 2 sum l23sum 1lt2lt30gtgt prod123 1 2 6 3 6 1 COnwtlUL H7 273 l1 H l273l Hgtgt The pattern associates the 77 opw to the right foldquot 0p 6 6 foldquot 0p 6 z IS 1 0p fold39r 0p 1 IS So if we had rnacros7 we could just plug the functions and identity element in th macros to get the above de nition Now we can de ne the above functions using fold sum foldquot 0 prod foldquot 1 concat foldquot H What about the operators that don7t associate to the right 7 For example a 71 7 c f a 7 7 c What if you want a left associative pattern 7 sum 123 0 1 2 3 We need f0le f0le 0p 6 f0le 0p 6 I IS foldl 0p 6 0p zzs The idea is carry the results completed so fat in e starting With e being the identity sum foldl 0 sum 123 foldl 1 0 123 foldl 1 0 1 23 foldl lt1 0 1 2 31 foldl lt1 0 1 2 3 1 ltltlt0123 Note for associative operators 69 With identity 6 foldquot 0p 6 f0le 0p e In general foldl is more ef cient than foldri We can do a fold computation as sum123 foldquot 0 123 1 foldr 0 23 1 2 foldr 0 3 1 2 3 faldr 0 11 1 2 3 0 1 2 3 1 5 6 3 List Comprehensions 1n Haskell strings are just list of charsi Maingt xy x lt 13 y lt quotabcquot 1 a 1 b 1 c 2 a 2 b 2 C 3 a 3 b 3 C If we want to do this in the normal way we have a11pairs ys a11pairs x2xs ys map y gt xy ys allpairs xs ys map 9 A 179 W b l y A 179 a I y A 179 b I l 1a 11b 1 1a 71b l allpai39rsl I IS ys map p ys allpairsl IS ys where p y 17y Maingt xx x lt 1 5 odd x 1 9 25 0 L5 generators 0 odd I guard So what is list comprehension z E S l ln set theory7 this is de nition by comprehension ln general7 e l is a list comprehension where e 7is a Haskell expression Q 7is a comma separated list of generations and guards Generators look like I lt7 18 where z is a variable and IS is a list valued expression and a guard is a boolean valued expressioni List comprehensions are very expressive but add no computational power What is the semnatics There are two rules e l I lt7 13 concat map f zwhere f z 6W Note I had to leave early and so I missed last 57 mins of lecture materiali COSC 3015 Lecture 7 Lecture given by Prof Caldwell and scribed by Sunil Kothari September 167 2008 1 Inductive Datatype data Nat Zero I Succ Nat There is recursion in the datatype equation We are de ning the datatype Nat and in doing so7 use the data type Natl Zero and Succ are constructors for the data type ZeroHNat is a constant of the type nati Succ Nat A Nat is a constant that maps Nats to Nats Maingt 1 Zero Zero Nat Maingt t Succ Zero Succ Zero Nat Maingt To apply the constructor Succ we must have a previously constructed Nat to apply to it What objects have type Nat Nat Zara S39uche ro7 SuccSucher0 This representation goes back to Peano7 an Italian logician and mathemati ciani ln Haskell7 we have the most re ned form of equality instance Eq Nat where Zero Zero True Zero Succ n False Succ n Zero False Succ n Succ m m 11 Maingt 1 Eq agt a gt a gt Bool By default7 we also get not equal to it 2 Eq a gt a gt a gt Bool Maingt If we had said data Nat Zero lSucc Nat deriving Eq Haskell would have derived an equivalent function to one we have writ ten Succ Zero Succ Succ Zero M Zero Succ Zero M False Nat terms have a tree structure We can de ne our own as Nat A Nat A Nat m zero m m Succ n Succ n m Theorem 1 Vm Natm succ 0 succ m Proof Choose an arbitrary m and show m succ 0 succ m Starting wit m succ 0 succ m zero D ltltdefn oi gtgt succ m Similarly7 we can check if zero is same as our notion of 0 in mathematics Theorem 2 Vm Natzero m m Proof by induction on m CI 11 Induction Principle Consider again inductively de ned data type data Nat Zero l Succ Nat deriving Eq The induction principle for Nat as is in the book Case Zero PZe r0 holds Case succ n Assuming Pn holds7 show Psucc n holds What is P7 P 2 Nat A B001 P is a property of natural numbers Another way of thinking this is P0 Vm NatPm Pm 1 Vm NatPm Theorem 3 Vmn Natn m m n By induction on m What is Pm we can look at the statement as Vm7Vn Natin m m n So the property is Pm lg Vn Natlnm mni So we have to show case Pzero Vn Natin zero zer0ni Choose an arbitrary nl LiHSi n zero n by de nition of zero n n by Lemma 1 case PSucc n Assume Pk7 z39e Vn Natn k k n Show PSucc k Vn Natin Sum 16 Sum 16 n Choose arbi n and show that n succ k succ k n On the left7 nSucc k succ n kby defnition of plus succ kn by Pk k succ n On the right7 since Vn NatJL k k n we know succ n k k succ n Lemma 1 Vn Natzero n n Proof By induction on n What is Pn Pn lg zero n n Base case show zero zero zeroi But zero zero zero so the base case holds Induction case show Psucc k assume Pk and show Psucc k Pk lg zero k k Psucc k d f zero succ k succ k Start on the left Psucc 16 lg zero succ k succ zero k succ So the induction principle holds 1 We are trying to prove properties of our recursive programl We are proving properties of our haskell function COSC 3015 Lecture 1 Lectured given by Prof Caldwell and scribed by Sunil Kothari August 267 2008 1 Books and Programming Environments 11 Books for functional programming Haskell is a lazy language Chris Okasaki looked at imperative data structures in a functional setting For example7 binomial trees7 splay trees7 redblack trees7 etc 12 Higherorder Perl by Mark Jason Dominus Lisp has higherorder functions That means7 functions are rst class members You have C Pointers which pint to a piece of code Java has lambda expres sions now There are links to the authors lecture on the web Per16 is being implemented in Haskell 13 Programming Environments There are two implementations o Hugs Haskell Implementation7 choose the editor you want to use 0 GHCi Glasgow Haskell Compiler o Emacs Text editor Dr Caldwell uses emacs as a text editor We will use interpreter even though Haskell programs can be compiled Lets go for Hugs then 2 What is functional programming It s de ned by other programming paradigms 21 Imperative Programming 0 Fortran7 C C7 Ada7 Pascal7 Java7 Basic7 Perl 0 Inherent in this model of programming is the state based computation command base o A computation is a sequence of memory states SOH51gt527gt Objectoriented programming can also be looked as imperative programming It s a kind of data abstraction mechanism built upon imperative or functional programming language eg OCaml Object oriented Caml a functional PL 22 Logic Programming Prolog a variant is Lambda Prolog functional logical hybrid A program is a logical description of a problem to be solved Computation is a form of search for a solution You have to Write description of a problem in the form of Horn clauses Its a kind of a restricted logic 23 Functional Programming Functional programming languages are expression based You Write an expres sion describing the desired solution 7 and computation is the process of evalu ating the expression Here s a Haskell program for Quick sort 231 Lists in Haskell There are two constructors o empty list 0 h hs cons that sticks the value created by h onto the left hand of the list hs For example7 The usage is as follows hue 1 01222HM172l 2zlt1zugtem wry Z wzzyw Z gt VIZ77777222477 232 Append Append 12 34 lt 1234 24 Quick Sort qsort qsort hhs qsort smaller h qsort larger where smaller a I alt hsI a lt h larger blblths I bgth qso rt2 l qso rt2 lt gt qso rtl 2 qsort QSOTtH H1 480Ttll H2 H QSOTtH H1 l HQD 1 l2l lt gt 12 Note that List comprehensions are Haskell macros 25 Typed vs untyped Functional programming languages can be categorized as o Typed Haskell OCaml ML F Supports type inference o Untyped Lisp Scheme 2 6 Type Inference zi gt z 5 is a Haskell expression for the function that adds 5 to the argument I It can also be Written as addSz z 5 The compiler gures out the type of the expression if it has a type gt21 add 5 gt Numa gtagta The Num above is a type class The type for qsort is gt21 qsort gt0rd a gt a gt a Here 0rd is a type class COSC 3015 Lecture 2 Lecture given by Prof Caldwell and scribed by Sunil Kothari September 167 2008 1 Recap We talked about functional Programming vsi Logic programming vsi lmpera tive Programming The rst two categories are declarative qsort qsort hhs qsort smaller h qsort larger where smaller a I alt hs a lt h larger bl b lt hs b gt h This is more declarative than what you would do in Java or Ci This is a very natural description of the problemi The functional languages like ML7 Haskell are strongly typed languages They have type inference Type inference works well with the functional programming languages For example7 gt t qsort 0rd a gt a gt a where7 1 a is a type variable 2 a is the type of lists containing elements of type at We can run qsort as gt qsort reverse 1 10 gt 12345678910 gt qsort reverse a Z gt quotabcdefghijklmnopqrstuvwxyzquot 2 Interaction with the programming environment 3 Functions in Haskell Qthatls an example of things that cannot be compared 7 AzFunctionsi 31 Notation for functions Notation that allows you to write down a function but you don7t have to give a name to a function Haskell expression or functions 1de x x 1 E x gt x 1 where7 o xl is the body of a function We cannot print a function in a resonable way but we can get its type but we can apply the function so x gt x 1 5 returns 6 in Haskell So7 how does a function gets evaluated 7 Arm l5 z lz I 5 lt gt zz 5lz 5 lt gt 5 1 lt gt 6 where7 xx5 is a substitution operationi mapisahigherorder functioni lts typeis map a gt b gt a gt b 0 we know which ways the arrows associate 7 arrows associate to the rightsoagtbgtcisagtbgtc map is de ned as map f l l mapfhzhs fhzmapfhs ln Haskell7 we can use map as Maingt x gt x 1 1 10 234567891011 Maingt t x gtx 1 x gtx1Numagta1 Maingt t infinity infinity a So7 let s back up on what is a function 32 Cartesian Product RemeberAXBltabgtl aEAAbEB 123 gtlt ab lt la gtlt 112 gtlt 2a gtlt 2bgtlt3agtlt3bgt ab gtlt 123 lt al gtlta2 gtlta3gtlt b1 gtlt b2 gtltb3gt ln Haskell ab is a pair if azzA and bzzB AB is the cartesian product if A and B are types Maingt 1 quotabcquot 1 quotabcquot Integer Char Maingt R is a binary relation on A and B if R Q A X B For example A 123 Rlt11 gtlt 12 gtlt 13 gt The proeprty of being a function called functionality for f E A X B is VIAVy2B1fz yAfz 2 gtyz A function is total if VIA3yBlfzy Maingt t x gt if x lt0 then infinity else x x gt if x lt0 then infinity else xNum a 0rd a gt a gt a Maingt x gt if x lt0 then infinity else x 5 Interrupted When a system gives a type it is saying that if the function halts it Will have the type but if it does not halt then it might be unde ned but still it has a type So When we Write f z a A b as a Haskell type we mean that f is a function not necessarily total from domain a to range 1 Here s an example of a function from any type to any other type Maingt t x gt infinity x gt infinity a gt b A lot of Haskellrelated topics are on You39l ube some are Google tech talksl COSC 3015 Lecture 13 Lecture given by Prof Caldwell and scribed by Sunil Kothari October 7 2008 1 Trees Chapter 5 has some really good examples But7 we will move on And we may move to HigherOrder Perl book We will start with Chapter 6 on trees Todayls lecture is a sort of review7 since many of the things discussed here are in 2300 A binary tree is de ned 39 as data Bt ree a Leaf a l Fork Bt ree a Bt ree a So7 herels an example of a tree Fork Leaf 1 Fork Leaf 2 Leaf 3 Maingt 1 Leaf Leaf a gt Btree a You get case statement for free when you create a datatypei For example7 consider the size function size 1 case 1 of Leaf gt 1 Fork xt yt gt size xt size yt Maingt 1 size size Num a gt Btree b gt a So7 case is like a destructor for the datatypei What s the other way of writing it sizel Leaf 1 sizel Fork xt yt sizel xt sizel yt Maingt t sizel sizel Num a gt Btree b gt a Whenever you have a datatype7 you also get a structural induction principle The induction principle for Btree is VI aiPLeaf z Vzt7yt BtTee aiPzt Pyt PFOTk It yt Vt BtTee aiPt 1 VI aiPLeafz base case 2 Vzt yt BtTee aiPzt Pyt PFOTk It yt induction case We also have extra case for partial elements of the type 0 P l De nition 1 A Btree is nite and only sizet l The book says that any nite path through a syntax tree of a recursive datatype is linear For example succ Z 6T0 succ succ Z 6T0 Similar is the case with lists So7 let s look at different trees something used in 2300 data TTTEE a Leaf l Node a TTTEE a TTTEE a Or we can also have a tree with three subtreesi data TTTTEE a Leaf l Node a TTTTEE a TTTTEE a TTTTEE a Q Can we make circular structures 7 A No7 we cant But7 we can de ne Nat as a form of DAG directed acyclic graph dataNat Zero l SNat l SSNat where7 55 k S S k So7 what about the nite induction principle for TTTTEE ai 1i PLeaf base case 2 VI a7Vzt7 yt7 2t BtTee ai Pzt APyt APzt PN0de3 I It yt 2t induction case If we want in nite induction7 we ought to have 131 tooi Let7s de ne flatten flatten Btree a gt a flatten Leaf x x flatten Fork t t flatten t flatten t flatten Node Leaf 1 Node Leaf 2 Leaf flattenLeaf1flattenFOTkLeaf2 Leaf3 1flattenLeaf2flattenLeaf3 111121131 17 2 3 Theorem 1 size lengthiflatten Proof By extensionality we must show Vt Bt ree a7 size t lengthiflatten ti Continue by structural induction on t There are two cases Pleaf We must show VI aiPleaf ie that VI aisi2eleaf z lengthiflatten leaf 1 Choose arbi z E a and s ow si2eleaf z lengthiflattenleaf I On the left size leaf 1 1 On the right lengthiflattenleaf z length flatten leaf length 1 PFOTk IS ys Assume Pzs and Pys and show PFOTk IS ys Pzs size 18 lengthiflatten IS Pys size ys lengthiflatten ys Show sizef039rk IS ys lengthiflatten ork IS ys On the left side sizef07quotk IS ys size 18 size ys lengthiflatten 18 lengthiflatten ys length flatten 13 length flatten ys On the right lengthiflatten fork IS ys comic lengthflatten fork IS ys Hagen lengthflatten zsflatten ys lengthgppend length flatten 13 length flatten ys Note that 77 is a function composition operatori Lemma 1 LengthAppend V137ys a 1 zsys 11 18 1 1 ys 1 We can de ne a function nodes as nodes Leaf 0 nodes Fork xs ys 1 nodes xs nodes ys Then we can prove a theorem Theorem 2 Vzt Bt ree aisize It 1 nodes It Proof By indi on xti PXt 12f size xt 1 nodes xt Again7 we have two cases Case Pleaf x size Leaf x 1 nodes Leaf x LiHiS size Leaf X 1 R H S 1 nodes Leafx 1 0 1 so the base case holds Case PFork XS ys Assume Size XS 1 nodes XS Size yS 1 nodes yS Show Size Fork XS yS 1 nodes XS yS L H S Size Fork XS yS 1 nodes XS 1 nodes yS R H S 1 nodeSFork XS yS 1 1 nodes XS nodes yS

### 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

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### 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.