Как найти все возможные поддеревья двоичного дерева в Haskell?

Question

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

allSubtrees :: BinaryT a -> [BinaryT a]
allSubtrees = undefined

и дерево это:

data BinaryT a =
    Empty
  | Node (BinaryT a) a (BinaryT a)
  deriving (Eq, Show)

Я новичок в Хаскеле и знаю, что нет while / for Цикл в Хаскеле. Хаскелл это все о рекурсии. У меня вопрос, как получить все возможные поддеревья дерева без бесконечной рекурсии?

Answer 1

bheklilr дал вам ответ на одно из толкований вашего вопроса, но это то, что я бы сказал вам, как новичку, который извлек бы пользу из самостоятельного решения проблемы:

Сначала убедитесь, что вы четко определили, что вы хотите, чтобы ваша функция выполняла. Я предполагаю, что вы хотите, чтобы это работало как tails,

Тогда думай декларативно, где твой = -sign означает "есть", и написать два утверждения. Первый должен читать allSubtrees из Empty дерево это..." (это ваш базовый случай):

allSubtrees Empty = ...

Тогда ваш рекурсивный случай, читая allSubtrees из Node является...":

allSubtrees (Node l a r) = ...something combining the subTrees of l and the subtrees of r

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

Answer 2

Uniplate твой друг, здесь:

{-# LANGUAGE DeriveDataTypeable #-}

import Data.Generics.Uniplate.Data (universe)
import Data.Data (Data)
import Data.Typeable (Typeable)

data BinaryT a =
   Empty
   | Node (BinaryT a) a (BinaryT a)
deriving (Eq, Show, Typeable, Data)


allSubtrees :: (Data a, Typeable a) => BinaryT a -> [BinaryT a]
allSubtrees = universe

Answer 3

Так как демонстрация Uniplate уже есть, вот реализация, использующая recursion-schemes ради полноты библиотеки:

{-# LANGUAGE DeriveFunctor, TypeFamilies #-}
import Data.Functor.Foldable

data BinaryT a 
    = Empty
    | Node (BinaryT a) a (BinaryT a)
    deriving (Eq, Show)

data BinaryTBase a b 
    = BaseEmpty 
    | BaseNode b a b
    deriving (Functor)

type instance Base (BinaryT a) = BinaryTBase a

instance Foldable (BinaryT b) where
    project Empty = BaseEmpty
    project (Node a b c) = BaseNode a b c 

instance Unfoldable (BinaryT b) where
    embed BaseEmpty = Empty
    embed (BaseNode a b c) = Node a b c 

allSubtrees :: BinaryT a -> [BinaryT a]     
allSubtrees = para phi where
    phi BaseEmpty = []
    phi (BaseNode (l, ll) v (r, rr)) = ll ++ rr ++ [Node r v l] 

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

А вот еще одна реализация, использующая geniplate библиотека:

{-# LANGUAGE TemplateHaskell #-}
import Data.Generics.Geniplate

data BinaryT a =
    Empty
  | Node (BinaryT a) a (BinaryT a)
  deriving (Eq, Show)

allSubTrees :: BinaryT a -> [BinaryT a]
allSubTrees = $(genUniverseBi 'allSubTrees)

А вот сокращенная версия явно рекурсивного подхода @bheklilr, который, вероятно, ожидается от новичка (я использовал (++) для симметрии):

allSubTrees3 :: BinaryT a -> [BinaryT a]
allSubTrees3 Empty = []
allSubTrees3 this @ (Node left _ right) = [this] ++ leftSubs ++ rightSubs where
    leftSubs = allSubTrees3 left
    rightSubs = allSubTrees3 right

Обратите внимание, что он перечисляет корень, но не перечисляет пустые поддеревья, но его легко изменить.

Интересно, каковы преимущества и недостатки разных подходов. Является uniplate как-то более-менее безопасно, чем другие подходы?

Обратите внимание, что recursion-schemes подход является одновременно лаконичным (если вам нужно много разных обходов для одного типа) и гибким (у вас есть полный контроль над порядком обхода, будь то включение пустых поддеревьев и т. д.). Одним из недостатков является тот тип para и другие схемы слишком общие, чтобы разрешить вывод типа, поэтому для устранения неоднозначности часто требуется сигнатура типа.

geniplate кажется менее навязчивым, чем uniplate, так как нет необходимости ставить deriving статьи.

Answer 4

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

allSubTrees :: BinaryT a -> [BinaryT a]
allSubTrees Empty = []
allSubTrees (Node Empty n Empty) = []
allSubTrees (Node Empty n right) = right : allSubTrees right
allSubTrees (Node left n Empty) = left : allSubTrees left
allSubTrees (Node left n right) = left : right : leftSubs ++ rightSubs
    where
        leftSubs = allSubTrees left
        rightSubs = allSubTrees right

Answer 5

В дополнение к решению nponeccop, здесь идет обход дерева в ширину (это невозможно при параморфизме; на самом деле требуется совместная рекурсия):

{-# LANGUAGE DeriveFunctor, TypeFamilies #-}
import Data.Functor.Foldable

data BinaryT a 
    = Empty
    | Node (BinaryT a) a (BinaryT a)
    deriving (Eq, Show)

allSubtrees :: BinaryT a -> [BinaryT a]
allSubtrees t = ana phi [t] where
    phi [] = Nil
    phi (Empty:t) = Cons Empty t
    phi (n@(Node l v r):t) = Cons n (t++(l:[r]))

main = print $ allSubtrees $ 
       Node (Node Empty "a" Empty) "b" (Node (Node Empty "c" Empty) "d" Empty)