2

I'm very new to haskell and need to use a specific data type for a problem I am working on.

data Tree a = Leaf a | Node [Tree a]
deriving (Show, Eq)

So when I make an instance of this e.g Node[Leaf 1, Leaf2, Leaf 3] how do I access these? It won't let me use head or tail or indexing with !! .

Ciarán Martin
  • 21
  • 2
  • A note on terminology. What you have defined is a "type constuctor" (`Tree`) which can be provided with a type argument to produce a type (ex `Tree Int`) and a couple "data constructors" (`Leaf` and `Node`) which can be provided value argument to produce a value (not an "instance"). See, for example, [this prior question and answer](https://stackoverflow.com/questions/18204308/haskell-type-vs-data-constructor). – Thomas M. DuBuisson Jan 03 '18 at 22:06
  • That's good, since partial functions as `head,tail,!!` should be avoided as much as possible, using pattern matching instead. – chi Jan 03 '18 at 23:20

1 Answers1

4

You perform pattern matching. For example if you want the first child, you can use:

firstChild :: Tree a -> Maybe (Tree a)
firstChild (Node (h:_)) = Just h
firstChild _ = Nothing

Here we wrap the answer in a Maybe type, since it is possible that we process a Leaf x or a Node [], such that there is no first child.

Or we can for instance obtain the i-th item with:

iThChild :: Int -> Tree a -> Tree a
iThChild i (Node cs) = cs !! i

So here we unwrap the Node constructor, obtain the list of children cs, and then perform cs !! i to obtain the i-th child. Note however that (!!) :: [a] -> Int -> a is usually a bit of an anti-pattern: it is unsafe, since we have no guarantees that the list contains enough elements, and using length is an anti-pattern as well, since the list can have infinite length, so we can no do such bound check.

Usually if one writes algorithms in Haskell, one tends to make use of linear access, and write total functions: functions that always return something.

Willem Van Onsem
  • 443,496
  • 30
  • 428
  • 555