任意深度嵌套模式匹配

Question

有没有办法创建一个Mathematica模式,匹配其头部可能任意深度的表达式,即类似的东西f[___][___][___]...？

Answer 1

建议的解决方案

似乎没有内置构造来自动模式测试嵌套头.我们可以通过编写一个函数来实现目标,该函数对于表单的任何给定(子)表达式f[___]...[___],有效地确定f(对于术语的轻微滥用,我们可以称之为表达式的符号头).这是代码:

ClearAll[shead];
SetAttributes[shead, HoldAllComplete];
shead[expr_] := Scan[Return, Unevaluated[expr], {-1}, Heads -> True];

以下是它的使用方法(我将使用与@Sasha相同的测试集):

In[105]:= Cases[{f[1], g[f[1]], f[1, 2, 3][1], f[1][2][3][4]}, x_ /; shead[x] === f]

Out[105]= {f[1], f[1, 2, 3][1], f[1][2][3][4]}

模式语法

如果您更喜欢使用@Sasha建议的语法,那么该版本看起来就像

Clear[headPattern];
headPattern[head_] := _?(Function[Null, shead[#] === head, HoldFirst]);

In[108]:= Cases[{f[1], g[f[1]], f[1, 2, 3][1], f[1][2][3][4]}, headPattern[f]]

Out[108]= {f[1], f[1, 2, 3][1], f[1][2][3][4]}

进一步的解释和评论

这个怎么运作

以下是导致此解决方案的逻辑以及工作原理的一些提示.如果我们设法利用一些内置的表达式遍历函数,那么解决方案将是最简洁和高效的.一些浮现在脑海中的Map,Scan,Cases,MapIndexed,Position.鉴于我们需要头部,我们需要通过Heads->True选项.我使用过Scan,因为这个很容易在任何一点停止(不像其他提到的构造,你通常需要抛出一个例外来阻止它们"在中间",这是相当不优雅的,并且还会产生一些开销)一旦我们找到了我们想要的东西.我们的结果将是在Scan深度优先表达式遍历中找到的第一个结果,因此预期它非常有效(它不会遍历整个表达式).

避免评估泄漏

另一个评论是关于评估.您可以看到该HoldAllComplete属性已在其中使用shead,并Unevaluated在其正文中使用.这些非常重要 - 它们用于防止对传递给函数的表达式进行可能的评估.这样的情况可能很重要:

In[110]:= m = n = 0;
g[x_] := n++;
h[x_] := m++;
{Cases[Hold[f[g[1]][h[2]]], x_ /; shead[x] === f :> Hold[x], Infinity], {m, n}}

Out[113]= {{Hold[f[g[1]][h[2]]]}, {0, 0}}

在这里,我们看到了我们所期望的 - 尽管Cases已经遍历整个表达并将其(子)部分馈送到shead,但是没有触发子部分的评估shead.现在我们定义一个天真的版本,shead其中"泄漏评估":

sheadEval[expr_] := Scan[Return, expr, {-1}, Heads -> True]

现在,

In[114]:= {Cases[Hold[f[g[1]][h[2]]], x_ /; sheadEval[x] === f :> Hold[x], Infinity], {m, n}}

Out[114]= {{Hold[f[g[1]][h[2]]]}, {2, 1}}

后者的行为一般不令人满意.整个代码是数据范例,在元编程中非常有用,在Mathematica中非常强大,因为您可以使用规则来解构代码.在模式匹配期间可能的(不需要的)评估会极大地损害它.整个问题在于子部分.环绕Hold仅阻止整个表达式的评估.Cases用于代码解构的函数 和其他类似函数是如此之大,因为它们在进行结构(语法)匹配时不会评估子部分.

评论符号头

这里的最后一条评论(主要是关于定义)是shead函数返回的不完全是Mathematica中通常称为符号头的东西.不同之处在于原子表达式.例如,shead[f]返回f,而对于原子表达式,真正的符号头应该与表达式的头部重合(Symbol在本例中).我已经在这里开发了symbolicHead具有这种行为的函数,并且也可以成功地用于代替上面的函数,尽管效率更高.sheadshead

Answer 2

以下内容如何:

In[277]:= 
ArbitrarilyDeepHeadPattern[
  head_Symbol] := _?(Function[
    MemberQ[
      Position[#, _head, {0, Infinity}, Heads -> True], {0 ...}]])

In[281]:= Cases[{f[1], g[f[1]], f[1, 2, 3][1], f[1][2][3][4]}, 
 ArbitrarilyDeepHeadPattern[f]]

Out[281]= {f[1], f[1, 2, 3][1], f[1][2][3][4]}

Answer 3

这里可以使用递归匹配策略:

curried[head_] := _head | (x_[___] /; MatchQ[Hold[x], _[curried[head]]])

用法:

In[26]:= $testCases = {f, f[1], g[f[1]], f[1,2,3][1], f[1][2][3][4]};
         Cases[$testCases, curried[f]]

Out[27]= {f[1],f[1,2,3][1],f[1][2][3][4]}

更新

在Leonid的建议中,Unevaluated可以用作更清晰,更快捷的方法来避免模式条件中的评估泄漏:

curried[head_] := _head | (x_[___] /; MatchQ[Unevaluated[x], curried[head]])