0

我试图将通用二叉树表示为一对。

我将使用 SML 语法作为示例。这是我的 btree 类型定义：

datatype btree = leaf | branch of btree*btree;

所以，我想写一个函数，给定一个 btree，打印以下内容：

bprint leaf = 0
bprint (branch (leaf,leaf)) = (0,0)
bprint (branch (leaf, branch (leaf,leaf))) = (0, (0, 0))

等等。

问题是这个函数总是返回不同的类型。这显然是 SML 的问题，也可能是其他函数式语言的问题。

任何想法？

4

2 回答 2

1

如果您真的不需要其他任何地方的字符串表示，正如其他人已经提到的那样，只需打印树可能是最简单的方法：

open TextIO

datatype btree = leaf | branch of btree * btree

fun print_btree leaf = print "0"
  | print_btree (branch (s, t)) =
    (print "("; print_btree s; print ", "; print_btree t; print ")")

如果您还希望能够获得一个表示 a 的字符串btree，那么简单的解决方案是：

fun btree_to_string leaf = "0"
  | btree_to_string (branch (s, t)) =
    "(" ^ btree_to_string s ^ ", " ^ btree_to_string t ^ ")"

但是，我并不真正推荐这种变体，因为对于 big btrees，由于许多字符串连接存在问题。

值得考虑的是以下变体，它通过一个技巧（例如也用于 Haskell 的Show类中）避免了连接问题，即，不是处理字符串，而是处理从 char 列表到 char 列表的函数。然后可以用函数组合代替串联

fun btree_to_string' t =
  let
    fun add s t = s @ t
    fun add_btree leaf = add [#"0"]
      | add_btree (branch (s, t)) =
        add [#"("] o add_btree s o add [#",", #" "] o add_btree t o add [#")"]
  in implode (add_btree t []) end
于 2013-04-25T04:51:27.360 回答
1

由于您要做的就是将树结构打印到屏幕上，因此您可以这样做并让函数的返回类型为unit. 这不是试图返回元组(0, (0, 0))，而是将字符串 (0, (0, 0)) 打印到屏幕上。这样你就不会在类型方面遇到任何困难。

于 2013-04-24T21:53:54.807 回答