MathGroup Archive 1995

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: how can I do this functionally?

  • To: mathgroup at
  • Subject: [mg941] Re: how can I do this functionally?
  • From: rubin at (Paul A. Rubin)
  • Date: Wed, 3 May 1995 00:20:25 -0400
  • Organization: Michigan State University

In article <3nn4h3$91f at>,
   drc at (David Cabana) wrote:
->Below I define a function, Classify[S_, f_], in an imperative (and
->not particularly efficient) style.  Can anyone tell me how to define 
->it either functionally or via pattern matching?
->The function Classify takes 2 arguments, f and S.  f is a function,
->and S is a subset of the domain of S.  In particular, S is a list
->of elements of the domain of f, and contains no repeated elements.
->The function f induces an equivalence relation on S as follows:
->a is equivalent to b modulo f if and only if f[a] == f[b]. Classify
->returns the equivalence classes of S modulo f. 

The following is a mix of pattern matching and list-oriented functional 
stuff.  I use a marker ($Nil) to indicate the end of a list of pairs 
{f(a), a} having common function value; my version of Classify calls a 
second function (breakup) to split that list up into sublists by function 
value (i.e., every run of elements up to a marker becomes a new sublist, 
and the markers are dropped).  The breakup function is defined recursively, 
and uses pattern matching in the arguments.

breakup[ {a__, {_, $Nil}, c__} ] :=
  {{a}, Sequence @@ breakup[ {c} ]}
breakup[ {a__, {_, $Nil}} ] := {{a}}
Classify[ s_, f_ ]:=
    {x, y},
    x = {f[ # ], #}& /@ s;
    y = {#, $Nil}& /@ Union[ f /@ s ];
    Last /@ (Transpose /@ (breakup @ Sort @ Join[ x, y ]))


* Paul A. Rubin                                  Phone: (517) 432-3509   *
* Department of Management                       Fax:   (517) 432-1111   *
* Eli Broad Graduate School of Management        Net:   RUBIN at MSU.EDU    *
* Michigan State University                                              *
* East Lansing, MI  48824-1122  (USA)                                    *
Mathematicians are like Frenchmen:  whenever you say something to them,
they translate it into their own language, and at once it is something
entirely different.                                    J. W. v. GOETHE

  • Prev by Date: Re: Re: Strange answer from Eigensytem
  • Next by Date: Re: Challenge!
  • Previous by thread: Re: Re: Strange answer from Eigensytem
  • Next by thread: Re: how can I do this functionally?