Zipper

Вказівки

Створення застібки для бінарного дерева.

Застібка - це чисто функціональний спосіб орієнтуватися в структурі даних і змінювати її. По суті, вона містить структуру даних і вказівник у цю структуру (який називають фокусом).

Наприклад, для трояндового дерева (де кожен вузол містить значення та масив дочірніх вузлів) застібка може підтримувати такі операції:

• from_tree (отримати застібку з трояндового дерева, фокус стоїть на кореневому вузлі)
• to_tree (отримати трояндове дерево із застібки)
• value (отримати значення вузла у фокусі)
• prev (перемістити фокус на попередній дочірній вузол того самого батьківського вузла, повертає нову застібку)
• next (перемістити фокус на наступний дочірній вузол того самого батьківського вузла, повертає нову застібку)
• up (перемістити фокус на батьківський вузол, повертає нову застібку)
• set_value (встановити значення вузла у фокусі, повертає нову застібку)
• insert_before (вставити нове піддерево перед вузлом у фокусі; воно стає prev вузла у фокусі, повертає нову застібку)
• insert_after (вставити нове піддерево після вузла у фокусі; воно стає next вузла у фокусі, повертає нову застібку)
• delete (видаляє вузол у фокусі та всі піддерева; фокус переходить на вузол next, якщо це можливо, інакше на вузол prev, якщо це можливо, інакше на батьківський вузол, повертає нову застібку)

Існує багато способів виконати цю вправу, але ми підготували її для тих, хто хоче попрактуватися в написанні власних [обробників ability][ability-handler-docs].

Напишіть ability Zipper, який дозволяє переміщатися структурою даних бінарного дерева.

Сам ability Zipper уже визначено, але нам потрібно реалізувати обробник, який дозволить йому переміщатися нашою заданою структурою даних бінарного дерева.

Нехай у нас є таке бінарне дерево. Якщо викликати Zipper.right, Zipper.right, Zipper.up, а потім Zipper.left, ми опинимося у вузлі зі значенням 5.

     1
   /   \
  2     4
 /     /  \
3     5    7

Для цієї вправи, якщо викликати left або right у бінарного дерева, яке не містить лівої чи правої гілки, можна повернути значення в поточному вузлі.

Над чим поміркувати

У чому обробник ability сам схожий на zipper? Чи можна вважати continuation функції вказівником на наступний «вузол» у нашій програмі? Чи могли б ми зберігати минулі виклики continuation у своєму обробнику, щоб мати змогу переміститися «назад» до попереднього стану?

Якими ще структурами даних можна переміщатися в такий спосіб? Чи могли б ми написати Zipper поверх JSON або поверх дерева HTML DOM?