Search code examples
haskelltypesalgebraic-data-typesrecursive-datastructures

Haskell - Algebraic data types that use recursion?

I've followed a guide to creating a binary search tree which uses the following datatype:

data BinarySearchTree a = EmptyTree | TreeNode a (BinarySearchTree a) (BinarySearchTree a) deriving (Show, Read, Eq)

Am I correct in saying 'TreeNode' is using recursion, i.e. creates 2 elements of its own data type '(BinarySearchTree a) (BinarySearchTree a)'?

I've never seen a datatype like this, any brief explanation would be great!

Solution

  • Yes, this is a recursive data type.

    I recommend a relevant chapter in Learn You A Haskell For Great Good - it is very beginner-friendly. It describes your exact case, too:

    Here's what we're going to say: a tree is either an empty tree or it's an element that contains some value and two trees. Sounds like a perfect fit for an algebraic data type!