Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

Specializing Functions with Currying

by FoxtrotUniform (Prior)
on Aug 06, 2004 at 00:42 UTC ( [id://380421]=perlmeditation: print w/replies, xml ) Need Help??

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.

--
F o x t r o t U n i f o r m
Found a typo in this node? /msg me
% man 3 strfry

Replies are listed 'Best First'.
Re: Specializing Functions with Currying
by diotalevi (Canon) on Aug 06, 2004 at 04:38 UTC

    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';
      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.)

      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'.

        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.

      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.

      --
      F o x t r o t U n i f o r m
      Found a typo in this node? /msg me
      % man 3 strfry

Re: Specializing Functions with Currying
by leriksen (Curate) on Aug 06, 2004 at 02:53 UTC
    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

    use brain;

      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->( @_ ) ) } },

      Makeshifts last the longest.

        '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.

        --
        F o x t r o t U n i f o r m
        Found a typo in this node? /msg me
        % man 3 strfry

        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"), );

        thor

        Feel the white light, the light within
        Be your own disciple, fan the sparks of will
        With all of us waiting, your kingdom will come

Re: Specializing Functions with Currying
by stvn (Monsignor) on Aug 06, 2004 at 14:17 UTC

    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.

    -stvn
Double-curried goodness
by tmoertel (Chaplain) on Aug 06, 2004 at 21:46 UTC
    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'), );
Re: Specializing Functions with Currying
by stvn (Monsignor) on Aug 06, 2004 at 16:30 UTC
    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);

    -stvn
Re: Specializing Functions with Currying
by kabel (Chaplain) on Aug 06, 2004 at 05:48 UTC
    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")->();

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlmeditation [id://380421]
Approved by elusion
Front-paged by broquaint
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others imbibing at the Monastery: (6)
As of 2024-03-28 19:10 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found