Specializing Functions with Currying
FoxtrotUniform
created: 2004-08-05 20:42:37
perlmonks
prlmnks

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";
}

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 [id://165428|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";
}

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

Re: Specializing Functions with Currying
leriksen
created: 2004-08-05 22:53:01
perlmonks
prlmnks
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;

Re^2: Specializing Functions with Currying
Aristotle
created: 2004-08-05 23:12:34
perlmonks
prlmnks

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.

Re^3: Specializing Functions with Currying
FoxtrotUniform
created: 2004-08-05 23:23:54
perlmonks
prlmnks 
 '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

Re^4: Specializing Functions with Currying
Aristotle
created: 2004-08-06 00:38:14
perlmonks
prlmnks

I had seen that some primitive exists for this kind of thing in functional programming, but I have never gotten past a brief foray into that world. My first contact with a number of functional concepts was through Perl, and ever since I've meant to learn a serious functional language. It hasn't happened yet…

For anyone looking for an introduction to functional concepts in Perl, Mark-Jason Dominus' Higher Order Perl book is well worth a look… or will be once it's finished.

Makeshifts last the longest.

Re^4: Specializing Functions with Currying
stvn
created: 2004-08-06 09:46:32
perlmonks
prlmnks

Why limit compose to just two functions? 

sub compose {
    my ($f, $f2, @rest) = @_;
    return $f unless defined $f2;
    return &compose(sub { $f2->($f->(@_)) }, @rest);
}

*bold_italic_and_underlined_paragraph = compose(
    &curry(\&wrap_with_html, 'u'),
    &curry(\&wrap_with_html, 'b'),
    &curry(\&wrap_with_html, 'i'),
    &curry(\&wrap_with_html, 'p')
);

print bold_italic_and_underlined_paragraph("test");

-stvn
Re^5: Specializing Functions with Currying
jryan
created: 2004-08-06 17:03:43
perlmonks
prlmnks

Why recurse when you can iterate instead? :) 

use List::Util qw(reduce);
sub compose {
    reduce { sub { $b->($a->(@_)) } } @_;
}

Of course, that doesn't actually work because Perl's reduce uses global variables ($a,$b). But, we can roll our own: 

sub compose {
    my $c = shift;
    foreach my $s (@_) {
        my $o = $c;
        $c = sub { $s->($o->(@_)) }
    }
    $c
}
Re^6: Specializing Functions with Currying
stvn
created: 2004-08-06 17:56:37
perlmonks
prlmnks
Why recurse when you can iterate instead? :)

*gasp* .... thats not very functional! (I wont even bring up the fact you are using variable assignment, tssk tssk)

If we really want to be "efficient" about it, we would avoid the overhead of the wrapper subroutine, and just use straight perl's closures. 

sub compose {
    my (@funcs) = @_;
    return sub {
        my (@args) = @_;
        foreach my $func (@funcs) {
            @args = $func->(@args);
        }
        return @args;
    };
}
But really, that takes all the fun out of it ;-)

-stvn
Re^7: Specializing Functions with Currying
jryan
created: 2004-08-06 18:21:24
perlmonks
prlmnks

Why be functional when you can be efficient? Recursion might be elegant, but computers don't really understand elegance. :) Functional programming has a lot of great and useful concepts in it, and luckily we use a language that doesn't *force* us to be purists about it.

P.S.: The variable assignment is very necessary in my second example, because otherwise you're going to get a circularly referenced subroutine, which will make perl hit a infinite recursion warning pretty damned quick.

P.P.S: And, you're right, your last version is even better!

Re^8: Specializing Functions with Currying
tilly
created: 2004-08-06 18:29:05
perlmonks
prlmnks
Actually programming languages that understand tail-recursion would have made stvn's solution both elegant and efficient.

That said, some algorithms just cannot be efficiently implemented in a "pure" functional manner. A good example is the Sieve of Eratosthenes.

Re^9: Specializing Functions with Currying
hardburn
created: 2004-08-09 09:08:06
perlmonks
prlmnks

Something I've noticed in some of my own (brief) studies into functional programming is that it tends to make one think in algorithms that are not always the most efficient, and sometimes tail-recursion won't save you.

