CODEWITHSUNDEEP
haskell
Daniel Robinson
Daniel Robinson

Reputation: 14848

Haskell type declarations for multiple parameter functions

I'm looking through this introduction to Haskell which contains this example:

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

which it says is essentially also defining the types:

Branch                  :: Tree a -> Tree a -> Tree a
Leaf                    :: a -> Tree a

I understand the Leaf definition is saying that it maps an a to a Tree of a. but I don't understand the Branch definition, I read it as "Branch maps Tree of a to Tree of a to Tree of a which doesn't sound correct. Is this because all Haskell functions get curried by default?

Upvotes: 3

Views: 2024

Answers (3)

Kapol
Kapol

Reputation: 6463

I read it as "Branch maps Tree of a to Tree of a to Tree of a"

You can think of the definition as a function that takes a Tree a and returns another function, which also takes a Tree a and produces a Tree a (which is the final result, a tree with two branches). Your signature of Branch is equivalent to

Branch :: Tree a -> (Tree a -> Tree a)

The notion that every function has just one input parameter is called currying.

Upvotes: 3

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476503

No. If it had a signature like:

Branch :: (Tree a, Tree a) -> Tree a

then you should have to feed it a tuple, and call the constructor like:

Branch (tree1,tree2)

Branch has however a signature:

Branch :: Tree a -> Tree a -> Tree a

Or with explicit parenthesis:

Branch :: Tree a -> (Tree a -> Tree a)

So when you feed Branch a first parameter, like Branch tree1, the signature is:

(Branch t1) :: Tree a -> Tree a

when you finally feed it a second parameter t2, its type will collapse to:

((Branch t1) t2) :: Tree a

A more convenient example is for instance (+) which is not a constructor, but a function. (+) our plus (+) has signature 

(+) :: Int -> Int -> Int

(Haskells plus is a bit more generic, but let's not consider this now).

If you now write (5+) you have specialized your function to a function:

(5+) :: Int -> Int

In other words you constructed a new function that will add 5 to the given number.

Since the signatures for (a,b) -> c and a -> b -> c are however a bit equivalent, Haskell provides the curry and uncurry functions:

curry :: ((a, b) -> c) -> a -> b -> c
uncurry :: (a -> b -> c) -> ((a, b) -> c)

If you decide you need for instance an additional constructor for Branch that should be fed a tuple, you can construct such constructor:

branchTuple :: (Tree a, Tree a) -> Tree a
branchTuple = uncurry Branch

Upvotes: 5

Chad Gilbert
Chad Gilbert

Reputation: 36375

Branch (Tree a) (Tree a) is a constructor with two type parameters, both of which are Tree a, and the result of that constructor is a Tree a, hence the definition of

Tree a -> Tree a -> Tree a

I understand the Leaf definition is saying that it maps an a to a Tree of a. but I dont understand the Branch definition, shouldn't it be something like:

Branch :: (Tree a, Tree a) -> Tree a

No, because if you used (Tree a, Tree a), you would be defining a single type parameter which is a tuple.

Upvotes: 2

Related Questions