[perl-python] generic equivalence partition

From: Xah Lee (xah_at_xahlee.org)
Date: 02/24/05 

Date: 24 Feb 2005 03:48:53 -0800

another functional exercise with lists.

Here's the perl documentation. I'll post a perl and the translated
python version in 48 hours.

=pod

parti(aList, equalFunc)

given a list aList of n elements, we want to return a list that is a
range of numbers from 1 to n, partition by the predicate function of
equivalence equalFunc. (a predicate function is a function that
takes two arguments, and returns either True or False.)

Note: a mathematical aspect: there are certain mathematical constraints
on the a function that checks equivalence. That is to say, if a==b,
then b==a. If a==b and b==c, then a==c. And, a==a. If a equivalence
function does not satisfy these, it is inconsistent and basically give
meaningless result.

example:
parti([['x','x','x','1'],
['x','x','x','2'],
['x','x','x','2'],
['x','x','x','2'],
['x','x','x','3'],
['x','x','x','4'],
['x','x','x','5'],
['x','x','x','5']], sub {$_[0]->[3] == $_[1]->[3]} )

returns
 [[1],['2','3','4'],['5'],['6'],['7','8']];

=cut

In the example given, the input list's elements are lists of 4
elements, and the equivalence function is one that returns True if the
last item are the same.

Note that this is a generic function. The input can be a list whose
elements are of any type. What "parti" does is to return a partitioned
range of numbers, that tells us which input element are equivalent to
which, according to the predicate given. For example, in the given
example, it tells us that the 2nd, 3rd, 4th elements are equivalent.
And they are equivalent measured by the predicate function given, which
basically tests if their last item are the same integer. (note that if
we want to view the result as indexes, then it is 1-based index. i.e.
counting starts at 1.)

PS if you didn't realize yet, nested lists/dictionaries in perl is a
complete pain in the ass.

PS note that the code "sub {$_[0]->[3] == $_[1]->[3]}" is what's called
the lambda form, in Perl.

 Xah
 xah@xahlee.org
 http://xahlee.org/PageTwo_dir/more.html

Relevant Pages

  • [perl-python] generic equivalence partition
    ... Here's the perl documentation. ... on the a function that checks equivalence. ... the input list's elements are lists of 4 ...
    (comp.lang.python)
  • Re: [perl-python] generic equivalence partition
    ... > another functional exercise with lists. ... I'll post a perl and the translated ... and the equivalence function is one that returns True if the ...
    (comp.lang.python)
  • Reg. Directory listing program
    ... I am new to this mailing list and I am very new to PERL. ... I wrote a code that lists files in a directory with the permissions. ... Directory listing program ...
    (perl.beginners)
  • Emulating Generators: Iterators for Lists (Newbie)
    ... achieving various things in Perl. ... What would be a good way to do an iterator for a sequence of values to be ... sub-routine, and declare the state you need to maintain between sub calls ... lists which might be the answer. ...
    (comp.lang.perl.misc)
  • FAQ 4.46 How do I handle linked lists?
    ... comes with the standard Perl distribution. ... How do I handle linked lists? ... Both pop and shift are both Ooperations on ... The perlfaq-workers, a group of volunteers, maintain the perlfaq. ...
    (comp.lang.perl.misc)