For instance, in a SoPW a while back, a poster wanted an efficient way to get the highest number in a list (or something along those lines). I posted this solution:

my $highest = pop sort { $a <=> $b } @list;

For some reason, my brain was convinced that this was the most efficient solution. While it may be a wonderful bit of functional code, it is not nearly as efficient as the iterative solution I knew quite well when I was a new C programmer:

my $highest = pop @list;
foreach (@list) {
	$highest = $_ if $_ > $highest;
}

Just what was I thinking?

I guess this is a warning not to rely on any one tool too much.

"There is no shame in being self-taught, only in not trying to learn in the first place." -- Atrus, Myst: The Book of D'ni.

Re^10: Specializing Functions with Currying
Aristotle
created: 2004-08-09 09:19:29
perlmonks
prlmnks

If you write bad functional code, that does not imply the of failure functional programming.

What were you thinking, indeed?

use List::Util qw(reduce);

my $highest = reduce { $a > $b ? $a : $b } @list;

Of course, in practice, you'd use the specialized max() function from the module — but the above is how you'd write this algorithm in any functional language.

The fact that you wrote the [perlfunc:sort|sort] solution in functional style is a red herring — you can just as well write a [perlfunc:sort|sort] solution in imperative style.

Makeshifts last the longest.

Re^10: Specializing Functions with Currying
adrianh
created: 2004-08-09 09:28:21
perlmonks
prlmnks
While it may be a wonderful bit of functional code, it is not nearly as efficient as the iterative solution

While it is functional, I wouldn't describe it as wonderful :-) A functional developer would use reduce to do it efficiently

Re^10: Specializing Functions with Currying
BrowserUk
created: 2004-08-09 09:50:04
perlmonks
prlmnks

I sometimes fall foul of that too. My most recent example was: 

my $first = first{ length > 3 } @array;
print $first;

Versus:

my $first;
for ( @array ) {
	next unless length > 3;
	$first = $_;
	last;
}
print $first;

where, despite the compiled-loop nature of List::Util::first, the latter was considerably more efficient than the former if the required value was close to the front of the array.

Nearly twice as efficient with an array of 100,000 items and the thing I was looking for about a 10th of the way in.

Funnily enough, even if the item I was looking for was the last item in the array, the iterative approach was still quickest. I guess the penalty of entering and exiting the block scope is the cause?

Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - [Abigail-II|Abigail]
"Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - [tachyon]
Re^11: Specializing Functions with Currying
Aristotle
created: 2004-08-09 10:12:41
perlmonks
prlmnks

first is pure-Perl and does not have short-circuiting behaviour.

Use the source, Luke. It's what it's there for. :-)

Makeshifts last the longest.

Re^12: Specializing Functions with Currying
adrianh
created: 2004-08-09 10:18:28
perlmonks
prlmnks
first is pure-Perl and does not have short-circuiting behaviour.

And if you look at the the source just before the pure perl reduce definition we find:

eval <<'ESQ' unless defined &reduce;

# This code is only compiled if the XS did not load

:-)

So the reduce() in question may, or may not, be pure perl.

Re^13: Specializing Functions with Currying
Aristotle
created: 2004-08-09 10:34:45
perlmonks
prlmnks

Oops.

Interesting, also, that the XS version does short-circuit. I looked at the source and thought I could see that, but I don't know XS so to be sure, I tested. And lo:

$ perl -MList::Util=first -le'@_=(0)x100; first { ++$a; $_ == 0 } @_; print $a'
1

Hmm.

Makeshifts last the longest.

Re^14: Specializing Functions with Currying
adrianh
created: 2004-08-09 12:19:03
perlmonks
prlmnks
Oops.

If it's any comfort I did exactly the same sort of thing once :-)

Re^12: Specializing Functions with Currying
BrowserUk
created: 2004-08-09 10:28:49
perlmonks
prlmnks

I did... :) 

