CODEWITHSUNDEEP
haskell
zoran119
zoran119

Reputation: 11307

Repetition in data constructor

I can define a binary tree data structure:

data Tree a = Leaf | Node a (Tree a) (Tree a)

Now I want to create a tree such that each Node has 10 sub-trees. I could so so by writing out 10 (Tree a)s, but is there a more consise way? I'm thinking type families might help here but I'm not sure.

Upvotes: 2

Views: 127

Answers (1)

user2407038
user2407038

Reputation: 14588

It seems like you want a tree whose branching factor is determined on the type level, and can be any natural number. This is fairly straightforward with GADTs:

data Nat = Z | S Nat 

data Vec (n :: Nat) a where 
  Nil :: Vec 'Z a 
  (:>) :: a -> Vec n a -> Vec ('S n) a 
infixr 5 :> 

data Tree k a = Leaf | Node a (Vec k (Tree k a))

Vec is the standard way to encode a homogenous length-indexed vector with GADTs (found e.g. here). A node in a tree is then an element of type a and a vector of length k, where each element of the vector is a subtree.

Binary trees are simply

type BinaryTree = Tree ('S ('S 'Z))

and constructing is simply

tree = Node 1 (Node 2 (Leaf :> Leaf :> Nil) :> Leaf :> Nil)

the inferred type will be Num a => Tree ('S ('S 'Z)) a.

But if you really need 10 nodes, writing out ten 'S is still too tedious, so you may want to use type literals:

import qualified GHC.TypeLits as TL

...

type family N (n :: TL.Nat) :: Nat where  
  N 0 = 'Z 
  N n = 'S (N (n TL.- 1))

type Tree10 = Tree (N 10)

This not only gives you trees with any branching factor you like, but it allows you to write functions which are polymorphic in the branching factor, and even more, GHC give you all the following for free:

-- With StandaloneDeriving, DeriveFunctor, DeriveFoldable, DeriveTraversable
deriving instance Functor (Vec k) 
deriving instance Foldable (Vec k) 
deriving instance Traversable (Vec k) 

deriving instance Functor (Tree k)
deriving instance Foldable (Tree k) 
deriving instance Traversable (Tree k)

Upvotes: 2

Related Questions