Re: how can I do this functionally?
- To: mathgroup at christensen.cybernetics.net
- Subject: [mg941] Re: how can I do this functionally?
- From: rubin at msu.edu (Paul A. Rubin)
- Date: Wed, 3 May 1995 00:20:25 -0400
- Organization: Michigan State University
In article <3nn4h3$91f at news0.cybernetics.net>, drc at gate.net (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. [chomp] 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_ ]:= Module[ {x, y}, x = {f[ # ], #}& /@ s; y = {#, $Nil}& /@ Union[ f /@ s ]; Last /@ (Transpose /@ (breakup @ Sort @ Join[ x, y ])) ] Paul ************************************************************************** * 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