Циркулярные программы
Вчерашняя лекция Конора МакБрайда взорвала мозги аудитории, но тем не менее я получил массу удовольствия. Приведу один пример циркулярной программы продемонстрированный вчера.
Задачка. Имеется бинарное дерево, у которого лейблы находятся только в листьях и имеют целочисленный тип. Надо написать программу, которая создаст новое дерево, идентичное по своей структуре исходному, заменив все метки дерева на минимальное число из меток старого дерева.Например:
Казалось бы все просто, обойти дерево два раза, сначала найти минимальный элемент, а затем создать дерево. Но задача как раз состоит в том чтобы сделать это за один обход! Нереально? Нет, очень даже реально! Нас спасет Хаскелл и его ленивые вычисления.
Конор делал доклад без слайдов, всё писал на доске, за что ему огромное спасибо, я успевал всё переварить и усвоить :) Придя на рабочее место, по памяти написал программку и о чудо, она работает! Хотя пришлось поломать голову КАК она работает.
Вот собсно сама программа:
data LT = Leaf Int | Node LT LT
repMin :: LT -> LT
repMin t = t' where
(t', m) = help t m where
help (Leaf x) m = (Leaf m, x)
help (Node l r) m = (Node l' r', min i j) where
(l', i) = help l m
(r', j) = help r m
Сначала идет объявление структуры данных (т.е. дерева). Далее тип функции repMin, из дерева получаем дерево.
Ну и следовательно объявление самой функции. Тут самое интересное. Я сначала пытался представить в уме как это работает на примере дерева с тремя листьями, показанного выше. Запутавшись, решил начать с простейшего, т.е. с дерева с одной единственной вершиной. Ясно, что функция будет возвращать дерево, идентичное изначальному, но КАК. Видно, что вспомогательная функция help принимает два аргумента, дерево и нечто m, что есть минимальное число в дереве. Но как, ведь изначально мы никакого m не знаем. Тем не менее это не мешает Хаскеллу вызвать функцию со знаком вопроса вместо значения m. Итак, имея дерево с одним листом имеем дело только с вариантом help (Leaf x) m.
Запускаем программу:
> repMin (Leaf 1)
Что происходит: где-то в недрах интерпретатора идет вызов help (Leaf 1) m=?, далее, внутри тела к x присваивается 1 и возвращается пара (Leaf m=?, 1). На выходе пара матчится с желаемым результатом (t', m) = (Leaf m=?, 1), из этого следует, что m=1 и соответственно получаем дерево t' = Leaf 1. Круто? О да! :D
Второй случай (help (Node l r) m) я расписывать не буду т.к. поняв первый, разобраться во втором труда не составит.
з.ы. есть и более сложные примеры с которыми я по мере сил и желания возможно вас ознакомлю. конечно если есть интерес...
з.з.ы. кто будет пробовать запускать прогу должен не забыть добавить возможность вывода дерева на экран, напр сл образом:
instance Show LT where
show (Leaf x) = show x
show (Node l r) = "[" ++ show l ++ ", " ++ show r ++ "]"
Задачка. Имеется бинарное дерево, у которого лейблы находятся только в листьях и имеют целочисленный тип. Надо написать программу, которая создаст новое дерево, идентичное по своей структуре исходному, заменив все метки дерева на минимальное число из меток старого дерева.Например:
Казалось бы все просто, обойти дерево два раза, сначала найти минимальный элемент, а затем создать дерево. Но задача как раз состоит в том чтобы сделать это за один обход! Нереально? Нет, очень даже реально! Нас спасет Хаскелл и его ленивые вычисления.
Конор делал доклад без слайдов, всё писал на доске, за что ему огромное спасибо, я успевал всё переварить и усвоить :) Придя на рабочее место, по памяти написал программку и о чудо, она работает! Хотя пришлось поломать голову КАК она работает.
Вот собсно сама программа:
data LT = Leaf Int | Node LT LT
repMin :: LT -> LT
repMin t = t' where
(t', m) = help t m where
help (Leaf x) m = (Leaf m, x)
help (Node l r) m = (Node l' r', min i j) where
(l', i) = help l m
(r', j) = help r m
Сначала идет объявление структуры данных (т.е. дерева). Далее тип функции repMin, из дерева получаем дерево.
Ну и следовательно объявление самой функции. Тут самое интересное. Я сначала пытался представить в уме как это работает на примере дерева с тремя листьями, показанного выше. Запутавшись, решил начать с простейшего, т.е. с дерева с одной единственной вершиной. Ясно, что функция будет возвращать дерево, идентичное изначальному, но КАК. Видно, что вспомогательная функция help принимает два аргумента, дерево и нечто m, что есть минимальное число в дереве. Но как, ведь изначально мы никакого m не знаем. Тем не менее это не мешает Хаскеллу вызвать функцию со знаком вопроса вместо значения m. Итак, имея дерево с одним листом имеем дело только с вариантом help (Leaf x) m.
Запускаем программу:
> repMin (Leaf 1)
Что происходит: где-то в недрах интерпретатора идет вызов help (Leaf 1) m=?, далее, внутри тела к x присваивается 1 и возвращается пара (Leaf m=?, 1). На выходе пара матчится с желаемым результатом (t', m) = (Leaf m=?, 1), из этого следует, что m=1 и соответственно получаем дерево t' = Leaf 1. Круто? О да! :D
Второй случай (help (Node l r) m) я расписывать не буду т.к. поняв первый, разобраться во втором труда не составит.
з.ы. есть и более сложные примеры с которыми я по мере сил и желания возможно вас ознакомлю. конечно если есть интерес...
з.з.ы. кто будет пробовать запускать прогу должен не забыть добавить возможность вывода дерева на экран, напр сл образом:
instance Show LT where
show (Leaf x) = show x
show (Node l r) = "[" ++ show l ++ ", " ++ show r ++ "]"