P:\lib\auto\List\Util>strings Util.dll | grep Usage
Usage: List::Util::reduce(block, ...)
Usage: List::Util::first(block, ...) <<<<<<<<<<<<<<<<<<
Usage: Scalar::Util::dualvar(num, str)
Usage: Scalar::Util::blessed(sv)
Usage: Scalar::Util::reftype(sv)
Usage: Scalar::Util::refaddr(sv)
Usage: Scalar::Util::weaken(sv)
Usage: Scalar::Util::isweak(sv)
Usage: Scalar::Util::readonly(sv)
Usage: Scalar::Util::tainted(sv)
Usage: Scalar::Util::isvstring(sv)
Usage: Scalar::Util::looks_like_number(sv)
Usage: Scalar::Util::set_prototype(subref, proto)
Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - [Abigail-II|Abigail]
"Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - [tachyon]
Re^13: Specializing Functions with Currying
Aristotle
created: 2004-08-09 10:39:34
perlmonks
prlmnks

Weird.

use Benchmark qw(cmpthese);
use List::Util qw(first);

@_= ( (0)x1000, 1, (0)x8999 );

cmpthese -1, {
    func => sub { first { $_ == 1 } @_ },
    imper => sub { for ( @_ ) { next unless $_ == 1; return $_ } },
}
__END__
          Rate imper  func
imper 518950/s    --  -20%
func  649177/s   25%    --

Makeshifts last the longest.

Re^14: Specializing Functions with Currying
BrowserUk
created: 2004-08-09 11:07:12
perlmonks
prlmnks

This is closer to what I was doing 

#! perl -slw
use strict;
use Benchmark qw[ cmpthese ];
use List::Util qw[ first ];

our @array = 1 .. 100_000;

cmpthese( -1, {
	func_10th => q[ 
		my $first = first{ length > 3 } @array;
#		print "F:$first";
	],
	iter_10th => q[
		my $first;
		for ( @array ) {
			next unless length > 3;
			$first = $_;
			last;
		}
#		print "I:$first";
	],
	func_last => q[ 
		my $first = first{ length > 5 } @array;
#		print "F:$first";
	],
	iter_last => q[
		my $first;
		for ( @array ) {
			next unless length > 5;
			$first = $_;
			last;
		}
#		print "I:$first";
	],
});
__END__
P:\test>381208
            Rate func_last iter_last func_10th iter_10th
func_last 22.0/s        --      -16%      -98%      -99%
iter_last 26.1/s       18%        --      -98%      -99%
func_10th 1196/s     5336%     4488%        --      -56%
iter_10th 2706/s    12201%    10282%      126%        --
Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - [Abigail-II|Abigail]
"Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - [tachyon]
Re^15: Specializing Functions with Currying
Aristotle
created: 2004-08-09 11:50:35
perlmonks
prlmnks

I prefer not to compare apples and oranges:

use Benchmark qw[ cmpthese ];
use List::Util qw[ first ];

our @array = 1 .. 100_000;

cmpthese( -1, {
    func_10th => sub {
        first { length > 3 } @array;
    },
    iter_10th => sub {
        for ( @array ) {
			return $_ if length > 3;
        }
    },
});

cmpthese( -1, {
    func_last => sub {
        first { length > 5 } @array;
    },
    iter_last => sub {
        for ( @array ) {
			return $_ if length > 5;
        }
    },
});
__END__
            Rate func_10th iter_10th
func_10th  718/s        --      -77%
iter_10th 3139/s      337%        --
            Rate iter_last func_last
iter_last 29.4/s        --      -29%
func_last 41.1/s       40%        --

The results are similar if I run your code though.

Over here, first always wins given a sufficiently large number of iterations.

Makeshifts last the longest.

Re^16: Specializing Functions with Currying
BrowserUk
created: 2004-08-09 12:10:21
perlmonks
prlmnks

Strange. Taking your exact code from above and runnning here I get: 

P:\test>type 381208-2.pl
#! perl -slw
#use strict;

use Benchmark qw[ cmpthese ];
use List::Util qw[ first ];

our @array = 1 .. 100_000;

cmpthese( -1, {
    func_10th => sub {
        first { length > 3 } @array;
    },
    iter_10th => sub {
        for ( @array ) {
            return $_ if length > 3;
        }
    },
});

cmpthese( -1, {
    func_last => sub {
        $_ = first { length > 5 } @array;
    },
    iter_last => sub {
        for ( @array ) {
            return $_ if length > 5;
        }
    },
});

