recursion - 递归类型的默认递归

Question

惯用的 F# 可以很好地表示经典的递归表达式数据结构:

type Expression = 
    | Number of int
    | Add of Expression * Expression
    | Multiply of Expression * Expression
    | Variable of string

连同递归函数:

let rec simplify_add (exp: Expression): Expression = 
    match exp with
    | Add (x, Number 0) -> x
    | Add (Number 0, x) -> x
    | _ -> exp

... 哎呀，这不像写的那样工作； simplify_add需要递归到子表达式中。在这个玩具示例中，它很容易做到，只有几行额外的代码，但在真正的程序中会有几十种表达式类型；人们宁愿避免向每个对表达式进行操作的函数中添加几十行样板。

有什么方法可以表达“默认情况下，在子表达式上重复”？就像是:

let rec simplify_add (exp: Expression): Expression = 
    match exp with
    | Add (x, Number 0) -> x
    | Add (Number 0, x) -> x
    | _ -> recur simplify_add exp

哪里 recur可能是某种使用反射来查找类型定义或类似的高阶函数？

Answer 1

不幸的是，F# 没有为您提供任何递归函数来“免费”处理您的数据类型。您可能可以使用反射生成一个 - 如果您有很多递归类型，这将是有效的，但在正常情况下可能不值得。

不过，您可以使用多种模式来隐藏重复。我觉得特别好的一个是基于 ExprShape module from standard F# libraries .这个想法是定义一个事件模式，让您可以将您的类型 View 作为叶子(没有嵌套的子表达式)或节点(带有子表达式列表):

type ShapeInfo = Shape of Expression

// View expression as a node or leaf. The 'Shape' just stores
// the original expression to keep its original structure
let (|Leaf|Node|) e = 
  match e with
  | Number n -> Leaf(Shape e)
  | Add(e1, e2) -> Node(Shape e, [e1; e2])
  | Multiply(e1, e2) -> Node(Shape e, [e1; e2])
  | Variable s -> Leaf(Shape e)

// Reconstruct an expression from shape, using new list 
// of sub-expressions in the node case.
let FromLeaf(Shape e) = e
let FromNode(Shape e, args) = 
  match e, args with
  | Add(_, _), [e1; e2] -> Add(e1, e2)
  | Multiply(_, _), [e1; e2] -> Multiply(e1, e2)
  | _ -> failwith "Wrong format"

这是您必须编写的一些样板代码。但好消息是我们现在可以编写递归 simplifyAdd仅使用您的特殊情况和叶和节点的两个附加模式来运行:

let rec simplifyAdd exp =
    match exp with
    // Special cases for this particular function
    | Add (x, Number 0) -> x
    | Add (Number 0, x) -> x
    // This now captures all other recursive/leaf cases
    | Node (n, exps) -> FromNode(n, List.map simplifyAdd exps)
    | Leaf _ -> exp