- Constraint Systems
- Local Propagation Networks
- Linear Equations
`linogram`: a drawing system- Conclusion

## Currying

We have seen several times so far how to use callbacks to parametrize the behavior of a function so that it can serve many purposes. For example, in Section ??? we saw how a generic directory-walking function could be used to print a list of dangling symbolic links, to return a list of interesting files, or to copy an entire directory.

Callbacks are a way to make functions more general by supplying other
functions to them as arguments. We saw how to write functions that
used closures to generate other functions as return values. The
*currying* technique we'll see combines closures and callbacks,
turning an ordinary function into a factory that manufactures
functions on demand.

Recall our `walk_html()` function from Chapter ???. Its
arguments were an HTML tree and a pair of callbacks, one to handle
plain text and one to handle tagged text. We had found a way to use
this to extract all the text that was enclosed in `<h1>` tags:

We then observed that it would make sense to abstract the `<h1>` out of
`promote_if_h1tag()`, to make it more general:

The second callback in `walk_html()` is rather peculiar. It's an
anonymous function that we manufactured solely to call `promote_if()`
with the right arguments. The previous version of the code was
tidier. What we need is a way to get `promote_if()` to *manufacture*
the `promote_if_h1tag()` function we need. This seems like it should
be possible, since after all `promote_if()` already knows how to
perform the task that we want `promote_if_h1tag()` to perform. All
that we need to do is to have `promote_if()` wrap up that behavior into
a new function:

Download code for `promote_if_curried`

sub promote_if { my $is_interesting = shift;=contlisting promote_if_curriedreturn sub {my $element = shift; if ($is_interesting->($element->{_tag}) { return ['keeper', join '', map {$_->[1]} @_]; } else { return @_; }}}

Instead of accepting both arguments right away, `promote_if()` now gets
the `$is_interesting` callback only, and manufactures a new function
that, given an HTML element, promotes it if it's considered
interesting. Making this change to `promote_if()`, to turn it from a
function of two arguments into a function of one argument that returns
a function of one argument, is called *currying* it, and the
version of `promote_if()` immediately above is the *curried* version
of `promote_if()`. [1]

The happy outcome is that the call to `walk_html()` is now much simpler:

my @tagged_texts = walk_html($tree, sub { ['maybe', $_[0]] }, promote_if('h1'), });

Once you get used to the idea of currying, you start to see
opportunities to do it all over. Recall our functions from Chapter ??? for adding and multiplying two streams together
element-by-element: `add2()` and `mul2()`.

sub add2 { my ($s, $t) = @_; return unless $s && $t; node(head($s) + head($t), promise { add2(tail($s), tail($t)) }); } sub mul2 { my ($s, $t) = @_; return unless $s && $t; node(head($s) * head($t), promise { mul2(tail($s), tail($t)) }); }

These functions are almost identical. We saw in Chapter ???
that two functions with similar code can often be combined into a
single function that accepts a callback parameter. In this case, the
callback, `$op`, specifies the operation to use to combine
`head($s)` and `head($t)`:

sub combine2 { my ($s, $t, $op) = @_; return unless $s && $t; node($op->(head($s), head($t)), promise { combine2(tail($s), tail($t), $op) }); }

Now we can build `add2()` and `mul2()` from `combine2()`:

sub add2 { combine2(@_, sub { $_[0] + $_[1] }) } sub mul2 { combine2(@_, sub { $_[0] * $_[1] }) }

Since a major use of `combine2()` is to manufacture such functions, it
would be more convenient for `combine2()` to do what we wanted in the
first place. We can turn `combine2()` into a factory that manufactures
stream-combining functions by currying it:

sub combine2 {my $op = shift;return sub {my ($s, $t) = @_;return unless $s && $t; node($op->(head($s), head($t)),promise { combine2($op)->(tail($s), tail($t)) });};}

Now we simply have

$add2 = combine2(sub { $_[0] + $_[1] }); $mul2 = combine2(sub { $_[0] * $_[1] });

