递归类型的默认递归

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 需要递归到子表达式中。在这个玩具示例中，这很容易做到，只需要几行额外的代码，但在真实的程序中，会有几十种表达式类型；人们更愿意避免向每个对表达式进行操作的函数添加数十行样板文件。

有什么方法可以表达'by default, recur on subexpressions'？类似于：

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# 没有提供任何递归函数来处理您的数据类型 "for free"。您可能可以使用反射生成一个 - 如果您有很多递归类型，这将是有效的，但在正常情况下可能不值得。

尽管如此，您可以使用多种模式来隐藏重复。我发现特别好的一个是基于 ExprShape module from standard F# libraries。这个想法是定义一个活动模式，使您可以将类型视为叶（没有嵌套子表达式）或节点（具有子表达式列表）：

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

递归类型的默认递归

Default recursion on recursive types

recursion

f#