Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

When are lambda forms necessary in Haskell?

I'm a newbie to Haskell, and a relative newbie to functional programming. In other (besides Haskell) languages, lambda forms are often very useful.

For example, in Scheme:

(define (deriv-approx f)
  (lambda (h x)
    (/ (- (f (+ x h)
          (f x)
       h)))

Would create a closure (over the function f) to approximate a derivative (at value x, with interval h). However, this usage of a lambda form doesn't seem to be necessary in Haskell, due to its partial application:

deriv-approx f h x = ( (f (x + h)) - (f x) ) / h

What are some examples where lambda forms are necessary in Haskell?

Edit: replaced 'closure' with 'lambda form'

like image 937
Matt Fenwick Avatar asked Aug 18 '11 21:08

Matt Fenwick


People also ask

What is lambda calculus in Haskell?

When talking about Haskell, the term “lambda calculus” often crops up. It's a theoretical framework used to define the meaning of computation in many functional languages, such as Haskell, Agda, Idris, etc. Understanding lambda calculus can be very helpful when talking about programs written in these languages.

What does lambda do in Haskell?

λ-expressions (λ is the small Greek letter lambda) are a convenient way to easily create anonymous functions — functions that are not named and can therefore not be called out of context — that can be passed as parameters to higher order functions like map, zip etc.


1 Answers

I'm going to give two slightly indirect answers.

First, consider the following code:

module Lambda where

derivApprox f h x = ( (f (x + h)) - (f x) ) / h

I've compiled this while telling GHC to dump an intermediate representation, which is roughly a simplified version of Haskell used as part of the compilation process, to get this:

Lambda.derivApprox
  :: forall a. GHC.Real.Fractional a => (a -> a) -> a -> a -> a
[LclIdX]
Lambda.derivApprox =
  \ (@ a) ($dFractional :: GHC.Real.Fractional a) ->
    let {
      $dNum :: GHC.Num.Num a
      [LclId]
      $dNum = GHC.Real.$p1Fractional @ a $dFractional } in
    \ (f :: a -> a) (h :: a) (x :: a) ->
      GHC.Real./
        @ a
        $dFractional
        (GHC.Num.- @ a $dNum (f (GHC.Num.+ @ a $dNum x h)) (f x))
        h

If you look past the messy annotations and verbosity, you should be able to see that the compiler has turned everything into lambda expressions. We can consider this an indication that you probably don't need to do so manually.

Conversely, let's consider a situation where you might need lambdas. Here's a function that uses a fold to compose a list of functions:

composeAll :: [a -> a] -> a -> a
composeAll = foldr (.) id

What's that? Not a lambda in sight! In fact, we can go the other way, as well:

composeAll' :: [a -> a] -> a -> a
composeAll' xs x = foldr (\f g x -> f (g x)) id xs x

Not only is this full of lambdas, it's also taking two arguments to the main function and, what's more, applying foldr to all of them. Compare the type of foldr, (a -> b -> b) -> b -> [a] -> b, to the above; apparently it takes three arguments, but above we've applied it to four! Not to mention that the accumulator function takes two arguments, but we have a three argument lambda here. The trick, of course, is that both are returning a function that takes a single argument; and we're simply applying that argument on the spot, instead of juggling lambdas around.

All of which, hopefully, has convinced you that the two forms are equivalent. Lambda forms are never necessary, or perhaps always necessary, because who can tell the difference?

like image 80
C. A. McCann Avatar answered Sep 20 '22 17:09

C. A. McCann