Programmatically creating multivariate functions i

Question

This is a split from discussion on earlier question.

Suppose I need to define a function f which checks if given labeling of a graph is a proper coloring. In other words, we have an integer assigned to every node and no two adjacent nodes get the same answer. For instance, for {"Path",3}, f[{1,2,3}] returns True and f[{1,1,2}] returns False. How would I go about creating such a function for arbitrary graph?

The following does essentially what I need, but generates Part warnings.

g[edges_] := Function @@ {{x}, And @@ (x[[First[#]]] != x[[Last[#]]] & /@ edges)}
f = g[GraphData[{"Path", 3}, "EdgeIndices"]];
f[{1, 2, 1}]==False

This is a toy instance problem I regularly come across -- I need to programmatically create a multivariate function f, and end up with either 1) part warning 2) deferring evaluation of g until evaluation of f

Answer 1

Here's something. When nothing else is working, Hold and rules can usually get the job done. I'm not sure it produces the correct results w.r.t. your graph-coloring question but hopefully gives you a starting place. I ended up using Slot instead of named variable because there were some scoping issues (also present in my previous suggestion, x$ vs. x) when I used a named variable that I didn't spend the time trying to work around.

g[edges_] := 
 With[{ors = (Hold @@ edges) /. {a_, b_} :> #[[a]] == #[[b]]},
  Function[!ors] /. Hold -> Or
  ]

In[90]:= f = g[GraphData[{"Path", 3}, "EdgeIndices"]]
Out[90]= !(#1[[1]] == #1[[2]] || #1[[2]] == #1[[3]]) &

In[91]:= f[{1, 2, 3}]
Out[91]= True

In[92]:= f[{1, 1, 2}]
Out[92]= False

I feel like it lacks typical Mathematica elegance, but it works. I'll update if I'm inspired with something more beautiful.

Answer 2

There are a couple other solutions to this kind of problem which don't require you to use Hold or ReleaseHold, but instead rely on the fact that Function already has the HoldAll attribute. You first locally "erase" the definitions of Part using Block, so the expression you're interested in can be safely constructed, and then uses With to interpolate that into a Function which can then be safely returned outside of the Block, and also uses the fact that Slot doesn't really mean anything outside of Function.

Using your example:

coloringChecker[edges_List] := 
 Block[{Part},
  With[{body = And @@ Table[#[[First@edge]] != #[[Last@edge]], {edge, edges}]},
   body &]]

I don't know if this is all that much less cumbersome than using Hold, but it is different.

Answer 3

I'm still puzzled by the difficulties that you seem to be having. Here's a function which checks that no 2 consecutive elements in a list are identical:

f[l_List] := Length[Split[l]] == Length[l]

No trouble with Part, no error messages for the simple examples I've tried so far including OP's 'test' cases. I also contend that this is more concise and more readable than either of the other approaches seen so far.