- 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:
--- extract_headers ??? ---We then observed that it would make sense to abstract the <h1> out of promote_if_h1tag(), to make it more general:
--- promote_if ??? ---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;
return sub {
my $element = shift;
if ($is_interesting->($element->{_tag}) {
return ['keeper', join '', map {$_->[1]} @_];
} else {
return @_;
}
}
}
=contlisting promote_if_curried 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);
=endtestInstead 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 scaleSimilarly, 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 {
my $f = shift;
my $e = 0.00000095367431640625;
return sub {
my $x = shift;
($f->($x+$e) - $f->($x-$e)) / (2*$e);
};
}
=test slope0
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 slope0slope() 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.
=test slope
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 slopeCurrying 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_functionOne 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 jcombine2($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;
my $r;
$r = sub {
my ($s, $t) = @_;
return unless $s && $t;
node($op->(head($s), head($t)),
promise { $r->(tail($s), tail($t)) });
};
}
=test combine2.1
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.1Now 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