This may also be fractionally more efficient, since we won't have to do
an extra function call every time we call `add2()` or `mul2()`. `add2()`
is the function to add the two streams, rather than a function that
re-invokes `combine2()` in a way that adds two streams.

If we want these functions to stick around, we can give them names, as above; alternatively, we can use them anonymously:

my $catstrs = combine2(sub { "$_[0]$_[1]" })->($s, $t);=test catstrs

use Stream qw(:all); do 'combine2'; my $s = upto(1,4); my $t = upto(5,9); my $catstrs = combine2(sub { "$_[0]$_[1]" })->($s, $t); for my $want (qw(15 26 37 48)) { is(head($catstrs),$want); $catstrs = tail($catstrs); } is($catstrs,undef);=endtest

Instead of the `scale()` function we saw earlier, we might prefer this
curried version:

sub scale { my $s = shift; return sub { my $c = shift; return if $c == 0; transform { $_[0] * $c } $s; } }

`scale()` is now a function factory. Instead of taking a stream and a
number and returning a new stream, it takes a stream and manufactures
a function that produces new streams. `$scale_s = scale($s)` returns
a function for scaling `$s`; given a numeric argument, say `$n`,
`$scale_s` produces a stream that has the elements of `$s` scaled
by `$n`. For example `$scale_s->(2)` returns a stream whose every
element is twice `$s`'s, and `$scale_s->(3)` returns a stream whose
every element is three times `$s`'s. If we're planning to scale the
same stream by several different factors, it might make sense to have
a single scale function to generate all the outputs.

Depending on how we're using it, we might have preferred to curry the function arguments in the other order:

sub scale {my $c = shift;return sub {my $s = shift;transform { $_[0] * $c } $s; } }

Now `scale()` is a factory for manufacturing scaling functions.
`scale(2)` returns a function which takes any stream and doubles it;
`scale(3)` returns a function which takes any stream and triples it.
We could write `$double = scale(2)` and then use `$double->($s)` to
double `$s`, or `scale(2)->($s)` to double `$s`.

If you don't like the extra arrows in `$double->($s)` you can get
rid of them by using Perl's *glob* feature:

*double = scale(2); $s2 = double($s);=test scale

use Stream qw(:all); do 'scale'; my $double = scale(2); my $triple = scale(3); my $s = upto(1,3); my $s2 = $double->($s); my $s3 = $triple->($s); for my $want (qw(2 4 6)) { is(head($s2),$want); $s2 = tail($s2); } is($s2,undef); for my $want (qw(3 6 9)) { is(head($s3),$want); $s3 = tail($s3); } is($s3,undef);=endtest scale

Similarly, in Chapter ???, we defined a `slope()` function
that returned the slope of some other function at a particular point:

sub slope { my ($f, $x) = @_; my $e = 0.00000095367431640625; ($f->($x+$e) - $f->($x-$e)) / (2*$e); }

We could make this more flexible by currying the `$x` argument:

sub slope {=test slope0my $f = shift;my $e = 0.00000095367431640625;return sub {my $x = shift;($f->($x+$e) - $f->($x-$e)) / (2*$e);};}

do 'slope0'; my $d1 = slope( sub { 2 * $_[0] } ); is($d1->(3) ,2); is($d1->(-1233),2); my $d2 = slope( sub { cos( $_[0] ) } ); is(int(10000*$d2->(0)) ,int(10000*-sin(0))); is(int(10000*$d2->(.1)) ,int(10000*-sin(.1))); is(int(10000*$d2->(3.14)) ,int(10000*-sin(3.14)));=endtest slope0

`slope()` now takes a function and returns its derivative function! By
evaluating the derivative function at a particular point, we compute
the slope at that point.

If we like, we can use Perl's polymorphism to put both behaviors into the same function:

sub slope { my $f = shift; my $e = 0.00000095367431640625;my $d = sub {my ($x) = shift; ($f->($x+$e) - $f->($x-$e)) / (2*$e); };return @_ ? $d->(shift) : $d;}

