Haskell中非二叉树的工作原理、内存结构及使用问题咨询

1. 语法错误优先修正 #

你写的代码运行报错首先是两个基础语法问题：

1. 数据类型定义未声明泛型参数：a是节点存储值的泛型类型，需要绑定到类型构造器上，正确的多叉树定义如下：

data Tree a = Node a [Tree a]

2. 构造节点时缺少参数：数据构造器Node需要接收两个参数，第一个是当前节点的存储值，第二个是子节点组成的列表，哪怕没有子节点也要传入空列表[]，修正后的示例代码如下：

t1 = Node 10 []
t2 = Node 20 []
t3 = Node 30 [t1, t2]

上述代码可以直接正常运行。

2. 与面向对象语言的结构对比 #

你可以直接类比Java中常见的多叉树节点定义，二者逻辑完全一致：

class TreeNode<T> {
    T value;
    List<TreeNode<T>> children;
    
    public TreeNode(T value, List<TreeNode<T>> children) {
        this.value = value;
        this.children = children;
    }
}

对应关系如下：

• Haskell的Tree a类型等价于Java的TreeNode<T>泛型类
• Haskell的Node数据构造器等价于Java的构造方法，其中第一个参数a对应value字段，第二个参数[Tree a]对应children字段
• 你之前写的t1 = Node 10等价于Java中只传一个参数调用构造方法，必然会报参数不匹配的错误，补全空列表的操作等价于Java中new TreeNode<>(10, Collections.emptyList())

3. 内存排布与调用方式说明 #

内存结构 #

Haskell的代数数据类型内存排布和面向对象语言的引用逻辑高度相似：

• 每个Node实例对应一块内存，存储两个指针：一个指向当前节点的存储值，一个指向子节点列表的头节点
• 子节点列表是Haskell的普通链表，每个元素都是指向其他Node实例的指针，和Java中List存储对象引用的逻辑完全一致，只是默认是惰性求值，访问时才会实际计算子节点的值。

字段调用 #

你可以通过模式匹配实现类似OO中getter的效果，示例如下：

-- 等价于Java中的getValue方法
getValue :: Tree a -> a
getValue (Node val _) = val

-- 等价于Java中的getChildren方法
getChildren :: Tree a -> [Tree a]
getChildren (Node _ children) = children

调用示例：

-- 返回30
getValue t3
-- 返回[t1, t2]
getChildren t3
-- 返回10
getValue $ head $ getChildren t3

4. 常用操作示例 #

以前序遍历为例，逻辑和OO中递归遍历完全一致，只是写法更简洁：

preOrder :: Tree a -> [a]
preOrder (Node val children) = val : concatMap preOrder children

调用preOrder t3会返回[30,10,20]。

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