Haskell-style list folding

Haskell (and many other functional languages, I'm sure) features a number of fold functions, which accumulate list values into a scalar using a given operation. I find folds to be really handy. Here, then, are Perl implementations of Haskell's foldl, foldl1, foldr, and foldr1 functions (see The Haskell 98 Language Report for more on Haskell and its folds).

This isn't exactly elegant, robust, or thoroughly-tested code, but what the hell, it might be handy....

#! /usr/bin/perl -w

use strict;
use Test;

sub foldl {
    my ($fn, $base, @list) = @_;

    foreach my $foo (@list) { 
        $base = &$fn($base, $foo);
    }

    return $base;
}

sub foldl1 {
    my ($fn, @list) = @_;

    my $base = shift @list;
    return &foldl($fn, $base, @list); 
}

sub foldr {
    my ($fn, $base, @list) = @_;

    foreach my $foo (reverse @list) {
        $base = &$fn($foo, $base); 
    }

    return $base;
}

sub foldr1 {
    my ($fn, @list) = @_;

    my $base = pop @list;
    return &foldr($fn, $base, @list); 
}

BEGIN { plan tests=>4 }

ok(&foldl (sub {$_[0] - $_[1]}, 11, (1..10)), -44);
ok(&foldl1(sub {$_[0] - $_[1]},     (1..10)), -53);
ok(&foldr (sub {$_[0] - $_[1]}, 11, (1..10)), 6);
ok(&foldr1(sub {$_[0] - $_[1]},     (1..10)), -5);
[download]

Comment on Haskell-style list folding Select or Download Code

Replies are listed 'Best First'.
Re: Haskell-style list folding by BrowserUk (Patriarch) on Jun 09, 2004 at 21:54 UTC
If I'm reading it right, your `foldl` routine is essentially the same as `reduce()` from List::Util. Examine what is said, not who speaks. "Efficiency is intelligent laziness." -David Dunham "Think for yourself!" - Abigail	[reply] [d/l] [select]
Re: Haskell-style list folding by adrianh (Chancellor) on Jun 09, 2004 at 22:32 UTC
You might want to take a look at Language::Functional.	[reply]
Re: Haskell-style list folding by hardburn (Abbot) on Jun 10, 2004 at 16:16 UTC
This is one of the places where prototypes would come in handy. `foldl (&$@)` would allow you to call it as: `my $data = foldl { . . . } $base, @data;` [download] Just like map/grep do now. You'll have to modify some of the code to handle the array ref being passed instead of a list. Also, change the `foreach` to not save to a lexical, but rather use the default of saving to local `$_` instead. That allows the subroutine to use a localized `$_`, just like map/grep do now. ---- send money to your kernel via the boot loader.. This and more wisdom available from Markov Hardburn.	[reply] [d/l] [select]