README

Treegami 是一个小型库，用于映射和折叠任意形状的树。作为程序员，我们经常与树打交道，无论是在公开场合还是在隐藏状态下，例如当它们伪装成 JSON 文档时。Treegami 使转换这些结构并从中提取数据变得容易。Treegami 的名称是单词“tree”和“origami”的缩合词。

要求

PHP 7.1+

安装

$ composer require pwm/treegami

用法

让我们先手动创建一个树

$tree = new Tree(
    'first', [ // node has 3 children
        new Tree('second', [ // node has 2 children
            new Tree('third'),  // children are optional and defaults to []
            new Tree(), // node value is optional and defaults to null
        ]),
        new Tree('fourth', []), // explicitly saying no children
        new Tree('fifth', [
            new Tree(null, []) // explicitly saying no node value or children
        ]),
    ]
);

结果如下树

        ____first____
       /      |      \
    second  fourth  fifth
    /    \            |
 third   null        null

现在让我们使用一个将字符串映射到其长度并将 null 映射到 0 的函数来映射此树

$mappedTree = $tree->map(function (?string $node): int {
    return is_string($node)
        ? strlen($node)
        : 0;
});

结果如下树

        ____5____
       /    |    \
      6     6     5
     / \          |
    5   0         0

现在让我们将此树折叠为其节点值的总和

$foldedTree = $mappedTree->fold(function (int $node, array $acc): int {
    return $node + array_sum($acc);
});

assert($foldedTree === 27); // true

最后，一个从种子值展开树示例

$tree = Tree::unfold(function (int $x): array {
    return $x < 2 ** 3
        ? [$x, range(2 * $x, 2 * $x + 1)]
        : [$x, []];
}, 1);

结果如下完全二叉树

        ______1______
       /             \
    __2__           __3__
   /     \         /     \
  4       5       6       7
 / \     / \     / \     / \
8   9  10  11  12  13  14  15

工作原理

一些（大多数？）的读者可能熟悉列表上的高阶函数 map 和 fold。在 PHP 中，它们分别称为 array_map 和 array_reduce。

作为一个快速回顾：函数 map 通过对其元素应用函数将列表映射到另一个列表，而函数 fold 通过对其元素应用函数并将它们累积到最终值来“折叠”列表。例如，如果我们有一个将数字加一的函数 addOne，那么 map(addOne, [1,2,3,4,5]) 的结果是 [2,3,4,5,6]。然后，如果我们有一个将两个数字相加的函数 add，那么 fold(add, 0, [2,3,4,5,6])，其中 0 是种子值，结果是 0+2+3+4+5+6 = 20。

但是，map 和 fold 并不特定于列表。实际上，许多不同的结构都可以进行映射和折叠，包括树。在树上映射一个函数会得到另一个相同形状的树，其中每个节点都是应用该函数的结果。使用函数折叠树意味着遍历树，对其节点应用函数并将它们累积到最终值。

例如，如果我们有以下树

        ______1______
       /             \
    __2__           __3__
   /     \         /     \
  4       5       6       7
         / \       \
        8   9      10

然后映射 addOne 到它上面会得到

        ______2______
       /             \
    __3__           __4__
   /     \         /     \
  5       6       7       8
         / \       \
        9  10      11

然后，使用根值 2 作为种子值，使用 add 对此树进行折叠，结果为：2+3+4+5+6+7+8+9+10+11 = 65。

在 Treegami 中，fold 的默认种子值是根节点的值，空树表示没有子节点且节点值为 null。

根据我们在折叠函数中组合当前值和累积值的顺序，我们得到不同的遍历顺序。具体来说，如果我们将当前值添加到累积值的前面，我们得到先序遍历，而如果我们将其添加到累积值的后面，我们得到后序遍历。

一般来说，fold 不需要将结构“折叠”为某种标量值，如整数。我们同样可以将结构折叠为另一种结构。这正是 Treegami 中 map 的工作方式，这意味着 map 通过 fold 来表达。

unfold 相反（或者说是对偶，使用正确的术语）是 fold。它接受一个函数和一个种子值，将种子值“展开”成一个结构，在我们的例子中是一个树。重要的是要理解，展开种子的函数返回一对值：我们树中的一个节点和一个种子值列表，这些种子值将被用于后续的 unfold 迭代，直到返回一个空列表，从而本质上结束迭代。

对于好奇且勇敢的读者：fold 是一种归纳法，而其对偶 unfold 是一种展开法。您可以在论文使用香蕉、透镜、信封和铁丝进行函数式编程中了解更多关于这些术语的信息。

测试

$ vendor/bin/phpunit
$ composer phpcs
$ composer phpstan
$ composer infection

变更日志

点击这里

许可证

麻省理工学院

pwm / treegami

维护者

详细信息

README

目录

要求

安装

用法

工作原理

测试

变更日志

许可证