Wiggins has asked for the wisdom of the Perl Monks concerning the following question:

In those thing that seem the most simple, may lay the greatest complexity..
This is a search for enlightment. I can see that it works, but I don't know why; is the definition of "faith"?

Page 36 of "Higher Order Perl" contains a function called "find_share", as part of a solution to the partitioning problem. 

sub find_share {
  my ($target, $treasures) = @_;
  return [] if $target == 0;
#  return 0 if $target == 0;    #my code experiment
#  return '' if $target == 0;   #my code experiment
#  return '0' if $target == 0;  #my code experiment
#  return () if $target == 0;   #my code experiment
#  return undef if $target == 0;#my code experiment
  return    if $target < 0 || @$treasures == 0;

  my ($first, @rest) = @$treasures;
  my $solution = find_share($target-$first, \@rest);
  return [$first, @$solution] if $solution;
  return         find_share($target       , \@rest);
}

sub partition {
  my $total = 0;
  my $share_2;
  for my $treasure (@_) {
    $total += $treasure;
  }
  my $share_1 = find_share($total/2, [@_]);
  return unless defined $share_1;
  my %in_share_1;
  for my $treasure (@$share_1) {
    ++$in_share_1{$treasure};
  }
  for my $treasure (@_) {
    if ($in_share_1{$treasure}) {
      --$in_share_1{$treasure};
    } else {
      push @$share_2, $treasure;
    }
  }

## My code to run samples
my ($rslt1,$rslt2) = partition ( 1,5,3,1,6,2 );
if ($rslt1){
  printf "rslt1= %s\n",join ',',@$rslt1;
  printf "rslt2= %s\n",join ',',@$rslt2;
}

[download]
The accompanying text says:
We take care of some trivial cases first. If the target amount is exactly zero, then it's easy to produce a list of treasures that total the target amount: the empty list is sure to have value zero, so we return that right away.
? return the 'empty list' right away? Wouldn't that be ()?
? [] = empty list?

The closer I look, the more puzzling things are. But I think they all revolve around the use of the Anonymous Array Composer to passing references rather than data.

The calling sequence is: 

my $share_1 = find_share($total/2, [@_]);

[download]
which passes as argument 2, I am hoping; the parameter array and re-encapsulates it in an anonymous array and passes the reference to the encapsulation to find_share.
find_share returns references to anon arrays as well. Looking at the variable $solution, I see it is set with the return value from a recursive call the this code; and subsequently used in a Boolean context on the next line.
Checking "perlsyn::Truth and Falsehood" to see what would make $solution FALSE, gives:
The number 0, the strings '0' and '', the empty list "()", and "undef" are all false in a boolean context. All other values are true.
None of those values worked in place of [] (the commented lines). So what type and value is $solution???
It is always better to have seen your target for yourself, rather than depend upon someone else's description.

Replies are listed 'Best First'.
Re: A new FALSEness
by tilly (Archbishop) on Mar 03, 2009 at 20:56 UTC
    $solution is an anonymous array reference with the solution if a solution was found, and otherwise it is undef.

    Note that the use of [] vs undef is necessary so you can distinguish between saying that an empty list is a valid solution, and there was no solution found.

[reply]
[d/l]
[select]
Re: A new FALSEness
by ikegami (Patriarch) on Mar 03, 2009 at 20:57 UTC

    return the 'empty list' right away? Wouldn't that be ()?

    It seems to be speaking abstractly. It's speaking of the list of results, and not of the data format used to represent the list of results.

    find_share actually returns a reference to an array containing the list of results. So where the documentation says an empty list (of results) is returned, the implementation returns a reference to an empty array. 

    my $share_1 = find_share($total/2, [@_]);

if (!@$share_1) {
   print("No results\n");
}

    [download]
[reply]
[d/l]
[select]
Re: A new FALSEness
by kyle (Abbot) on Mar 03, 2009 at 21:07 UTC

    This line returns a false value: 

      return    if $target < 0 || @$treasures == 0;

    [download]

    ? [] = empty list?

    As you say later, it's a reference to an empty (anonymous) array, not an empty list.

[reply]
[d/l]
      More particularly, the statement
          return if $target < 0 || @$treasures == 0;
      returns undef in scalar context and the empty list  () in list context.

      Both of these return values evaluate as false, so this statement returns a false value regardless of the context in which the function was called.

[reply]
[d/l]
[select]
        But "false" is a scalar concept. Any boolean test is scalar context.
[reply]
Re: A new FALSEness
by hbm (Hermit) on Mar 04, 2009 at 14:22 UTC

    You may want to jump ahead to HOP Chapter 4, section 4.5, "The Semipredicate Problem". It talks about "alternative undefs", and returning a reference for a guaranteed distinct value.

[reply]

Back to Seekers of Perl Wisdom