OCaml变体模式匹配错误：二叉树中序遍历递归实现报错

错误原因 #

你的inorder函数参数定义冗余，导致函数类型不符合预期。代码里let rec inorder bt = function...的写法，相当于让inorder接受两个参数：第一个是bt，第二个是function关键字匹配的二叉树节点。但调用时你只传了一个二叉树节点，所以函数返回的是btnode -> string类型的函数，而非预期的string，这就触发了类型错误。

修正方案 #

有两种简洁的修正方式：

方式1：移除多余的bt参数，直接用function匹配

type btnode =
  | Leaf
  | Node of string * btnode * btnode

let rec inorder = function
  | Leaf -> ""
  | Node(s, left, right) -> 
    (inorder left) ^ s ^ (inorder right)
  
let tree = inorder (Node("a", Node("b", Leaf, Leaf), Leaf))

方式2：不用function，直接匹配bt参数

type btnode =
  | Leaf
  | Node of string * btnode * btnode

let rec inorder bt =
  match bt with
  | Leaf -> ""
  | Node(s, left, right) -> 
    (inorder left) ^ s ^ (inorder right)
  
let tree = inorder (Node("a", Node("b", Leaf, Leaf), Leaf))

补充说明 #

两种写法本质都是让inorder只接受一个btnode类型的参数，递归遍历后返回拼接好的字符串。调用时给Node表达式加上括号，可避免语法歧义。

内容的提问来源于stack exchange，提问作者Dantezo Ribaldi