P:\test>381208-2
            Rate func_10th iter_10th
func_10th 1196/s        --      -61%
iter_10th 3076/s      157%        --
            Rate func_last iter_last
func_last 22.6/s        --      -23%
iter_last 29.3/s       30%        --

Which indicates something about the difference in OS, but I'm not sure what.

I also wonder what context Benchmark calls the subs in? And is first optimised for the void context case?

Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - [Abigail-II|Abigail]
"Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - [tachyon]
Re^17: Specializing Functions with Currying
Aristotle
created: 2004-08-09 12:27:55
perlmonks
prlmnks

Or differences in compilers and flags used to build the versions.

$ perl -v | grep ^This
This is perl, v5.8.3 built for i486-linux
$ perl -V:gccversion
gccversion='3.3.2';
$ perl -V:config_args
config_args='-de -Dprefix=/usr -Dcccdlflags=-fPIC -Dinstallprefix=/usr -Doptimize=-O3 -march=i486 -mcpu=i686 -Darchname=i486-linux';

The relevant bits for call context are in the runloop() function:

    # ...
    if (ref $c eq 'CODE') {
	$subcode = "sub { for (1 .. $n) { local \$_; package $pack; &\$c; } }";
        $subref  = eval $subcode;
    }
    else {
	$subcode = "sub { for (1 .. $n) { local \$_; package $pack; $c;} }";
        $subref  = _doeval($subcode);
    }
    # ...
    &$subref;

(_doeval is basically a [perlfunc:eval|eval].)

So void context, but I don't think that matters here — the compiler doesn't know the context at the time of [perlfunc:eval|eval], so shouldn't be optimizing things away. One would have to instrument the code with a few [cpan://B::Deparse] calls to know for sure, of course. But going by the numbers from the benchmark, it doesn't seem to be making the difference.

There just seems to be a high startup overhead for first that amortizes over time, given enough time, for at least some Perls.

Makeshifts last the longest.

Re^10: Specializing Functions with Currying
tilly
created: 2004-08-09 14:44:05
perlmonks
prlmnks
Oh, that solution can be quite efficient. You just have to generalize the problem in the right way. :-)

An example where the moral equivalent of your approach is efficient is if you want the top m elements out of a set of n. Make the sort be a lazy sort (eg heapsort) so that you only do the necessary comparisons. The efficiency is then O(n+m*log(n)), which is about as good as you will get.

Re^8: Specializing Functions with Currying
stvn
created: 2004-08-06 19:04:25
perlmonks
prlmnks
Why be functional when you can be efficient

Spoken like a true Electrical Engineering Major ;-)

Functional programming has a lot of great and useful concepts in it, and luckily we use a language that doesn't *force* us to be purists about it.

I agree with you on both points. However, as tilly points out, recursion (and other functional programming goodies) don't have to be inefficient. I would encourage you to check out Standard ML, and in particular its compilation model (which I can't find any good links to at the moment, but I will post them when I find them). ML is a fast functional language, and according to the (inherently flawed) computer language shootout one of the fastest (faster than C++ in some cases). In addition there are some really fast LISP implementations out there too as well.

Basically with a good compiler, you can be functional and efficient.

-stvn
Re^9: Specializing Functions with Currying
jryan
created: 2004-08-06 19:20:36
perlmonks
prlmnks

Hey, don't take me wrong, I'm all about elegance. My argument isn't against functional langauges (hell, I used reduce, which is the same thing in lisp! lisp, baby! how's that for functional!), it was that recursion in Perl is crazy inefficient, and to use it just because its "functional" is kind of silly. :) Tilly's point was about tail-recursion, which is an optimization that Perl doesn't support (for some reason, I honesetly don't have a clue why).

Re^10: Specializing Functions with Currying
stvn
created: 2004-08-06 19:37:28
perlmonks
prlmnks
... it was that recursion in Perl is crazy inefficient, ...

Is it really? I mean, its certainly not as efficient as the equivalent iterative code. And I know that subroutine calls have a non-trivial overhead (setting up lexical scope and all), but being that perl does not tie itself to the C-stack like some other langauges do (*cough* Python *cough*) I would think that it wouldn't really be all that inefficient. Of course, I have never benchmarked it, so who knows.

... and to use it just because its "functional" is kind of silly ...

But if we can't get silly with Perl at 7 o'clock (EST) on a Friday night, then what kind of world is this! ;-P

about tail-recursion, which is an optimization that Perl doesn't support (for some reason, I honesetly don't have a clue why)

