in reply to Finding the max()/min()
What I really like is writing generic min/max routines that handle more than two variables. They show the beauty of recursive functions, even though Perl doesn't handle tailrecursion^{1}.
Iterative:
sub max {
my ($max, @vars) = @_;
for (@vars) {
$max = $_ if $_ > $max;
}
return $max;
}
Recursive:
sub max {
my ($max, $next, @vars) = @_;
return $max if not $next;
return max( $max > $next ? $max : $next, @vars );
}
Interestingly enough, though this example works well in several languages, Perl's iterative version is remarkably short; I've never noticed this before. I guess I just proved myself wrong.
^{1}Okay, so this isn't strictly true. Using a magic goto with the & sigil and @_, you can fake it. But it's not very pretty.
Update: Fixed my mistake. Thanks, pg. (I always want to use postmodifier if and for in the same statement.)
Update: Okay, so I should test my code before I post. Or find where I left my brain. Snippet 2 is fixed.
Re^2: Finding the max()/min() by itub (Priest) on Nov 11, 2004 at 04:32 UTC 
Perhaps this will count as "cheating" for the purpose of this thread, but I just do this to find the min/max of a list
use List::Util qw(min max);
$min = min @list;
$max = max @list;
;)  [reply] [d/l] 

$min = reduce { ($a,$b)[$a < $b] } @list;
$min_key = reduce { ($a,$b)[$x{$a} < $x{$b}] } keys %x;
Working out max is left as an exercise :)
 [reply] [d/l] 
Re^2: Finding the max()/min() (stmt modifier form) by demerphq (Chancellor) on Nov 11, 2004 at 10:47 UTC 
sub max {
my $max=shift;
$max < $_ and $max = $_
for @vars;
return $max;
}
Is marginally shorted and probably faster, but commits what some would call the crime of logic based control flow.
 [reply] [d/l] 
Re^2: Finding the max()/min() by pg (Canon) on Nov 11, 2004 at 02:52 UTC 
Update:
Per elusion's update, he has already fixed both solutions.
============
Your solution one does not compile.
Your solution two does not work, and it does not print anything:
use strict;
use warnings;
print max(1.23,2.6,55.1,4,5);
sub max {
my ($max, $next, @vars) = @_;
return if not $next;
return max( $max > $next ? $max : $next, @vars );
}
 [reply] [d/l] 
Re^2: Finding the max()/min() by sleepingsquirrel (Hermit) on Nov 11, 2004 at 19:47 UTC 
Your recursive version of max is broken for lists like (1,0,1,2) and (1,undef,1,2). i.e. the code assumes it is at the end of the list whenever $next==0 or $next==undef (which isn't true in general).
Here's a snazzy (if not the most efficient) recursive version with a hat tip to Zaxo...
sub max {
my ($x, @xs) = @_;
@xs ? ($x, max(@xs))[$x < max(@xs)] : $x
}
 All code is 100% tested and functional unless otherwise noted.
 [reply] [d/l] 

Your solution is calling max(@xs) twice each step. This leads to O(2^n) growth for what should be an O(n) problem. Modifying it slightly to call max once and save the value in a temp variable should save considerable time on long lists.
sub max {
my ($x, @xs) = @_;
@xs ? do { my $m = maxdo(@xs); ($x, $m)[$x < $m] } : $x;
}
 [reply] [d/l] [select] 
Re^2: Finding the max()/min() by Aristotle (Chancellor) on Dec 18, 2004 at 02:15 UTC 
sub max {
my( $i, @l ) = @_;
my $j = @l ? max( @l ) : $i;
return $i > $j ? $i : $j;
}
And for that matter, an iterative form:
sub max {
$_[ 0 ] < $_[ 1 ] ? shift : pop while @_ > 1;
return @_;
}
Makeshifts last the longest.
 [reply] [d/l] [select] 

It's normally best to end recursive solutions with the recursive call. That allows the compiler to use tailrecursion to speed up the solution.
Of course, in Perl you need to jump through a few hoops to do use tailrecursion, so I mentioned but didn't include it in my original node. But with a bit if tinkering you can use it, and here it is now:
sub max {
my $max = shift;
my $next = shift;
return $max if not $next;
unshift @_, $max > $next ? $max : $next;
goto &max;
}
Which I estimate to be about 10x faster on a random 5000 element list. (Exact benchmarks are left to the reader as an exercise :).
I wonder if Ponie (Perl 5 On New Internals Engine) will be able to detect and use tailrecursion.
 [reply] [d/l] 

There's a bug in that code, try finding the max of this list...
@a = (1,0,3,2);
 All code is 100% tested and functional unless otherwise noted.
 [reply] [d/l] 


That's all well and nice, but my goal was to use an approach which directly generalizes from the specific case of a two element list. As you'll also notice I used the value returned from the recursive call twice, it's both kind of difficult and beside the point to work on tail recursion here. Noone in their right mind writes a recursive max() outside a functional language anyway, and in a pure functional language I'd just write max( @l ) twice and let the compiler/VM figure out that the result need only be calculated once.
In any case, your new approach is just a variation on what was already posted in the parent node — no need for repetition…
Makeshifts last the longest.
 [reply] [d/l] 

