Как правильно отобразить дерево в стеке? - PullRequest
Новая
       34

Как правильно отобразить дерево в стеке?

2 голосов
/ 01 мая 2019

Существуют разные способы рекурсивного сопоставления дерева: 

const reduceTree = (f, node) => {
  const go = ([x, xs]) => f(x, xs.map(go));
  return go(node);
};

const mapTree = (f, node) =>
  reduceTree((x, xs) => Node_(f(x), xs), node);

const Node_ = (x, xs) => ([x, xs]);
const Node = (x, ...xs) => ([x, xs]);

const tree = Node(1,
  Node(2,
    Node(3),
    Node(4,
      Node(5))),
  Node(6),
  Node(7,
    Node(8),
    Node(9),
    Node(10),
    Node(11)));

console.log(
  mapTree(x => 2 * x, tree));

На самом деле это элегантное решение, но оно небезопасно. Поскольку рекурсивный вызов (xs.map(go)) не находится в хвостовой позиции, я не могу вернуться к батуту, и мне не кажется тривиальным преобразовать алгоритм в хвостовую рекурсивную форму.

Обычный способ сделать это, вероятно, - преобразование CPS, которое запутывает вычисления. Может быть, есть другой способ обеспечения безопасности стека - например, с помощью генератора? Существуют ли общие правила для такого преобразования, которые могут применяться почти механическим образом?

Меня в первую очередь интересует процесс этого преобразования, а не конечный результат.

1 Ответ

1 голос
/ 01 мая 2019

Начиная с правильно сформированной взаимно рекурсивной пары - 

// map :: (a -> b, Tree a) -> Tree b
const map = (f, [ v, children ]) =>
  Node (f (v), ...mapAll (f, children))

// mapAll :: (a -> b, [ Tree a ]) -> [ Tree b ]
const mapAll = (f, nodes = []) =>
  nodes .map (n => map (f, n))

Сначала мы удаляем нетерпеливое Array.prototype.map, которое не может допустить форму хвоста - 

const map = (f, [ v, children ]) =>
  Node (f (v), ...mapAll (f, children))

const mapAll = (f, [ node, ...more ]) =>
  node === undefined
    ? []
    : [ map (f, node), ...mapAll (f, more) ]

Затем добавляемпараметр для преобразования CPS - 

const identity = x =>
  x

const map = (f, [ v, children ], k = identity) =>
  mapAll (f, children, newChilds =>        // tail
    k (Node (f (v), ...newChilds)))        // tail

const mapAll = (f, [ node, ...more ], k = identity) =>
  node === undefined
    ? k ([])                               // tail
    : map (f, node, newNode =>             // tail
        mapAll (f, more, moreChilds =>     // tail
          k ([ newNode, ...moreChilds ]))) // tail

Проверьте результаты в своем браузере ниже 

const Node = (x, ...xs) =>
  [ x, xs ]

const identity = x =>
  x

const map = (f, [ v, children ], k = identity) =>
  mapAll (f, children, newChilds =>
    k (Node (f (v), ...newChilds)))
  
const mapAll  = (f, [ node, ...more ], k = identity) =>
  node === undefined
    ? k ([])
    : map (f, node, newNode =>
        mapAll (f, more, moreChilds =>
          k ([ newNode, ...moreChilds ])))

const tree = 
  Node
    ( 1
    , Node
        ( 2
        , Node (3)
        , Node
            ( 4
            , Node (5)
            )
        )
    , Node (6)
    , Node
        ( 7
        , Node (8)
        , Node (9)
        , Node (10)
        , Node (11)
        )
    )

console.log (map (x => x * 10, tree))

Обратите внимание, что CPS сама по себе не делает программу безопасной для стека.Это просто форма, необходимая для размещения кода на батуте по вашему выбору.

...