I don't know why either, I once looked into trying to "implement" it with the B:: modules. But once was all it took for me to to decide that wouldn't work.

-stvn
Re^11: Specializing Functions with Currying
jryan
created: 2004-08-06 20:08:10
perlmonks
prlmnks

Well, here's a benchmark. The first two are just normal factorial functions. The second two are factorial functions with a twist: a simple string gets created. Now, this string has to be created and saved on *every* recursive call, which should show the discrepancy a little more (as saving one little integer to the stack doesn't make much difference): 

use strict;
use warnings 'all';

sub factorial_r {
    my ($n) = @_;
    
    return $n if ($n < 2);
    return $n * factorial_r($n-1);
}

sub factorial_i {
    my ($n) = @_;
    
    my $i = $n - 1;
    $n *= ($n - $i--) while $i > 1;
    return $n;
}

sub factorial_r_extra {
    my ($n) = @_;
    my $x = "blah" x 100;
    return $n if ($n < 2);
    return $n * factorial_r_extra($n-1);
}

sub factorial_i_extra {
    my ($n) = @_;
    my $x = "blah" x 100;
    my $i = $n - 1;
    $n *= ($n - $i--) while $i > 1;
    return $n;
}

use Benchmark qw(timethese);
timethese(100000, {
    first  => sub { factorial_r(50) },
    second => sub { factorial_i(50) },
});

The results: 

Benchmark: timing 100000 iterations of factorial_i, factorial_i_extra, factorial_r, factorial_r_extra...
factorial_i:  5 wallclock secs ( 4.94 usr +  0.00 sys =  4.94 CPU) @ 20251.11/s (n=100000)
factorial_i_extra:  6 wallclock secs ( 5.67 usr +  0.00 sys =  5.67 CPU) @ 17633.57/s (n=100000)
factorial_r:  6 wallclock secs ( 6.44 usr +  0.01 sys =  6.45 CPU) @ 15496.67/s (n=100000)
factorial_r_extra: 13 wallclock secs (11.98 usr +  0.00 sys = 11.98 CPU) @ 8344.46/s (n=100000)

P.S. : I'm still young and armed with a job with flextime - I don't wake up until about 1pm, so this is like early afternoon for me. :)

Re^12: Specializing Functions with Currying
stvn
created: 2004-08-06 20:25:01
perlmonks
prlmnks

I am not sure what you are trying to prove with this benchmark. Of course factorial_r_extra will take longer, it creates my $x = "blah" x 100 5,000,000 times, as opposed to factorial_i_extra which only creates it 100,000 times. That proves nothing about the inefficiency of recursion in perl, only that it takes longer to do something 50 times more, which is true regardless of whether you use iteration or recursion.

-stvn
Re^13: Specializing Functions with Currying
itub
created: 2004-08-06 22:35:41
perlmonks
prlmnks
How fitting that a discussion about recursion gets to over 12 levels of depth! ;-)

I must say that I'm surprised that the difference between recursion and iteration is as small as it is in this case. The problem I have had in some cases, though, is that perl starts to complain about deep recursion when I try recursive algorithms that go just one or two thousand levels down...

Re^14: Specializing Functions with Currying
stvn
created: 2004-08-06 23:11:34
perlmonks
prlmnks
How fitting that a discussion about recursion gets to over 12 levels of depth! ;-)

I will see your 13, and take it one more level down ;- )

The problem I have had in some cases, though, is that perl starts to complain about deep recursion when I try recursive algorithms that go just one or two thousand levels down...

FWIK, Perl's deep recursion error is a somewhat arbitrary number (I think its actually set to 1000), and has no real bearing on perl's ability to keep recursing (which is only limited to the physical resources (memory/CPU/disk-swap) available for it to consume). And I believe that someone once told me you can easily change that number and recomplile perl if you need more.

