sub functional_FY {
  return @_ ? ( splice( @_, rand @_, 1 ), &functional_FY ) : @_;
}
[download]

Update: A functional splice, though, shouldn't have side-effects. It would either retrieve the values, or return the array without them. Or you could make one that sticks them on the front, maybe. I pronounce it a good start.

A functional splice, though, shouldn't have side-effects.

Then use a slice instead. No, that's not Perl keyword, instead, it's a pattern you implement using array indexes.

Since we need the same random index more than once, I stuff it into a temporary variable. I don't think you consider those very "functional", but what the heck...

sub quite_functional_FY {
    my $i = int rand @_;
    return @_ ? ($_[$i], quite_functional_FY(@_[0 .. $i-1, $i+1 .. $#_
+])) : ();
}
[download]

I think you can get a faster implementation by avoiding the recursion for lists that don't need shuffling: lists of one item (or less: 0).

sub quite_functional_FY {
    my $i = int rand @_;
    return @_ > 1 ? ($_[$i], quite_functional_FY(@_[0 .. $i-1, $i+1 ..
+ $#_])) : @_;
}
[download]

Yes, of course. What was I thinking? This is almost twice as fast as the "cut" approach I proposed, and clearer to boot. Ode to bart

the lowliest monk

I think I'd gotten stuck in the mindset that functional programming requires streams, but there's no reason you couldn't use slices. Variables are not strictly functional, per se, but it's trivial to have an auxiliary function that does the same thing, so I don't object to them.

I see there's some confusion about what qualifies as functional. That's probably my fault for not specifying. I punted, because I don't think I had it well-defined in my own mind. But I think I have a better idea now:

In the purest sense, a functional program is one in which nothing is modified — all new values are modified copies of something else. In keeping with that, the only variables are parameters to the functions.

Most functional languages allow for some practical exceptions to avoid cumbersome jumping through hoops, as in the case of your temp variable. I like your solution a lot.

---

Caution: Contents may have been coded under pressure.

I'd probably make that

sub functional_FY {
  return @_ ? ( splice( @_, rand @_, 1 ), &functional_FY ) : ();
}
[download]

so that the intention is clearer. Or does that mess up the callstack that &-style calling uses?

#!perl -l
use strict;
use warnings;

# Return the array, with the first and Nth elements swapped
sub swapcar {
    my ($arr, $n, $between) = @_;
    return (@$between, @$arr) if (@$arr <= 1 or $n == 0);
    my ($car1, $car2, @cdr) = @$arr;
    return (($n == 1)
           ? ($car2, @$between, $car1, @cdr)
           : swapcar([$car1, @cdr], $n-1, [@$between, $car2])
    );
}

sub FY_tail {
  my ($car, @cdr) = @_;
  return unless @cdr;
  ($car, functional_FY(@cdr));
}

sub functional_FY {
  my ($car, @cdr) = @_;
  return @cdr ? FY_tail(swapcar([@_], int rand @_, [])) : ($car);
}

print join ', ', functional_FY(my @foo = qw(a k q j 10)) for (1..5);
[download]

Update: Screwed up my swapcar horribly. Also had algorithm inverted. I think this is correct for Fisher-Yates.

I think the key is to get a random element in the first position, and repeat the process (recursively) with the rest of the list. IMO the easiest way to do this without side effects is simply to do a random "cut" of the array, and generate a new array from the swapped portions:

sub maybe_functional {
  return unless @_;
  my $n = int rand @_;
  my @arr = ( @_[$n .. $#_], @_[0 .. $n - 1] );
  return ( $arr[ 0 ], maybe_functional( @arr[ 1 .. $#arr ] ) );
}
[download]

the lowliest monk