Haskell

Lambda Functions

7. (8 = 6 + 2 points)

a. Rewrite f g x y = g x (y x) three ways, first f g x = unnamed lambda function, then f g = unnamed lambda function, and finally f = unnamed lambda function.

b. Briefly, how does var = lambda function relate to first-class functions in Haskell?

More Information (Exmaples)

Lambda (Unnamed) Functions and the Lambda Calculus) (LYaH Ch.6 p.9] It can be annoying to write a function like multiple_of_3 just to use it in one spot. We can use unnamed functions instead. Below, \x-> x `mod` 3 == 0 is a function that takes an x and returns true if x mod 3 is zero. > -- divisible_by_3 x = x 'mod 3 == 0 > -- divisible_by_3 = x -> x mod 3 == 0 -- same as previous line > divisible_by_36 True > filter (1 x -> x `mod` 3 == 0) [27..83] [27,30,33,36,39,42,45,48,51,54,57,60,63,66,69,72,75,78,81] The lambda calculus discusses function definition and execution using unnamed, lambda functions. A lambda function tells you how to calculate a result given an argument but it doesn't give the function a name. (Hence, "unnamed" function.) Notation: 2. id.expr means "a function that takes a value for the identifier and yields the value of the expression. (The expression is also called the body.) Example: 2 x.x is the identity function. The body can itself be a function. E.g.,af. x. f(x) is the f squared function (f2=fof). Iterated a functions can be abbreviated: fx.fx) means a f. x. f(x) The Haskell notation for a id.expr is \id -> expr. (Backslash is used for lambda and the arrow separates the identifier and body.) E.g., \f->\x-> (f x) is the Haskell notation for f. 2x. f(x). Iterated lambdas can be abbreviated: E.g., \fx-> f(fx) means 2fx.f(fx). Haskell function definitions as syntactic sugar: A function declaration like f x = exp is short for the definition f= \x -> exp. This is one way in which Haskell supports first-class functions: Aside from the pleasant syntax, a function definition is just like a declaration of any other variable. Declaring id = expr works the same way regardless of whether the expression is a primitive Int or a pair or list or (now, we see) even a function. So these all have the same meaning: > f a b c = a + b + c > f = la b c -> a * b + c > f = la -> \b -> \c -> a * b + c > f 358 23 Referential transparency and lambda application": (1x -> expr) arg turns into the expr with arg replacing x everywhere. E.g., with f = \a -> \b -> lc -> a + b + c, f 3 is \b -> lc -> 3 * b + c . f35 is lc -> 3 * 5 + c f 3 5 8 is 3 * 5 + 8 evaluates to 23 When we have f a b c = a + b + c and replace f 35 8 by 3 * 5 + 8, we're doing the same thing as the above (just faster). Using lambdas in Haskell: Lambdas are very useful for short things you use once. Why define > positive x = x > 0 -- usual definition syntax > positive = \x -> x > 0 -- using lambda > filter positive [3, 5, -1, 2, -9, 7, -2, -3] [3,5,2,7] > filter (\x -> x > 0) (3, 5, -1, 2, -9, 7, -2, -3] [3,5,2,7] Lambda (Unnamed) Functions and the Lambda Calculus) (LYaH Ch.6 p.9] It can be annoying to write a function like multiple_of_3 just to use it in one spot. We can use unnamed functions instead. Below, \x-> x `mod` 3 == 0 is a function that takes an x and returns true if x mod 3 is zero. > -- divisible_by_3 x = x 'mod 3 == 0 > -- divisible_by_3 = x -> x mod 3 == 0 -- same as previous line > divisible_by_36 True > filter (1 x -> x `mod` 3 == 0) [27..83] [27,30,33,36,39,42,45,48,51,54,57,60,63,66,69,72,75,78,81] The lambda calculus discusses function definition and execution using unnamed, lambda functions. A lambda function tells you how to calculate a result given an argument but it doesn't give the function a name. (Hence, "unnamed" function.) Notation: 2. id.expr means "a function that takes a value for the identifier and yields the value of the expression. (The expression is also called the body.) Example: 2 x.x is the identity function. The body can itself be a function. E.g.,af. x. f(x) is the f squared function (f2=fof). Iterated a functions can be abbreviated: fx.fx) means a f. x. f(x) The Haskell notation for a id.expr is \id -> expr. (Backslash is used for lambda and the arrow separates the identifier and body.) E.g., \f->\x-> (f x) is the Haskell notation for f. 2x. f(x). Iterated lambdas can be abbreviated: E.g., \fx-> f(fx) means 2fx.f(fx). Haskell function definitions as syntactic sugar: A function declaration like f x = exp is short for the definition f= \x -> exp. This is one way in which Haskell supports first-class functions: Aside from the pleasant syntax, a function definition is just like a declaration of any other variable. Declaring id = expr works the same way regardless of whether the expression is a primitive Int or a pair or list or (now, we see) even a function. So these all have the same meaning: > f a b c = a + b + c > f = la b c -> a * b + c > f = la -> \b -> \c -> a * b + c > f 358 23 Referential transparency and lambda application": (1x -> expr) arg turns into the expr with arg replacing x everywhere. E.g., with f = \a -> \b -> lc -> a + b + c, f 3 is \b -> lc -> 3 * b + c . f35 is lc -> 3 * 5 + c f 3 5 8 is 3 * 5 + 8 evaluates to 23 When we have f a b c = a + b + c and replace f 35 8 by 3 * 5 + 8, we're doing the same thing as the above (just faster). Using lambdas in Haskell: Lambdas are very useful for short things you use once. Why define > positive x = x > 0 -- usual definition syntax > positive = \x -> x > 0 -- using lambda > filter positive [3, 5, -1, 2, -9, 7, -2, -3] [3,5,2,7] > filter (\x -> x > 0) (3, 5, -1, 2, -9, 7, -2, -3] [3,5,2,7]