具有单位类型输出的地图功能

Question

type ('a, 'b) t=
  | Leaf of 'b
  | Node of 'a * ('a, 'b) t* ('a, 'b) t
              

我想实现一个带有签名的

map f g t

函数：

val map: (('a -> unit) * ('b -> unit)) -> ('a,'b) t -> unit

地点：

f

到所有节点数据

g

到所有叶子数据

它应该通过前序遍历（根-左-右）进行迭代

这是我试过的：

let rec map f g t = 
  match t with
  | Leaf(w)  -> Leaf(g w)
  | Node (v, l, r) -> Node (f v, map f g l, map f g r)

但是我不知道如何匹配那个签名，有什么想法吗？

Answer 1

如果您希望

f

和

g

都具有

unit

的返回类型，那么这根本就不是真正的

map

。它更像是一个

iter

函数，你可以这样写：

let rec iter f g =
  function
  | Leaf v -> let () = g v in ()
  | Node (v, l, r) ->
    let () = f v in
    let () = iter f g l in
    iter f g r

这个函数具有以下类型，因为我们已经向编译器提供了足够的信息来推断

f

和

g

返回

unit

.

('a -> unit) -> ('b -> unit) -> ('a, 'b) t -> unit

请注意，这也保证了对左分支的递归调用将首先发生，而

Node (f v, map f g l, map f g r)

中的评估顺序可能会在不同的实现之间发生变化。