-stvn
Re^15: Specializing Functions with Currying
diotalevi
created: 2004-08-06 23:23:27
perlmonks
prlmnks
It is 100. grep for sub_crush_depth.
Re^10: Specializing Functions with Currying
tilly
created: 2004-08-06 19:39:29
perlmonks
prlmnks
Tail recursion has a seldom-noted cost. Sure, it speeds up some recursive code. But it also means that if you get into trouble, a stack backtrace will be missing a lot of potentially useful context.

That said, you can manually do tail-recursion in Perl with goto. Unfortunately it is not as efficient as it should be, and I'm not entirely sure why.

Re^11: Specializing Functions with Currying
stvn
created: 2004-08-06 20:06:08
perlmonks
prlmnks
That said, you can manually do tail-recursion in Perl with goto. Unfortunately it is not as efficient as it should be, and I'm not entirely sure why.

I think that it basically comes down to the fact that goto is just not all that efficient, and the amount of bookkeeping code needed to do that (for non-trivial implementations) outweighed the benefits.

-stvn
Re^7: Specializing Functions with Currying
ihb
created: 2004-08-07 20:19:40
perlmonks
prlmnks

For full equivalence you need to not spoil the aliasing of @_ for the first call. Replace all @args with @_ and you're home safe. (The @_ assignment later breaks the aliasing as it should.)

Cheers,
ihb

Read argumentation in its context!

Re^5: Specializing Functions with Currying
NodeReaper
created: 2004-08-06 18:54:36
perlmonks
prlmnks
This node was taken out by the NodeReaper on Fri Aug 6 19:21:15 2004 (EST)
Reason: jryan Duplicate of 380784, Delete

For more information on this node visit: this

Re^5: Specializing Functions with Currying
Aristotle
created: 2004-08-06 18:55:53
perlmonks
prlmnks

Of course, that's just asking for it.

my $biup = compose map curry( \&wrap_with_html, $_ ), qw( p u i b );

Now that actually looks like a construct you're likely to see in some flavour of functional programming language.

Makeshifts last the longest.

Re^3: Specializing Functions with Currying
thor
created: 2004-08-09 11:03:39
perlmonks
prlmnks
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>




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^4: Specializing Functions with Currying
                
    


    

        Aristotle
    


    


    

        created: 2004-08-09 11:38:18
    


    


        

            perlmonks
            
                    
        
   


        

            
            
                    
        
   

        

            prlmnks
    
                    
        
   

    

    


    


        
Err, yes, but that wasn't the point. It's a funny hack, but a hack. :-) It doesn't apply to the general case where one wants to compose functions.





Makeshifts last the longest.

















    

        
        Re^4: Specializing Functions with Currying
                
    


    

        miro
    


    


    

        created: 2004-08-10 03:05:06
    


    


        

            perlmonks
            
                    
        
   


        

            
            
                    
        
   

        

            prlmnks
    
                    
        
   

    

    


    


        The closing tag would be incorrect if you just add a slash before the string.









    

        
        Re^5: Specializing Functions with Currying
                
    


    

        thor
    


    


    

        created: 2004-08-10 07:54:14
    


    


        

            perlmonks
            
                    
        
   


        

            
            
                    
        
   

        

            prlmnks
    
                    
        
   

    

    


    


        You're absolutely correct.



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
diotalevi
created: 2004-08-06 00:38:02
perlmonks
prlmnks

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';
Re^2: Specializing Functions with Currying
zby
created: 2004-08-06 03:45:22
perlmonks
prlmnks
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'.
Re^3: Specializing Functions with Currying
diotalevi
created: 2004-08-06 11:25:47
perlmonks
prlmnks

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.

Re^4: Specializing Functions with Currying
jryan
created: 2004-08-06 16:10:55
perlmonks
prlmnks

"Currying" does not mean "using an anonymous function", it means "partial application of function arguments." It's kind of like saying "I know that I'm going to call this function with these first few arguments, so let me half-call it now so that I don't have to worry about them later." Perl's OO system sort of has transparent currying aspect to it. Each method call is just a function call automatically curried with one argument (the object that the method was called upon) and then called. For a more concrete application of currying, you could check out this old node by mirod.

