将函数应用于F#中的自定义类型

Question

在我学习F#的过程中,我遇到了一个我无法解决的问题.我已经定义了一个自定义类型:

type BinTree = 
  | Node of int * BinTree * BinTree
  | Empty

我创建了一个函数,它接受一个树,遍历它,并将它访问的元素添加到列表中,并返回它:

let rec inOrder tree = 
 seq{
 match tree with
  | Node (data, left, right) ->
   yield! inOrder left
   yield  data;
   yield! inOrder right
  | Empty -> ()
 }
 |> Seq.to_list;

现在我想创建一个类似于此的函数,它接受树和函数,遍历它并将函数应用于每个节点,然后返回树:

mapInOrder : ('a -> 'b) -> 'a BinTree -> 'b BinTree

这看起来很简单,而且很可能!但我不知道如何归还树.我试过这个:

let rec mapInOrder f tree = 
 match tree with
 | Node(data, left, right) ->
  mapInOrder f left
  Node(f(data), left, right)
  mapInOrder f right
 | Empty -> ()

但这会返回一个单位.我之前没有使用自定义类型,所以我可能在那里遗漏了一些东西!

Answer 1

试试这个:

let rec mapInOrder f = function
  | Node(a,l,r) ->
      let newL = mapInOrder f l
      let b = f a
      let newR = mapInOrder f r
      Node(b,newL,newR)
  | Empty -> Empty

如果该函数是无副作用的,则遍历顺序并不重要,您可以改为:

let rec map f = function
  | Node(a,l,r) -> Node(f a, map f l, map f r)
  | Empty -> Empty