Попытка версии takeWhile на деревьях в Haskell - PullRequest
Новая
       20

Попытка версии takeWhile на деревьях в Haskell

0 голосов
/ 22 сентября 2018

Учитывая дерево, которое выглядит так: 

data Tree a = Leaf | Node (Tree a) a (Tree a)

И функцию сгиба, которая выглядит следующим образом: 

foldTree :: (b -> a -> b -> b) -> b -> Tree a -> b
foldTree _ b Leaf         = b
foldTree fn b (Node lt x rt) = f (foldTree fn b lt) x (foldTree fn b rt)

Я хочу иметь возможность написать функцию takeWhileTree, которая выглядитнапример: 

treeTakeWhile :: (a -> Bool) -> Tree a -> Tree a

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

Итак, если деревоt = Node (Node Leaf 10 Leaf) 4 (Node Leaf 5 Leaf), затем: 

treeTakeWhile (> 5) T = Leaf
treeTakeWhile (>= 4) T = T
treeTakeWhile (< 5) T = Node Leaf 4 Leaf
treeTakeWHile (< 8) T = Node Leaf 4 (Node Leaf 5 Leaf)

Пока что я, похоже, не могу сформулировать, что передать в foldTree.В определении foldtree функция может быть разбита следующим образом: b, вероятно, является левым поддеревом, a, вероятно, является значением в текущем узле, а b, вероятно, является правым поддеревом.

Следовательно, функция переданаtreeTakeWhile должен быть применен ко всем этим частям узла каким-либо образом, чтобы иметь возможность остановиться, когда операция больше не применяется. 

treeTakeWhile fn = foldTree (\xs x ys -> if y then g else Leaf) Node()
              where g = (lt, x, rt)
                    y = fn (Node lt x rt)

Выше явно неверно, но я не уверен, как выразитьакт применения функции к значению текущего узла, за которым следуют левое дерево и правое дерево.Может ли кто-нибудь указать мне правильное направление?И как фолд сможет создать требуемое дерево?

Редактировать 1:

Хорошо, основываясь на ваших отзывах, я попал в такое место, где я думаю, что я довольно близок кответить, но не могу понять, почему компилятор все еще жалуется: 

treeTakeWhile :: (a -> Bool) -> Tree a -> Tree a
treeTakeWhile c = foldTree f acc
        where acc = Leaf
              f l x r = if c x then Node (f lt) x (f rt) else Leaf

Насколько я могу судить, foldTree сейчас передаются правильные аргументы.И предикат также оценивается по мере необходимости на каждом уровне дерева.Возвращаемое значение также всегда имеет тип Tree.

1 Ответ

0 голосов
/ 22 сентября 2018

Вместо немедленного использования foldTree давайте сначала нацелимся на определение самой функции.

В основном здесь есть три варианта:

  1. дерево - Leaf,независимо от того, что является условием, результатом также является Leaf;
  2. дерево является Node и условие насыщено, тогда мы получаем элемент и рекурсивно на поддеревьях;
  3. дерево это Node и условие не удовлетворено, тогда результатом будет Leaf.

Мы можем закодировать эти правила как: 

treeTakeWhile :: (a -> Bool) -> Tree a -> Tree a
treeTakeWhile c = go
    where go Leaf = Leaf                                -- (1)
          go (Node l x r) | c x = Node (go l) x (go r)  -- (2)
                          | otherwise = Leaf            -- (3)

это затем дает ожидаемые результаты: 

Prelude> treeTakeWhile (>5) t
Leaf
Prelude> treeTakeWhile (>=4) t
Node (Node Leaf 10 Leaf) 4 (Node Leaf 5 Leaf)
Prelude> treeTakeWhile (<5) t
Node Leaf 4 Leaf
Prelude> treeTakeWhile (<8) t
Node Leaf 4 (Node Leaf 5 Leaf)

Перемещение этого к foldTree

Теперь мы стремимся переместить логику в foldTree, мытаким образом можно написать функцию как: 

treeTakeWhile :: (a -> Bool) -> Tree a -> Tree a
treeTakeWhile c = foldTree f x0
    where f tl x tr = -- ...
          x0 = -- ...

x0 - это значение, которое мы должны заполнить для Leaf с, но мы уже знаем, что это: это первое правило (1) итаким образом, мы должны также вернуть Leaf.

Для f нам нужна функция Tree a -> a -> Tree a -> Tree a.Первый операнд tl - это treeTakeWhile левого поддерева (это будет эквивалентно go l в исходной реализации функции), второй параметр x - это значение, закодированное в Node, а последнийпараметр tr является результатом treeTakeWhile во втором поддереве (эквивалентно go r), поэтому: 

treeTakeWhile :: (a -> Bool) -> Tree a -> Tree a
treeTakeWhile c = foldTree f x0
    where f tl x tr = -- ...
          x0 = -- ...

(оставьте это как упражнение).

...