Ломать после нахождения -ю элемента в заказовМои обходе с использованием более высокого порядка обхода функции

Question

У меня есть следующий код, чтобы сделать заказовМои обхода бинарного дерева:

data BinaryTree a = 
    Node a (BinaryTree a) (BinaryTree a) 
    | Leaf 
    deriving (Show) 

inorder :: (a -> b -> b) -> b -> BinaryTree a -> b 
inorder f acc tree = go tree acc 
    where go Leaf z = z 
     go (Node v l r) z = (go r . f v . go l) z 

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

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

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

Есть ли способ сломать после k итераций?

Answer 1

Я заметил, что результаты рекурсивного вызова go в левом и правом поддеревьях недоступны для f; следовательно, вне зависимости от того, что делает f, он не может игнорировать результаты рекурсивных вызовов. Поэтому я считаю, что inorder, как написано, будет всегда ходить по всему дереву. (Редактирование: В обзоре это утверждение может быть немного сильным, кажется, что f может иметь возможность игнорировать левые поддеревья. Но точка в основном стоит, поэтому нет причин поднять левые поддеревья над правыми поддеревьями.)

Лучшим решением является предоставление рекурсивных вызовов f. Например:

anyOldOrder :: (a -> b -> b -> b) -> b -> BinaryTree a -> b 
anyOldOrder f z = go where 
    go Leaf = z 
    go (Node v l r) = f v (go l) (go r) 

Теперь, когда мы пишем

flatten = anyOldOrder (\v ls rs -> ls ++ [v] ++ rs) [] 

мы обнаружим, что flatten достаточно ленив:

> take 3 (flatten (Node 'c' (Node 'b' (Node 'a' Leaf Leaf) Leaf) undefined)) 
"abc" 

(undefined используется для предоставления доказательств того, что эта часть дерево никогда не проверяется во время обхода.) Поэтому мы можем написать

findK k = take 1 . reverse . take k . flatten 

который будет правильно закорочен. Вы можете сделать flatten немного более эффективным со стандартной difference list техники:

flatten' t = anyOldOrder (\v l r -> l . (v:) . r) id t [] 

Просто для удовольствия, я также хочу, чтобы показать, как реализовать эту функцию без использования списка аккумулятора. Вместо этого мы создадим вычисление с учётом состояния, которое перейдет по «интересной» части дерева, остановившись, когда достигнет k-го элемента. Расчеты с состоянием выглядят так:

import Control.Applicative 
import Control.Monad.State 
import Control.Monad.Trans.Maybe 

kthElem k v l r = l <|> do 
    i <- get 
    if i == k 
     then return v 
     else put (i+1) >> r 

Выглядит довольно просто, эй?Теперь наша findK функции откупа к kthElem, затем сделать некоторое NewType развёрток:

findK' k = (`evalState` 1) . runMaybeT . anyOldOrder (kthElem 3) empty 

Мы можем подтвердить, что он по-прежнему ленивый по желанию:

> findK' 3 $ Node 'c' (Node 'b' (Node 'a' Leaf Leaf) Leaf) undefined 
Just 'c' 

Answer 2

Есть (по крайней мере?) Два важные обобщения понятия складной список. Первое, более мощное, понятие - это катамаморфизм . Ответ anyOldOrder Даниэля Вагнера следует этой схеме.

Но для вашей конкретной проблемы понятие катаморфизма - это немного больше энергии, чем вам нужно. Второе, более слабое, понятие относится к контейнеру Foldable. Foldable выражает идею контейнера, элементы которого могут быть выровнены вместе, используя операцию произвольного Monoid. Вот такая уловка:

{-# LANGUAGE DeriveFoldable #-} 

-- Note that for this trick only I've 
-- switched the order of the Node fields. 
data BinaryTree a = 
    Node (BinaryTree a) a (BinaryTree a) 
    | Leaf 
    deriving (Show, Foldable) 

index :: [a] -> Int -> Maybe a 
[] `index` _ = Nothing 
(x : _) `index` 0 = Just x 
(_ : xs) `index` i = xs `index` (i - 1) 

(!?) :: Foldable f => Int -> f a -> Maybe a 
xs !? i = toList xs `index` i 

Тогда вы можете просто использовать !? индексировать в дереве!

---

Этот трюк мило, и на самом деле, вытекающих Foldable это огромное удобство, но это не поможет вам понять что-либо. Начну с того, что вы можете точно и эффективно определить treeToList, не используя Foldable.

treeToList :: BinaryTree a -> [a] 
treeToList t = treeToListThen t [] 

Магия находится в функции treeToListThen. treeToListThen t more преобразует t в список и добавляет список more в конец результата. Это небольшое обобщение оказывается тем, что требуется для эффективного преобразования в список.

treeToListThen :: BinaryTree a -> [a] -> [a] 
treeToListThen Leaf more = more 
treeToListThen (Node v l r) more = 
    treeToListThen l $ v : treeToListThen r more 

Вместо получения заказовМои обход левого поддерева, а затем добавляя все остальное, мы говорим левый обход какой наклеить на конце, когда это сделано! Это позволяет избежать потенциально серьезной неэффективности повторной конкатенации списков, которая может превратить вещи O (n^2) в плохих случаях.

Возвращаясь к Foldable понятия, превращая вещи в списки является частным случаем foldr:

toList = foldr (:) [] 

Так как мы можем реализовать foldr для деревьев? Он заканчивает тем, что несколько похож на то, что мы сделали с toList:

foldrTree :: (a -> b -> b) -> b -> BinaryTree a -> b 
foldrTree _ n Leaf = n 
foldrTree c n (Node v l r) = foldrTree c rest l 
    where 
    rest = v `c` foldrTree c n r 

То есть, когда мы идем вниз по левой стороне, мы говорим, что когда это будет сделано, он должен иметь дело с текущим узлом и его правом ребенка ,

В настоящее время foldr не является наиболее фундаментальной операцией Foldable; что на самом деле

foldMap :: (Foldable f, Monoid m) 
     => (a -> m) -> f a -> m 

Это можно реализовать с помощью foldrfoldMap, в некоторой степени сложной манере, используя своеобразный Monoid.Я не хочу перегружать вас данными об этом прямо сейчас, если вы не спросите (но вы должны посмотреть определение по умолчанию foldr в Data.Foldable). Вместо этого, я покажу, как foldMap можно определить с помощью Daniel Вагнер anyOldOrder:

instance Foldable BinaryTree where 
    foldMap f = anyOldOrder bin mempty where 
    bin lres v rres = lres <> f v <> rres