інтуітивність імперативного

[sassa_nf]

Тут хтось поскаржився, що порядок обчислень в Х-і не зрозумілий. Ну, ось вам імперативний варіант, не обляпайтесь:

function walk2(preorder, inorder) {
  let node = {parent: {}};
  while(preorder.length !== 0) {
    if (preorder[preorder.length - 1] === node.parent.value) {
      preorder.pop();
      node.parent.left = node;
      node = node.parent;
      continue;
    }
    node.parent = {value: inorder.pop(), parent: node.parent, right: node};
    node = {parent: node.parent};
  }
  return node;
}

Мені аж цікаво, як я раніше в такому розбирався?

Comments

[nivanych.livejournal.com]

> не обляпайтесь:

Кусаю крупные куски, жЫр во все стороны, вкуснотищщаа!
Ой, обляпался...
;-)

[juan-gandhi.livejournal.com]

Well, weird; first I asked myself if we roll it all back and try to write it immutably, that is, start building the tree starting from leaves... then I figure, it was my solution (big deal, use call stack instead)

[sassa-nf.livejournal.com]

What I find weird is that the immutable solution forces you to look at it inductively. You start expressing yourself in terms of subtrees (how do we know we have the whole left subtree for a node; how do we know we have the whole right subtree), because you can no longer think about "setting" pointers, or tweaking them later.

This imperative piece was obtained to see if we can do the same in reverse.

[juan-gandhi.livejournal.com]

Right. Just all my experience with mutable pointers tells me - it's a hell.

[nponeccop.livejournal.com]

Да даже удаление элемента из середины двунаправленного списка.

[thedeemon.livejournal.com]

То ли дело удаление элемента из середины двунаправленного списка в хаскеле или расте! :)

[juan-gandhi.livejournal.com]

Особенно в условиях "concurrency".

[zeit-raffer.livejournal.com]

Но тут такое дело: этому удалению можно научить любого школьника, если просто заставить его научиться (при наличии достаточного времени или мотивации). А написать диссертацию Криса Окасаки любой школьник не сможет (впрочем, это дискуссионный вопрос).