How to find all possible subtrees of a binary tree in Haskell?

Question

I need to find all possible subtrees in a binary tree:

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

and tree:

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

I am new to Haskell and I know that there is no while & frasl; for in Haskell. Haskell is a recursion. My question is: how to get all possible tree subtrees without infinite recursion?

Answer 1

bheklilr gave you an answer to one interpretation of your question, but this is what I will tell you as a beginner who will benefit from the problem:

First, make sure you clearly define what you need to do. I assume you want it to work like tails .

Then think declaratively where your = -sign means "is" and write two statements. The first should read " allSubtrees of the Empty is ... tree" (this is your main example):

 allSubtrees Empty = ... 

Then your recursive case reading " allSubtrees a Node : ...":

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

If you can't wrap yourself around it, just try writing a recursive function that works correctly for Node Empty 1 Empty , and then generalize it.

Answer 2

Uniplate is your friend, here:

 {-# 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

Since a Uniplate demo already exists, here is an implementation using the recursion-schemes library for completeness:

 {-# LANGUAGE DeriveFunctor, TypeFamilies #-} import Data.Functor.Foldable data BinaryT a = Empty | Node (BinaryT a) a (BinaryT a) deriving (Eq, Show) data BinaryTBase ab = BaseEmpty | BaseNode bab deriving (Functor) type instance Base (BinaryT a) = BinaryTBase a instance Foldable (BinaryT b) where project Empty = BaseEmpty project (Node abc) = BaseNode abc instance Unfoldable (BinaryT b) where embed BaseEmpty = Empty embed (BaseNode abc) = Node abc allSubtrees :: BinaryT a -> [BinaryT a] allSubtrees = para phi where phi BaseEmpty = [] phi (BaseNode (l, ll) v (r, rr)) = ll ++ rr ++ [Node rvl] 

The basic functor pattern is large, but relatively unsurprising and can save your efforts in the long run, once per type.

And here is another implementation using the geniplate library:

 {-# 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) 

And here is a shortened version of @bheklilr of a clearly recursive approach, which probably expects from a newbie (I used (++) for symmetry):

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

Note that it contains the root directory, but it does not contain empty subtrees, but it is easily replaced.

I wonder what are the advantages and disadvantages of the various approaches. Is uniplate something more or less type safe than other approaches?

Note that the recursion-schemes approach is concise (if you need many different workarounds for the same type) and flexible (you have full control over the workaround, whether to include empty subtrees, etc.). One of the drawbacks is that the para type and other schemes are too general to allow type inference, so type signature is often required to disambiguate.

geniplate seems less intrusive than uniplate , since there is no need to put deriving clauses.

Answer 4

You can easily use recursion to solve this problem. Probably easier than using loops.

 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

In addition to the nponeccop solution, there is a wide tree walk here (not possible with parametrism, actually requires a joint recursion):

 {-# 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 lvr):t) = Cons n (t++(l:[r])) main = print $ allSubtrees $ Node (Node Empty "a" Empty) "b" (Node (Node Empty "c" Empty) "d" Empty)