Treefolding/Treemapping

cata.php

<?php
declare(strict_types=1);

function Node($node, array $subtree = []): array {
    return [
        'node'    => $node,
        'subtree' => $subtree
    ];
}

function mapToTree(array $map): array {
    $mapToTree = function (array $map) use (&$mapToTree): array {
        $tree = [];
        foreach ($map as $k => $v) {
            $tree[] = is_array($v) && count($v) > 0
                ? Node($k, $mapToTree($v))
                : Node($v);
        }
        return $tree;
    };
    return $mapToTree($map)[0];
}

function foldTree(callable $f, array $tree) {
    $foldTree = function (array $tree) use (&$foldTree, $f) {
        return $f($tree['node'], array_map($foldTree, $tree['subtree']));
    };
    return $foldTree($tree);
}

function mapTree(callable $f, array $tree): array {
    return foldTree(function ($x, array $xs) use ($f): array {
        return Node($f($x), $xs);
    }, $tree);
}

$map = [
    'n' => [
        'u' => [
            'd',
            'b',
        ],
        'b',
        't' => [
            'q' => [
                's' => [
                    'n',
                    'p',
                ],
            ],
            'i',
            'j',
        ],
    ],
];

echo foldTree(function ($x, array $xs) {
    return implode($xs) . $x;
}, mapTree(function ($x) { return chr(ord($x) - 1); }, mapToTree($map)));