prolog - 为什么二叉树实现为嵌套项，而不是嵌套列表？

Question

我知道这是一个模糊的问题，但仍然是：使它们比列表更适合嵌套的术语是什么？还是列表（内部）是嵌套术语的微不足道的情况？

（我意识到我可以“使用源代码”，例如 SWI-Prolog，但如果指向正确方向的指针将不胜感激）

Answer 1

如果您事先不知道元素的数量，则使用列表是有意义的。如果很明显每个实体都有固定数量的元素（就像二叉树中的节点一样），那么使用具有固定数量的术语比列表更节省内存。例如考虑结构：

node(Name, Left, Right)

这总共需要 4 个存储单元：一个用于函子，三个用于参数。

使用列表（在这种情况下[Name, Left, Right]）总共占用大约两倍的内存：

'.'(Name, '.'(Left, '.'(Right, []))).

3 个用于列表函子 ('.') 的单元格，1 个用于 的单元格[]，以及三个用于参数的单元格。

也很挑剔：您当然知道，列表也是一个术语。不是列表、数字、对等的术语有时称为“结构”。

Answer 2

如前所述，Prolog 列表只是两个术语之上的语法糖：'.'/2 和'[]'。有关详细信息，请参阅此答案：Flatten a list in Prolog