Now we can call `slope($f, $x)` as before, to compute the slope of
`$f` at the point `$x`, or we can call `slope($f)` and get back the
derivative function of `$f`.

do 'slope'; my $d1 = slope( sub { 2 * $_[0] } ); is($d1->(3) ,2); is($d1->(-1233),2); is(slope( sub { 2 * $_[0] }, 12345 ), 2 );; my $d2 = slope( sub { cos( $_[0] ) } ); is(int(10000*$d2->(0)) ,int(10000*-sin(0))); is(int(10000*$d2->(.1)) ,int(10000*-sin(.1))); is(int(10000*$d2->(3.14)) ,int(10000*-sin(3.14)));=endtest slope

Currying can be a good habit to get into. Earlier, we wrote

sub iterate_function { my ($f, $x) = @_; my $s; $s = node($x, promise { &transform($f, $s) }); }

But it's almost as easy to write it this way instead:

Download code for `iterate_function`

sub iterate_function {my $f = shift;return sub {my $x = shift;my $s; $s = node($x, promise { &transform($f, $s) });};}

It requires hardly any extra thought to do it this way, and the payoff
is substantially increased functionality. We now have a function
which manufactures stream-building functions to order. We could
construct `upfrom()` as a special case of `iterate_function()`, for
example:

*upfrom = iterate_function(sub { $_[0] + 1 });

Or similarly, our earlier example of `pow2_from()`:

*pow2_from = iterate_function(sub { $_[0] * 2 });=test iterate_function

use Stream qw(:all); do 'iterate_function'; *upfrom = iterate_function(sub { $_[0] + 1 }); *pow2_from = iterate_function(sub { $_[0] * 2 }); my $from3toinfinity = upfrom(3); for (qw(3 4 5)) { is( head($from3toinfinity) , $_); $from3toinfinity = tail($from3toinfinity); } # we're not going to infinity my $andbeyond = pow2_from->(4); for (qw(4 8 16 32 64)) { is( head($andbeyond), $_); $andbeyond = tail($andbeyond); }=endtest iterate_function

One final lexical point about currying: when currying a recursive
function, it's often possible to get a small time and memory
performance improvement by tightening up the recursion. For example,
consider `combine2()` again:

sub combine2 { my $op = shift; return sub { my ($s, $t) = @_; return unless $s && $t; node($op->(head($s), head($t)), promise { combine2($op)->(tail($s), tail($t)) }); }; }

`combine2($op)` will return the same result function every time. So
we should be able to get a speedup by caching its value and using the
cached value in the promise instead of repeatedly calling
j`combine2($op)`. Moreover, `combine2($op)` is precisely the value
that `combine2()` is about to return anyway. So we can change this to:

sub combine2 { my $op = shift;=test combine2.1my $r;$r = sub {my ($s, $t) = @_; return unless $s && $t; node($op->(head($s), head($t)),promise { $r->(tail($s), tail($t)) });}; }

use Stream qw(:all); do 'combine2.1'; my $s = upto(1,4); my $t = upto(5,9); my $catstrs = combine2(sub { "$_[0]$_[1]" })->($s, $t); for my $want (qw(15 26 37 48)) { is(head($catstrs),$want); $catstrs = tail($catstrs); } is($catstrs,undef);=endtest combine2.1

Now the promise no longer needs to call `combine2()`; we've cached the
value that `combine2()` is about to return by storing it in `$r`, and
the promise can call `$r` directly. The code is also more
perspicuous this way: now the promise says explicitly that the
function will be calling itself on the tails of the two streams.

These curried functions are examples of *higher-order functions*.
Ordinary functions operate on values: You put some values in, and you
get some other values out. Higher-order functions are functions that
operate on other functions: You put some functions in, and you get
some other functions out. For example, in `combine2()` we put in a
function to operate on two scalars and we got out an analogous
function to operate on two streams.

TOP