Fun with Lambdas

Question

Not having them used them all that much I'm not quite sure all that lambdas/blocks can be used for (other than map/collect/do/lightweight local function syntax). If some people could post some interesting but somewhat understandable examples (with explanation).

preferred languages for examples: python, smalltalk, haskell

Answer 1

You can make a functional data structure out of lambdas. Here is a simple one - a functional list (Python), supporting add and contains methods:

empty = lambda x : None

def add(lst, item) :
    return lambda x : x == item or lst(x)

def contains(lst, item) :
    return lst(item) or False

I just coded this quickly for fun - notice that you're not allowed to add any falsy values as is. It also is not tail-recursive, as a good functional structure should be. Exercises for the reader!

Answer 2

You can use them for control flow. For example, in Smalltalk, the "ifTrue:ifFalse:" method is a method on Boolean objects, with a different implementation on each of True and False classes. The expression

someBoolean ifTrue: [self doSomething] ifFalse: [self doSomethingElse]

uses two closures---blocks, in [square brackets] in Smalltalk syntax---one for the true branch, and one for the false branch. The implementation of "ifTrue:ifFalse:" for instances of class True is

ifTrue: block1 ifFalse: block2
    ^ block1 value

and for class False:

ifTrue: block1 ifFalse: block2
    ^ block2 value

Closures, here, are used to delay evaluation so that a decision about control flow can be taken, without any specialised syntax at all (besides the syntax for blocks).

Haskell is a little different, with its lazy evaluation model effectively automatically producing the effect of closures in many cases, but in Scheme you end up using lambdas for control flow a lot. For example, here is a utility to retrieve a value from an association-list, supplying an optionally-computed default in the case where the value is not present:

(define (assq/default key lst default-thunk)
  (cond
    ((null? lst) (default-thunk)) ;; actually invoke the default-value-producer
    ((eq? (caar lst) key) (car lst))
    (else (assq/default key (cdr lst) default-thunk))))

It would be called like this:

(assq/default 'mykey my-alist (lambda () (+ 3 4 5)))

The key here is the use of the lambda to delay computation of the default value until it's actually known to be required.

See also continuation-passing-style, which takes this to an extreme. Javascript, for instance, relies on continuation-passing-style and closures to perform all of its blocking operations (like sleeping, I/O, etc).

ETA: Where I've said closures above, I mean lexically scoped closures. It's the lexical scope that's key, often.

Answer 3

You can use a lambda to create a Y Combinator, that is a function that takes another function and returns a recursive form of it. Here is an example:

def Y(le):
    def _anon(cc):
        return le(lambda x: cc(cc)(x))
    return _anon(_anon)

This is a thought bludgeon that deserves some more explanation, but rather than regurgitate it here check out this blog entry (above sample comes from there too).

Answer 4

An example in Haskell to compute the derivative of a single variabled function using a numerical approximation:

deriv f = \x -> (f (x + d) - f x) / d
  where
    d = 0.00001

f x = x ^ 2
f' = deriv f -- roughly equal to f' x = 2 * x

Answer 5

Its C#, but I personally get a kick out of this article every time I read it:

Building Data out of Thin Air - an implementation of Lisp's cons, car, and cdr functions in C#. It shows how to build a simple stack data structure entirely out of lambda functions.

Answer 6

It isn't really quite the same concept as in haskell etc, but in C#, the lambda construct has (optionally) the ability to compile to an objcet model representing the code (expression-trees) rather than code itself (this is itself one of the cornerstones of LINQ).

This in turn can lead to some very expressive meta-programming opportunities, for example (where the lambda here is expressing "given a service, what do you want to do with it?"):

var client = new Client<ISomeService>();
string captured = "to show a closure";
var result = client.Invoke(
    svc => svc.SomeMethodDefinedOnTheService(123, captured)
);

(assuming a suitable Invoke signature)

There are lots of uses for this type of thing, but I've used it to build an RPC stack that doesn't require any runtime code generation - it simply parses the expression-tree, figures out what the caller intended, translates it to RPC, invokes it, gathers the response, etc (discussed more here).