Haskell: return a list of all substrees in Binary Tree. Is my code correct?

Question

So I am trying to implement a functoin in Haskell that accepts a Binary Tree and returns a list of all subtrees where order and repetition does not matter but all substrees must be present at least once. Here is my code:

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

subtrees :: BinTree a -> [BinTree a]
subtrees Empty = [Empty]
subtrees (Node tL x tR) = [Node tL x tR] ++ subtrees tL ++ subtrees tR

Here is my data set

(Node (Node (Node (Node Empty 1 Empty) 1 Empty) 3 Empty) 4 (Node Empty 2 Empty))

Here is my result

[Node (Node (Node (Node Empty 1 Empty) 1 Empty) 3 Empty) 4 (Node Empty 2 Empty),
Node (Node (Node Empty 1 Empty) 1 Empty) 3 Empty,Node (Node Empty 1 Empty) 1 Emp
ty,Node Empty 1 Empty,Node Empty 2 Empty]

For some reason I am somewhat doubtful of this implementation and I would appreciate any feedback! Thanks!

Answer 1

Looks ok. Only answer the question: what is a list of all subtrees of a Empty tree?

Answer 2

The best way to test something like this, in my opinion, is to think of properties that you expect your function to satisfy, and then write some QuickCheck tests to try them out. The best thing about QuickCheck is that if it finds a problem, it will try to tell you the simplest possible case that fails! So let's begin...

{-# LANGUAGE FlexibleInstances #-}

import Test.QuickCheck
import Control.Applicative

What's a good property to test? Well, if we have two trees, t1 and t2, and combine them with a new node, then calling subtree on the combined tree should give us a list that includes subtree t1, subtree t2, plus the entire tree. The node type doesn't affect the logic, so I chose Char. You can probably think of a better name for this property.

prop_combining_works :: BinTree Char -> Char -> BinTree Char -> Property
prop_combining_works t1 x t2 =
  property $ subtrees t == t : subtrees t1 ++ subtrees t2
  where t = Node t1 x t2

NOTE: I didn't expect this to work without sorting the results of subtree in some way, but by happy accident, it does. But that may change, depending on how you decide to return for subtree Empty! Also, you may need to eliminate duplicates in expression to the right of ==.

Next, we need a way to generate random trees to test with. The code below may look complicated, but what it's saying is that test data for the BinTree type can be either Empty, or a Node build up with two arbitrarily chosen subtrees and an arbitrarily chosen Char.

instance Arbitrary (BinTree Char) where
  arbitrary = do
    oneof [return Empty, Node <$> arbitrary <*> arbitrary <*> arbitrary]

Add this to your code, and run QuickCheck:

λ> quickCheck prop_combining_works
Loading package QuickCheck-2.6 ... linking ... done.
+++ OK, passed 100 tests.

Now you can think of other properties to test.