Specializing Functions with Currying

[FoxtrotUniform]

Let's pretend: we're writing a markup-translation backend. The front end has taken the input text and transformed it into a bunch of paragraphs, each one a list of (style, content) pairs. For instance, a paragraph might look like

my @test_data = (
    ['none', 'The quick brown '],
    ['bold', 'fox'], 
    ['none', ' jumped '],
    ['ital', 'over'],
    ['none', ' the lazy '],
    ['bold', 'dog'], 
    ['none', '.']
);

Our task is to generate HTML from these paragraphs.

One obvious WTDI is to build a dispatch table of translation functions:

my %handlers = (
    'none' => sub {shift},
    'bold' => \&wrap_with_b_tags,
    'ital' => \&wrap_with_i_tags,
    'para' => \&wrap_with_p_tags,
);

sub build_para
{
    my ($data) = @_;

    my $text = '';

    for (@$data) {
        $text .= $handlers{$_->[0]}->($_->[1]);
    }

    return $handlers{'para'}->($text);
}

That's all well and good, but those wrap_with_foo_tags functions are all going to be variations on a theme. That's going to suck if we ever want to extend them (to allow for CSS classes, for instance). What we'd like to be able to do is something like

sub wrap_with_html
{
    my ($tag, $text) = @_;

    return "<$tag>$text</$tag>";
}

