Алгебра систем типов - использование дифференцирования

Question

Я помню веб-страницу, описывающую интересные приемы в связи с некоторыми задачами функционального программирования.Проблема в том, что я не могу вспомнить, что это было.

В качестве примера у него был узел двоичного дерева (Tree left, Tree right, Data d), который можно описать как Tree*Tree*Data или Tree^2*Data.Затем при выводе, например, по Tree, мы получаем 2*Tree*Data.

Не могли бы вы указать мне, для чего это используется?

Answer 1

Звучит как Молния .

Подводя итог: мантра для такого рода вещей заключается в том, что "производная типа - это контекст с одной дырой".Идея заключается в том, что если вы хотите представить бинарное дерево с одним местом, куда вы хотели бы выполнить вставку, то структура данных для этого - это точно путь от дыры до корня дерева и на каждом восходящем узле.Вы должны помнить, пришли ли вы слева или справа, а также данные в этом узле, а также поддерево, из которого вы не пришли.ну это точно кортеж из 2 (он же слева / справа) * Data * Tree.