|
macrobat has asked for the wisdom of the Perl Monks concerning the following question:
Hi folks,
One of the techniques often mentioned in functional programming circles is function currying, or taking a function with (N) parameters and returning another function that takes (N-M) parameters. The process is straightforward enough: you use a closure to return a function, like so:
sub add_to {
my $arg1 = $_[0];
return sub { add($arg1, $_[0]) };
}
my $plus_5 = add_to(5);
my $x = $plus_5->(3); # $x == 8
My problem is this: examples like the one above are the only ones I'm able to find, and I may be missing something, but it looks like I've spent 100 keystrokes or so to say "$x = 8". Woo hoo!
My question is this: function currying really looks useful, but in ways that I haven't yet worked out; can the esteemed monks share examples (ideas or full-blown code) that demonstrates when and where currying is a useful technique (and maybe where it isn't)? |
Re: Currying--useful examples?
by gaal (Parson) on Jan 10, 2007 at 20:37 UTC
|
Here's the example I usually give in talks etc.. Say you have an HTML editor that has bold, underline and italics. Instead of writing three functions, have the compiler write them for you:
sub mk_tagger {
my($tag) = @_;
return sub { my($txt) = @_; "<$tag>$txt</$tag>" };
}
my ($bold, $underline, $italic) = map { mk_tagger($_) } qw( b u i );
print $bold->("what a " . $underline->("nice") . $italic->(" day"));
Here's the equivalent Perl 6:
sub mk_tagger ($tag) {
-> { "<$tag>$^txt</$tag>" }
}
The idea is that the mk_taggger function is intentionally designed not to be used directly but to generate tagging functions.
Update: In Haskell and other languages that had autocurrying, you'd not need this explicit distinction.
tagStr :: String -> String -> String
tagStr tag text = "<" ++ tag ++ ">" ++ text ++ "</" ++ tag ++ ">"
-- now I can use it either way.
tagStr "b" "a bold moose"
underline = tagStr "u"
underline "an underlined moose"
| [reply]
[d/l]
[select] |
|
|
Of course, to say "<" ++ tag ++ ">" is very ugly, so you'd want to write it as angle tag. angle is a function? How is it implemented? In typical function programming style:
angle :: String -> String
angle s = surround "<" ">" s
{- This can, in "points free" style, be written:
angle = surround "<" ">" -- look ma, no explicit variable!
-}
surround :: String -> String -> String -> String
surround start end text = start ++ text ++ end
-- The idea is to reuse surround:
quote = surround "'" "'"
bracket = surround "[" "]"
braces = surround "{" "}"
... etc.
But this is straying off-topic for this site... | [reply]
[d/l]
[select] |
Re: Currying--useful examples?
by chargrill (Parson) on Jan 10, 2007 at 19:38 UTC
|
This node as well as some of the replies might have some more useful examples/applications.
Also, there's a fairly useful module on CPAN that makes use of what at first glance I thought was currying - check out File::Next by our very own petdance.
Updated: added bold text. I was just so excited by hearing about petdance's module.
--chargrill
s**lil*; $*=join'',sort split q**; s;.*;grr; &&s+(.(.)).+$2$1+; $; =
qq-$_-;s,.*,ahc,;$,.=chop for split q,,,reverse;print for($,,$;,$*,$/)
| [reply]
[d/l] |
|
|
| [reply] |
|
|
By the way, what does "our very own petdance" mean? "Our" seems to imply membership in a group. I'm concerned what group that would be. :-)
| [reply] |
|
|
I suppose it's possible (even likely?) for there to be clever modules on CPAN by authors who don't frequent PerlMonks, so the group I'm including you in is "those who frequent PerlMonks". :-)
I could also possibly be grouping you into Chicago Perl Mongers, but as the audience reading PerlMonks is far greater larger than the Chicago Perl Mongers group, that wouldn't be very clear from the context of the post.
:-)
Updated: True, we have some excellent folk in Chicago Perl Mongers and I wouldn't want them to feel slighted by my careless choice of words. ;)
--chargrill
s**lil*; $*=join'',sort split q**; s;.*;grr; &&s+(.(.)).+$2$1+; $; =
qq-$_-;s,.*,ahc,;$,.=chop for split q,,,reverse;print for($,,$;,$*,$/)
| [reply]
[d/l] |
|
|
Re: Currying--useful examples?
by blokhead (Monsignor) on Jan 10, 2007 at 20:16 UTC
|
You can interpret the standard way of "making a reference to a method call" as a form of currying:
my $coderef = sub { $obj->method(@_) };
There's no other way to do it, and it's pretty useful in OO programming when an interface is looking for a callback. In general, when you have to pass in a callback to some interface, you can use currying when the calling interfaces don't quite match up (the callback will be called with certain arguments, but the subroutine you have expects more/less/different arguments).
Sorry that this example is still pretty abstract.. ;)
| [reply]
[d/l] |
|
|
| [reply]
[d/l] |
Re: Currying--useful examples?
by stvn (Monsignor) on Jan 11, 2007 at 01:40 UTC
|
Currying in a functional language (as others have pointed out above) is automatic within the language. This is because in most functional languages, a function is only allowed to accept one argument. Syntactic sugar under the hood will convert a multi-parameter function like this (using pseudo-functional-perl):
sub foo $x $y { $x * $y }
into something like this:
sub foo $x { sub $y { $x * $y } }
and then function application like this:
foo(3, 5)
into this:
foo(3)(5)
This is even more obvious in the type signatures of functions in languages like OCaml or Haskell. For instance, the above foo function would have the type signature in OCaml:
val foo :: int -> int -> int
Which basically can be read as "a function which takes an int, which returns a function, which also takes an int, which then returns an int".
So, to answer your question more directly, using currying in a language like Perl has (at best) only obscure usages. But in a functional language like Standard ML, OCaml or Haskell it is a fundemental part of how the language actually works.
| [reply]
[d/l]
[select] |
|
|
foo(3)(5)
Is even more clearly written as
(foo 3) 5
| [reply]
[d/l]
[select] |
Re: Currying--useful examples?
by Errto (Vicar) on Jan 11, 2007 at 00:56 UTC
|
Another typical example involves higher-level functions like map. If map in Perl were curried then I could say something like:
# contrived
my $incAll = map { $_++ };
my @data = return_some_numbers();
my @data2 = return_some_other_numbers();
$incAll->(@data);
$incAll->(@data2);
and now I would have both of my arrays incremented by 1 across all their elements. Better yet, I could combine it with closures to create incrementors by an arbitrary value:
sub makeIncr {
my $incr = $_[0];
return map { $_ += $incr };
}
In my own experience, I use currying and partial invokation extensively in Haskell which has native syntactic support for them, but so far I have not really come across them in my own Perl work. | [reply]
[d/l]
[select] |
|
|
It's really quite simple to write a curry-able map in Perl. I'd expect it to be pretty slow, though, because of the many subroutine calls: 2+n for a list of n elements. If "map CODE, LIST" treats CODE as a subroutine, that makes 2+2*n calls.
And $_++ won't work.
use strict;
use warnings;
sub cmap (&) {
my $map = shift;
return sub { map $map->($_), @_ };
}
my $incr = cmap {$_*2};
print join " ", $incr->(2..5);
print "\n";
# 4 6 8 10
Steffen | [reply]
[d/l] |
Re: Currying--useful examples?
by ambrus (Abbot) on Jan 11, 2007 at 13:12 UTC
|
I think the most important application of currying is those languages in which functions can take only a few arguments. Belive it or not, there are lots of such programming languages. It all started with mathematical constructs.
The lambda calculus is a very simple model of computation where every object is a function with exactly one argument and one return value – so the argument and the return value are functions like this as well. It has very few building blocks and still do any calculation. Furthermore, there are variants of this which do not use lambda expressions or variables and as such can be seen simpler: the SKI calculus (which is the base of the Unlambda obfuscated programming language), and the more practical FP.
(Btw, these models are also side-effectless becuase mathematicians always had an affection for that, but that's not really important in this story.)
In such languages, it is still possible to simulate functions with arbitarily many arguments in two ways: one is currying, and the other is that you call a function with a single aggreate object (tuple, record, list or whatever you have in the language) containing all the arguments to the function.
However, the idea of limiting functions to only a few arguments was used in the Real World as well. Functional programming languages in the large family1 of ML (Standard ML, Caml, Haskell) have functions that accept only one argument. These languages support both currying and passing tuples by giving easy syntax to calling a curried function, creating tuples, defining a curried function, and defining a function that deconstructs a tuple argument. Indeed, function calling in these languages is denoted by juxtaposition and associates to the direction for calling a curried function, so you can just write f x y instead of f(x)(y), and function definitions can be curried rightaway so you can say fn x y => z instead of fn x => fn y => z etc. (Standard ML still seems to be supporting tuples more than currying because datatype constructor can not be curried.)
The J programming language is a bit different. In it, functions can have only one or two arguments. This makes it much easyer to define functions without explicitly naming the arguments (this is apparently practiced by haskell progammers as well, and is called pointfree style). On the other hand, even though J also has explicit function definitions, and some syntax ease about curried functions, it doesn't give as much helper syntax for multivariate functions as the ML languages do.
Not relevant here are those languages that limit the number of arguments to functions for some technical reason only, not by principle, and typically not as low as above. For example, the DOS shell allows access to only nine command-line arguments (the rest can still be accessed with the shift command); regular expressions in sed and joe have capturing parenthesis but you can only refer to the first 9 or 10 captures resp; some low-level cpu calling conventions limit how many arguments you can pass to a system call or such wierd functions.
1 Take care. As this is a rather large family, rather like the family of lisp-like languages, so some of its members might be offended if you count them in.
Update: link to the J programming language.
| [reply]
[d/l]
[select] |
Re: Currying--useful examples?
by exussum0 (Vicar) on Jan 10, 2007 at 22:56 UTC
|
In all honesty, this is probably most useful for things like, self evaluating trees. Based on some input of events, create a tree of how things should evaluate and execute upon that.
Imagine creating a flow chart, and you wish to see how it evaluates later on in a test scenario. Heck, it's implementable deterministic finite automata. If you somehow put a step function to control in there and have enough memory, you could do some non-deterministic finite automata.
By and large, from an everyday, custom, programming life, I agree there's no easy usage, but for people who make software engines, this is probably more useful. | [reply] |
Re: Currying--useful examples?
by jbert (Priest) on Jan 11, 2007 at 11:25 UTC
|
I'm not a huge user of it, but I think you can look at currying a multi-arg function as quite similar to constructing an object from a factory.
In both cases, you don't need to do it. Instead of creating the object, you could pass around all the parameters needed to construct the object everywhere you'd pass the object instead.
Both approaches "bundle" a bunch of information into a single context which can operate on things and be handily passed around.
Another way of looking at is both approaches allow you to make a specific tool (tailored object from factory or curried function) from a general one (factory or multi-arg function).
It's also very useful in 'map' or 'filter' (i.e. grep in perl), like situations, where you want a single-arg function to run the map or filter. e.g.
sub mk_less_than_filter {
my $limit = shift;
return sub { my $elt = shift; return $elt < $limit; };
}
sub find_less_than {
my $limit = shift;
my $vals = shift;
my $filter = mk_less_than_filter($limit);
return grep {$filter->($_)} @$vals;
}
print join(", ", find_less_than(4, [1, 2, 7, 10, 3, 8])), "\n";
# Prints 1, 2, 3
It's still a bit contrived, but I hope you can see the idea. In a more functional language 'grep' is written as 'filter' and would generally take a one-arg function as it's first argument.
| [reply]
[d/l] |
Re: Currying--useful examples?
by bsb (Priest) on Jan 12, 2007 at 06:22 UTC
|
| [reply] |
Re: Currying--useful examples?
by andye (Curate) on Jan 11, 2007 at 12:23 UTC
|
Is that really called currying?
That's fantastic! I have no idea why I find this funny, but I do... seems to suggest a whole line of cpan module names, 'use Curry::Tikka::Masala' and so on... ;)
best, a.
| [reply] |
|
|
It's named after Haskell Curry, the logician.
| [reply] |
|
|
Ah. Thank you. I still think it sounds funny, though. :)
| [reply] |
|
|