my %handlers = (
    'none' => sub {shift},
    'bold' => \&wrap_with_html('b', # partial funcall
    'ital' => \&wrap_with_html('i',
    'para' => \&wrap_with_html('p',
);

but of course that won't work. Will it?

Enter currying. Currying is basically partial application of a function: instead of supplying all of a function's arguments and getting a result back, you supply part of a function's arguments and get a function back. When you apply that curried function to the rest of the arguments, you get the result you expected.

educated_foo has a pretty clever currying implementation here, but for my purposes this should be sufficient:

sub curry
{
    my ($func, @args) = @_;

    return sub {
        my (@rest) = @_;
        &$func(@args, @rest); 
    }
}

# Currying:

sub foo
{
    my ($x, $y) = @_;

    print "$x + $y = ", $x + $y, "\n";
}

my $plus_five = &curry(\&foo, 5);

&$plus_five(3);

It's not pretty, nor is it especially safe, but it works.

Now we can have our cake and eat it, too: a pleasantly general wrap_with_html function, a dispatch table full of specialized functions (which, I might add, we can generate from a config file if we so desire), a distinct lack of superfluous wrapper code, and a bunch of coderefs to confuse the newbies. (Okay, that last is a bug, not a feature. That's the major drawback to currying: it's not easy to understand from a procedural point of view.) Our full code looks like this:

sub curry
{
    my ($func, @args) = @_;

    return sub {
        my (@rest) = @_;
        &$func(@args, @rest);
    }
}

my %handlers = (
    'none' => sub {shift},
    'bold' => &curry(\&wrap_with_html, 'b'),
    'ital' => &curry(\&wrap_with_html, 'i'),
    'para' => &curry(\&wrap_with_html, 'p'),
);

sub wrap_with_html
{
    my ($tag, $text) = @_;

    return "<$tag>$text</$tag>";
}

sub build_para
{
    my ($data) = @_;

    my $text = '';

    for (@$data) {
        $text .= $handlers{$_->[0]}->($_->[1]);
    }

    return $handlers{'para'}->($text);
}

my @test_data = (
    ['none', 'The quick brown '],
    ['bold', 'fox'],
    ['none', ' jumped '],
    ['ital', 'over'],
    ['none', ' the lazy '],
    ['bold', 'dog'],
    ['none', '.']
);

print &build_para(\@test_data);

I should point out that this is a bit of a toy example: it might be better to use qred regexes in a lookup table instead, for instance. I didn't want to clutter the code with more complexity than I needed; but the nice thing about this approach is that if you ever have to make wrap_with_html more complex, you don't really have to change anything else.

[diotalevi]

I would have just said this in perlish instead of Haskelish. I think you'll communicate better to perl people if you stop using the verb currying and use the noun closure instead. Its just the perl localism and it is how they are typically talked about.

bold => sub { wrap_with_html( b => @_ ) };

# vs

bold => curry \ &wrap_with_html => 'b';

[tilly]

Using the wrong word will not help you communicate.

Talking about currying is not exactly the same as talking about closures. Currying is a specific programming technique that can be implemented with closures. Currying is the idea that if I have some arguments for a function now, and will have more later, that I can right now generate a closure that has pre-bound some arguments and avoid having to pass around the arguments everywhere. Thus a curried function is a specific type of closure. A closure is somewhat more general though - for instance you can have multiple closures that privately communicate through their shared environment.

The distinction may become more apparent in Perl 6 because they are adding support to give a direct syntax for currying. And you'll see that sometimes that syntax is enough, and other times you'll want to do extra work and create a closure by hand. (In Perl 5, of course, when you want to curry it is often simpler just to create a closure by hand.)

[zby]

I find your example simpler than the original. But I need to object the dismissal of the verb 'currying' as it is a very basic vocabulary from Computing Science, much more basic than 'closure'.

[diotalevi]

Ok, well my understanding of computer science is limited. In perl we implement currying with anonymous function and as such, talk about anonymous functions much more often than currying. What part of currying in perl am I not understooding when I say "anonymous function?" Also, what part of language/implementation independent currying am I not understanding when I think of an anonymous function in perl?

I changed my term from "closure" to "anonymous function" because while closures are anonymous functions, they go slightly farther by having a lexical environment and anonymous functions don't necessarily have that.

[FoxtrotUniform]

Fair enough. It's not the case that currying is equivalent to making a closure, though (currying is more specific), but that's a minor point. The idea here is to describe a way to avoid the parameter-handling that comes with general-purpose functions, with as little lookup fuss as possible.

More generally, I'm turning into a functional-programming evangelist, and since Perl makes it easy to use a lot of my favourite techniques I'm writing about them here. Go up a meta-level from my OP, and what I'm talking about is building functions on an ad-hoc basis (compare to the static "functions are global named objects and part of the design document" world of straight procedural programming). Whether you use literal subs or build higher order functions to do it is less important than being aware of the possibility.

[leriksen]

good description of currying - it took me ages to understand this concept (through studies of Scheme, Lisp and Haskell over the years), and it didnt finally twig until I was having to extend some legacy C code here - at one point in the code I knew I would eventually call a key function, but I didn't have all the information in scope right then. I remember thinking 'if only I could have a new function that called that one, using the arguments I have now, and the arguments the new function _will_ have in scope when it gets invoked - I could just pass a function pointer to that new function, instead of chaining all these parameters together and passing long parameter lists around...hey!!'

another good name is 'partial application of functions' - your calling it with a partial list of parameters...

any idea how you would do multiple application of these attributes - e.g. bold _and_ italic

[Aristotle]

It's not really doable with the simpleminded curry() used here. You'll have to construct this manually.

    'boldital' => do {
        my $i = curry \&wrap_with_html => ( 'i' );
        my $b = curry \&wrap_with_html => ( 'b' );
        sub { $b->( $i->( @_ ) ) }
    },

[FoxtrotUniform]

 'boldital' => do {
    my $i = curry \&wrap_with_html => ( 'i' );
    my $b = curry \&wrap_with_html => ( 'b' );
    sub { $b->( $i->( @_ ) ) }
},

Neat use of =>. As for composition, as an inveterate Haskell hacker (well, hacker-wannabe), I'd prefer to have that as a primitive, too:

sub compose
{
   my ($f, $g) = @_;

   return sub { $f->($g->(@_)); }
}

# ...

'boldital' => &compose(&curry(\&wrap_with_html, 'i'),
                       &curry(\&wrap_with_html, 'b')),

The idea of functions that operate on functions and return other functions is much more useful than it first seemed to me. If you never think about functions as first-class objects, having a compose function seems incredibly redundant. Once you start building functions on-the-fly, composition becomes indispensible.

I guess I should write part 2 of my Perlesque Intro to Haskell, then.

[thor]

It's not really doable with the simpleminded curry() used here.

Perhaps I'm missing something, but what if you did this:

my %handler = (
   "bold_italic" =  curry(\&wrap_with_html,"b><i"),
);

[stvn]

Another favorite higher order function of mine is right curry:

sub rcurry {
    my ($f, @args) = @_;
    return sub { $f->(@_, @args) };
}

*company_name = &rcurry(\&wrap_with_html, "FoxTrotUniform Inc.");

print company_name('B');
print company_name('I');
print company_name('H1');

And these are nice function builders from Dylan.

sub conjoin {
    my ($f, $f2) = @_;
    return sub { $f->(@_) && $f2->(@_) }
}

sub disjoin {
    my ($f, $f2) = @_;
    return sub { $f->(@_) || $f2->(@_) }
}

*company_name_better = disjoin(
     conjoin(
         sub { return 1 if scalar @_ == 0 },
         curry(\&company_name, 'H1')
     ),
     \&company_name
);

print company_name_better('B');
print company_name_better();

And of course, if you really want to make your head spin, there is always combinators.

[tmoertel]

You could always take it one step further and curry the call to curry, eliminating further redundancy:

*wrap_with_tag = curry( \&curry, \&wrap_with_html );

my %handlers = (
    'none' => sub {shift},
    'bold' => wrap_with_tag('b'),
    'ital' => wrap_with_tag('i'),
    'para' => wrap_with_tag('p'),
);

[stvn]

FoxTrotUniform,

Nothing like a good meditation on functional programming to clean out the OOP cobwebs in ones head. Thanks :)

You could make your build_para sub even more Haskell-ish if you removed all assignment statements as well.

sub build_para
{
    return $handlers{'para'}->(join "" => map { $handlers{$_->[0]}->($
+_->[1]) } @{$_[0]});
}

But if we are really gonna get functional, then we might as well make a generic build_HTML sub and use more recursive datastructures.

my @test_data_2 = ( 'para', [
    ['none', 'The quick brown '],
    ['bold', 'fox'],
    ['none', ' jumped '],
    ['ital', 'over'],
    ['none', ' the lazy '],
    ['bold', 'dog'],
    ['none', '.']
    ]
);

sub build_HTML {
    join "" => map {
        (ref($_->[1]) eq "ARRAY") ?
            $handlers{$_->[0]}->(build_HTML(@{$_->[1]}))
            :
            $handlers{$_->[0]}->($_->[1])
    } ref($_[0]) ? @_ : ([ @_ ]);
}

print build_HTML(@test_data_2);

We could then actually use build_HTML to compose the build_para subroutine.

*build_para = curry(\&build_HTML, 'para');
print build_para(\@test_data);

[kabel]

i do not know if this is useful for anything, but

sub curry2 {
    my ($fn, $argstack) = @_;

    defined $argstack or $argstack = [];

    return sub {
        my $arg = shift;
        if (defined $arg) {
            return curry2 ($fn, [@$argstack, $arg]);
        } else {
            $fn->(@$argstack);
        }
    };
}

transforms a function f into a function which can be positionally parametrised, though named would pose too no problems. sample usage:

my $myprint = sub { print @_; };
my $curry = curry2 ($myprint);
$curry->("a")->("b")->("c")->();