CODEWITHSUNDEEP
haskellpattern-matchingsyntax-errorbinary-tree
Jung
Jung

Reputation: 139

Function to measure size of a binary tree

When i tried to size (N a (left a) (right a)) instead of size (N a left right), i was told by ghci that this line conflicts when the definition. I am not sure why because in my data signature, it is N a (Tree a) (Tree a). size is a function to count the number of nodes in a bin tree. 

data Tree a = Nil | N a (Tree a) (Tree a) deriving (Show, Read, Eq)


size :: Tree Int -> Int
size Nil = 0
size (N _ left right) = 1 + size left + size right

Upvotes: 1

Views: 184

Answers (2)

Greg Bacon
Greg Bacon

Reputation: 139711

To help you see what’s going on, you could write your match internal nodes to name the left and right subtrees and their respective values with

size (N _ left@(N a _ _) right@(N b _ _)) = 1 + size left + size right

Section 3.17.1 “Patterns” describes what is happening with the at signs, which allow the programmer to name the left and right subtrees.

Patterns of the form var@pat are called as-patterns, and allow one to use var as a name for the value being matched by pat.

The broad approach is inelegant for a number of reasons.

  1. left and right are already constrained to be of type Tree because of the declaration of the Tree algebraic datatype.
  2. Much worse, you’d also have to define the other three cases of size for either one or two Nil arguments.

Section 3.17.2 Informal Semantics of Pattern Matching outlines the cases for how the language handles patterns. Of especial note to you in the context of this question are

1. Matching the pattern var against a value v always succeeds and binds var to v.

and

5. Matching the pattern con pat1 … patn against a value, where con is a constructor defined by data, depends on the value:

  • If the value is of the form con v1 … vn, sub-patterns are matched left-to-right against the components of the data value; if all matches succeed, the overall match succeeds; the first to fail or diverge causes the overall match to fail or diverge, respectively.
  • If the value is of the form con′ v1 … vn, where con is a different constructor to con′, the match fails.
  • If the value is ⊥, the match diverges.

The first is how you want to do it and how you wrote it in your question, by binding the left and right subtree to variables. Your first attempt looked vaguely like binding to a constructor, and that’s why you got a syntax error.

Haskell pattern matching can be more sophisticated, e.g., view patterns. For learning exercises, master the basics first.

Upvotes: 1

ДМИТРИЙ МАЛИКОВ
ДМИТРИЙ МАЛИКОВ

Reputation: 22000

When i tried to size (N a (left a) (right a)) instead of size (N a left right)

left and right in this case are expressions of type Tree Int.

a is not a known variable or type in this context.

In case the definition is updated to size (N a left right), then a is a bound expression of type Int.

Upvotes: 4

Related Questions