Реализация карты на бинарном дереве с использованием сгиба - PullRequest
Новая
       56

Реализация карты на бинарном дереве с использованием сгиба

0 голосов
/ 16 февраля 2019

Я борюсь с определением карты над деревом, используя foldBT.Моя идея состоит в том, чтобы преобразовать дерево в список, сопоставить оператора со списком, а затем преобразовать список обратно в дерево.Но это звучит неэффективно и также не использует foldBT ... Я пытался запустить foldBT (*2) Nil (numTree [3,5,7], но ghci сообщил об ошибке.Я не очень понимаю, как работает функция foldBt.Пример был бы великолепен.

data SimpleBT a = Nil | N a (SimpleBT a) (SimpleBT a) deriving (Show, Eq)

foldBT :: (a -> b -> b -> b) -> b -> SimpleBT a -> b
foldBT f e Nil = e
foldBT f e (N a left right) = f a (foldBT f e left) (foldBT f e right)

mapTree :: (a -> b) -> SimpleBT a -> SimpleBT b
mapTree f Nil = Nil
mapTree f (N a left right) = N (f a) (mapTree f left) (mapTree f right)

size :: SimpleBT a -> Int
size Nil = 0
size (N _ left right) = 1 + size left + size right

insert ::  SimpleBT a -> a -> SimpleBT a
insert Nil a = N a Nil Nil
insert (N x left right) a
  | size left <= size right = N x (insert left a) right
  | otherwise = N x left (insert right a)

numTree :: [a] -> SimpleBT a
numTree xs = foldl insert Nil xs

Ответы [ 2 ]

0 голосов
/ 16 февраля 2019

Идея функции foldBT заключается в том, что она принимает аргумент для каждого конструктора вашего типа данных (плюс тот, который содержит весь SimpleBT a, который вы хотите свернуть).Первый тип a -> b -> b -> b соответствует рекурсивному конструктору N и показывает, как объединить значение в узле с результатами сгиба двух поддеревьев в результат всего сгиба.Второй аргумент соответствует конструктору Nil, и поскольку этот конструктор не принимает аргументов, соответствующий аргумент fold является просто константой.

Это абсолютно аналогично сворачиванию списка.Тип списка [a] также имеет 2 конструктора.Один из них берет a и список и добавляет элемент в начало списка: a -> [a] -> [a], это приводит к «функции сгиба» типа a -> b -> b.Другой конструктор, как и в вашем случае, является нулевым (пустой список), поэтому снова соответствует аргументу, тип которого просто b.Следовательно, foldr для списка имеет тип (a -> b -> b) -> b -> [a] -> b.

В этой главе вики-книги Haskell есть большое обсуждение этого, с большим количеством примеров: https://en.wikibooks.org/wiki/Haskell/Other_data_structures

Что касаетсякак построить карту из сгиба, для вашего конкретного типа дерева - учитывая то, что я сказал выше, вам нужно (учитывая функцию отображения f :: a -> a0), нам нужно подумать о том, что это делает с Nil дерево, и что оно делает рекурсивно для деревьев с листом и 2 ветками.Кроме того, поскольку наш тип возврата, конечно, будет другим деревом того же типа, b здесь будет SimpleBT a0.

Для Nil, очевидно, мы хотим, чтобы map оставил его без изменений, поэтомувторой аргумент foldBT будет Nil.А для другого конструктора мы хотим, чтобы map применил базовую функцию к значению на листе, а затем рекурсивно отобразил 2 ветви.Это приводит нас к функции \a left right -> N (f a) (mapTree f left) (mapTree f right).

. Таким образом, мы можем заключить, что функцию карты можно определить следующим образом (спасибо @DanielWagner и @WillemVanOnsen за помощь в исправлении моей первой сломанной версии): 

mapTree :: (a -> b) -> SimpleBT a -> SimpleBT b
mapTree f = foldBT foldFunc Nil
    where foldFunc a l r = N (f a) l r
0 голосов
/ 16 февраля 2019

Давайте выдвинем гипотезу mapTree f = foldBT g e и решим для g и e.Определение foldBT гласит: 

foldBT g e Nil = e

Между тем, из определения mapTree мы получаем: 

mapTree f Nil = Nil

Из нашей гипотезы, что mapTree f = foldBT g e, мы можем преобразоватьвторое уравнение и вставьте его рядом с первым уравнением: 

foldBT g e Nil = Nil
foldBT g e Nil = e

Итак e = Nil.

Давайте сделаем другие пункты сейчас.Определение foldBT гласит: 

foldBT g e (N a left right) = g a (foldBT g e left) (foldBT g e right)

Между тем, определение mapTree гласит: 

mapTree f (N a left right) = N (f a) (mapTree f left) (mapTree f right)

Опять же, используя нашу гипотезу mapTree f = foldBT g e, теперь мы можем переписать этоуравнение, и вставьте его рядом с первым: 

foldBT g e (N a left right) = N (f a) (foldBT g e left) (foldBT g e right)
foldBT g e (N a left right) = g a (foldBT g e left) (foldBT g e right)

Таким образом, g a = N (f a) подтвердит правильность этого уравнения.Записав все это в одном месте, мы получим: 

mapTree f = foldBT g e where
    e = Nil
    g a = N (f a)

Вы можете добавить определения e и g, если хотите;Я бы. 

mapTree f = foldBT (N . f) Nil
...