in reply to Re^8: Specializing Functions with Currying
in thread Specializing Functions with Currying

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;

[download]

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

[download]

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.

Replies are listed 'Best First'.
Re^10: Specializing Functions with Currying
by tilly (Archbishop) on Aug 09, 2004 at 18:44 UTC
    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.

[reply]
Re^10: Specializing Functions with Currying
by Aristotle (Chancellor) on Aug 09, 2004 at 13:19 UTC

    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;

    [download]

    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 sort solution in functional style is a red herring — you can just as well write a sort solution in imperative style.

    Makeshifts last the longest.

[reply]
[d/l]
Re^10: Specializing Functions with Currying
by adrianh (Chancellor) on Aug 09, 2004 at 13:28 UTC
    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

[reply]
[d/l]
Re^10: Specializing Functions with Currying
by BrowserUk (Patriarch) on Aug 09, 2004 at 13:50 UTC

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

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

    [download]

    Versus:

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

    [download]

    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
    "Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon
[reply]
[d/l]
[select]

      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.

[reply]
        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

        [download]

        :-)

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

[reply]
[d/l]

        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)

        [download]
        Examine what is said, not who speaks.
        "Efficiency is intelligent laziness." -David Dunham
        "Think for yourself!" - Abigail
        "Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon
[reply]
[d/l]

In Section Meditations