Re^5: Specializing Functions with Currying
diotalevi
created: 2004-08-06 16:45:56
perlmonks
prlmnks

Yes... I see that and still keep thinking "boy, this is pretty normal perl stuff". find( sub { wanted( @my_args, @_ ) }, ... ) is already easy to use and I don't see the utility in going out of the way to inject extra obfuscatory language just to describe it.

Re^6: Specializing Functions with Currying
adrianh
created: 2004-08-06 16:54:25
perlmonks
prlmnks
I don't see the utility in going out of the way to inject extra obfuscatory language just to describe it

It's only obfuscatory if you don't know what the terms mean :-) If you do then the utility is more information on the intent.

If somebody refers to a curried function then I know that they're going to be taking a function and specialising it by freezing one of its arguments. This tells me more than if they had referred to it as a closure.

Re^6: Specializing Functions with Currying
tilly
created: 2004-08-06 17:04:55
perlmonks
prlmnks
You're right that coming up with language to describe what you want often doesn't pay back when you are limited to a single tool that works how it works.

But it pays back in spades when you are considering what you can do with different sets of tools. And it is indispensable when you're trying to design a tool.

In Perl 5 it practically isn't worth the bother to think, "Oh, I could do this with currying" - you just do it with a closure and avoid the extra step. But if you know how to think about what you're doing as currying, then when you use a language with good support for currying, you will have some notions on when to reach for that rather than writing it in Perl 5. Alternately if you are working in a language that without support for closures, but you understand that all you really want is currying, then you can figure out ways to simulate the simpler concept rather than trying to do full-blown closures.

Furthermore when it comes to designing tools, well have you read Perl 6 : Not Just For Damians? Take a look at the example of currying offered there. If Larry and Damian et al did not have language to discuss the idea of currying, would they ever have thought up such a nice way to do it?

So yes, learning about currying is completely useless to you in day to day Perl 5 programming. But concluding that it is therefore a useless concept is a fast way to fall into the "Blub Paradox". See Beating The Averages if you don't know what that is.

Re^7: Specializing Functions with Currying
diotalevi
created: 2004-08-06 17:33:51
perlmonks
prlmnks

This is to both you and adrianh.

I have apparently misinterpreted this as thoughts on perl5 practice and constrained myself to that universe. Implicltly, I've thought that if I were in some other language where currying was standard I'd think along those lines. In this language (perl5), I don't and so I didn't and I objected with my initial request for a terminology change.

I do however, take to heart your bringing up that issue of language power and the perspective limiting aspect of being proficient in a language. In fact, I've often read all these functions returning other functions composed of other functions, wrapping other functions and felt really quite swimmy. Very lost. Suddenly I'm reminded of E and their Promises and the "So when does something *happen*?" and it makes more sense.

Thanks. This was useful to me. I just gained a new way to think about this stuff.

Re^2: Specializing Functions with Currying
tilly
created: 2004-08-06 14:44:55
perlmonks
prlmnks
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.)

Re^2: Specializing Functions with Currying
FoxtrotUniform
created: 2004-08-06 18:18:37
perlmonks
prlmnks

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
kabel
created: 2004-08-06 01:48:31
perlmonks
prlmnks
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")->();
Re: Specializing Functions with Currying
stvn
created: 2004-08-06 10:17:48
perlmonks
prlmnks

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 [http://www.functionalobjects.com/resources/index.phtml|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 [http://en.wikipedia.org/wiki/Combinatory_logic#Combinatory_calculi|combinators].

-stvn
Re: Specializing Functions with Currying
stvn
created: 2004-08-06 12:30:08
perlmonks
prlmnks
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
Double-curried goodness
tmoertel
created: 2004-08-06 17:46:16
perlmonks
prlmnks
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'),
);

perlmonks.org content © perlmonks.org and adrianh, Aristotle, BrowserUk, diotalevi, FoxtrotUniform, hardburn, ihb, itub, jryan, kabel, leriksen, miro, NodeReaper, stvn, thor, tilly, tmoertel, zby

prlmnks.org © 2006 edmund von der burg (eccles & toad)

v 0.03