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 the tree is:

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

I'm new to Haskell and I know there's no while ⁄ for loop in Haskell. Haskell is all about recursion. My question is, how to get all the possible subtrees of a tree without infinite recursion?

Answer 1

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

First make sure you've clearly defined what you want your function to do. I'm assuming 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 tree is ..." (this is your base case):

allSubtrees Empty = ...

Then your recursive case, reading "allSubtrees of a Node is ...":

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

If you can't wrap your head around this, try just 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