Построение списка всех ветвей в дереве

Question

Мне нужно, чтобы функция возвращала все возможные ветви дерева. с помощью этой формы:

data Tree a = EmptyT | NodeT a ( Tree a ) ( Tree a ) deriving (Show)

everyBranch :: Tree a -> [[a]]

Я не уверен, как подойти к этому ... xD Я все еще новичок в Хаскеле.

Допустим, у меня есть:

            1
           / \
          2   3
         /\  / \
        4  5 7  8

Я хочу получить: [[1,2,4], [1,2,5], [1,3,8], [1,3,7]]

Answer 1

Мы будем использовать рекурсивный подход. Начнем с грубого скелета:

everyBranch :: Tree a -> [[a]]
everyBranch EmptyT = _something
everyBranch (NodeT v (Tree l) (Tree r)) = _somethingElse

Теперь мы заполним отверстия. (Этот синтаксис известен как «типизированные дыры»: если вы запустите вышеупомянутую программу через GHC, он выдаст вам сообщение об ошибке с типом значения, которое должно быть в дыре.) Теперь я не уверен насчет Первый случай: в зависимости от ваших потребностей, это может быть [] (без ветвей) или [[]] (одна ветка без элементов), поэтому мы вернемся к этому позже. Во втором случае нам нужен способ построить список ветвей с учетом значения v и поддеревьев l eft и r ight. Как мы это делаем? Мы рекурсивно найдем каждую ветвь в l eft-дереве и каждую ветвь в r ight-дереве, а затем добавим v к обоим:

everyBranch :: Tree a -> [[a]]
everyBranch EmptyT = _something
everyBranch (NodeT v l r) = map (v:) $ everyBranch l ++ everyBranch r

Теперь вернемся к EmptyT. Рассмотрим очень простое дерево: NodeT 1 EmptyT EmptyT. В этом случае everyBranch должно вернуть [[1]]. Давайте вызовем everyBranch «вручную» для этого дерева:

(я использую └→ для обозначения «вычислить подвыражение рекурсивно», а => означает «выражение оценивается как»)

everyBranch (NodeT 1 EmptyT EmptyT)
=> map (1:) $ everyBranch EmptyT ++ everyBranch EmptyT
   └→ everyBranch EmptyT
      => _something
=> map (1:) $ _something ++ _something

Итак, мы хотим, чтобы map (1:) $ _something ++ _something было равно [[1]]. Что такое _something? Что ж, получается, что если _something равно [], то map (1:) $ [] ++ [] равно [], а это не то, что мы хотим. С другой стороны, если _something равно [[]], то map (1:) $ [[]] ++ [[]] равно [[1], [1]], что тоже не то, что нам нужно. Похоже, нам нужен немного другой подход. Что мы сделаем, мы добавим еще один случай специально для такого рода деревьев:

everyBranch :: Tree a -> [[a]]
everyBranch EmptyT = _something
everyBranch (NodeT v EmptyT EmptyT) = [[v]]
everyBranch (NodeT v l r) = map (v:) $ everyBranch l ++ everyBranch r

Теперь, если мы немного протестируем это (хотя и используем некоторое случайное значение для _something, чтобы не дать нам ошибок), мы обнаружим, что оно работает для всех двоичных деревьев. Как уже упоминалось, нам все еще нужно выяснить это значение _something. Это значение будет иметь значение только в двух случаях: пустые деревья (в этом случае оно будет совпадать с EmptyT) и деревья только с одним поддеревом (в этом случае l или r будет соответствовать EmptyT). Я оставлю это в качестве упражнения для вас, чтобы определить, какую ценность ставить, как это повлияет на результат и почему это так влияет.

Answer 2

Мы можем получить и использовать Foldable, чтобы сложить в специальный моноид для выполнения работы:

data Tree a = EmptyT
            | NodeT a ( Tree a ) ( Tree a )
            deriving (Show, Functor, Foldable)

data T a = T a                    -- tip
         | N [[a]]                -- node
         | TN (a,[[a]])           -- tip  <> node
         | NN ([[a]],[[a]])       -- node <> node
         deriving Show

instance Monoid (T a) where
    mempty = N []           -- (tip <> node <> node)  is what we actually want
    mappend (T a)  (N as) = TN (a,as)           -- tip  <> node
    mappend (N as) (N bs) = NN (as,bs)          -- node <> node

    mappend (T a) (NN ([],[])) = N ([[a]])      -- tip  <> (node <> node)
    mappend (T a) (NN (as,bs)) = N (map (a:) as ++ map (a:) bs) 

    mappend (TN (a,[])) (N []) = N ([[a]])      -- (tip <> node) <> node
    mappend (TN (a,as)) (N bs) = N (map (a:) as ++ map (a:) bs)

allPaths :: Tree a -> [[a]]
allPaths (foldMap T -> N ps) = ps

В определении функции allPaths используется ViewPatterns,Тестирование,

> allPaths $ NodeT 1 (NodeT 2 (NodeT 3 EmptyT EmptyT) EmptyT) 
                     (NodeT 5 EmptyT EmptyT)
[[1,2,3],[1,5]]

> allPaths $ NodeT 1 (NodeT 2 (NodeT 3 EmptyT EmptyT) (NodeT 4 EmptyT EmptyT)) 
                     (NodeT 5 EmptyT EmptyT)
[[1,2,3],[1,2,4],[1,5]]

(tip <> node <> node) - это то, что мы действительно хотим, но <> является двоичным, и мы не знаем (и не должны полагаться на это, если бы мы это сделали) фактический порядок, в которомчасти будут объединены в единое целое по производному определению foldMap,

foldMap T EmptyT          ==  N []
foldMap T (NodeT a lt rt) ==  T a <> foldMap T lt <> foldMap T rt
                              -- but in what order? 

Таким образом, мы «подделываем» его, задерживая фактическую комбинацию, пока все три части не станут доступны.

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

Так что, возможно, это не так здорово.Я все равно выложу, как контрапункт.