This can probably be golfed to high heaven, but my question is, is it "functional" enough?

use strict;

sub functional_FY {
  return @_ if @_ < 2;
  my $i = rand @_;
  @_[ 0, $i ] = @_[ $i, 0 ];
  return ( shift, functional_FY( @_ ) );
}

print "@{ [ functional_FY( 1..10 ) ] }\n";
[download]

Golf 1:

sub functional_FY {
  return @_ if @_ < 2;
  return ( splice( @_, rand @_, 1 ), &functional_FY );
}
[download]

Golf 2:

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

I pronounce if functional enough, when you use splice. Clearly, splice could be written as a separate function. (I could probably do that.) I would further golf #2 into

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

which is, I think, something of an improvement as well. Splicing the only element out of an array is certainly valid.

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.

---

Caution: Contents may have been coded under pressure.

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]

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?

I've tried to make this excruciatingly functional. Have I got it right?

#!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]

Some things are definitely not more intuitive in functional programming.

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

---

Caution: Contents may have been coded under pressure.

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

The Schwartzian Shuffle:

@ryaar =
  map  { $_->[ 0 ] }
  sort { $a->[ 1 ] <=> $b->[ 1 ] }
  map  { [ $_, rand ] }
  @array
[download]

Not "functional". Just plain functional.™

Isn't it the case that random number generators do not entirely fit into the "pure functional" programming paradigm? I seem to recall reading somewhere that obtaining random numbers in Haskell involves the use of Monads, which is a kind of stretching of the concept of pure functional programming (maybe this is why I have never been able to really understand Monads?)...

This leads me to think that pure functional progamming is not the best way to attack the list shuffle problem...

rg0now

Indeed a "functional shuffle" is a contradiction in terms. In functional programming, if you give a function the same inputs you must get the same outputs. Rand is resetting a seed somewhere, which is a disallowed side-effect in a pure functional program. However, one could define a shuffle that took a list of random numbers from some outside source as an input. The paper referenced by the OP does this.

You may very well be right. I did notice that in the article that Roy Johnson linked on the Haskell implementation the author spent longer than I would have expected on the discussion of the random numbers, which gave me the impression that the generation of random numbers has a conceptually different place, or different standing if you will, in the Haskell world than I'm used to from other programming languages.

But to be honest, I barely understand what this requirement that the shuffle be "functional" is, as is probably plainly obvious from my various stabs at it.

the lowliest monk

Sort-based shuffles like this are not good shuffles. You do not get all N! permutations with equal probability. The Fisher-Yates shuffle can do it; this one does not. The discussion under When the Best Solution Isn't and under other recent shuffle threads (like Is this a fair shuffle?) explains why.

I agree that the sort-based shuffles discussed in When the Best Solution Isn't are fundamentally wrong, but this is one is qualitatively different; it doesn't work by tinkering with the sort function, but rather by assigning randomly numbered indexes to the elements of the array, and then sorting the array according to these indexes. The number of possible rank orderings of N randomly chosen real numbers r₁,...,r_N in the unit interval is N!.

The objection to this shuffle, I suspect, is not on the grounds of correctness but rather on the grounds of efficiency.

Also, whether this meets Roy Johnson's original requirement that the shuffle be in a "functional" vein (whatever that means) is highly dubious.

the lowliest monk

Did you compare the code above to the faulty code in your link? The code above is indeed a fair shuffle. Sort-based shuffles that use rand in the comparison block are the ones that don't work. See Re: Is this a fair shuffle?.

blokhead