CODEWITHSUNDEEP
functionhaskell
DB Tsai
DB Tsai

Reputation: 1408

How to interpret the function type in Haskell?

My code is the following

data Tree a = Leaf a | Node (Tree a) (Tree a) 
    deriving (Show)
f x = x + 1
myTree = Node (Node (Leaf 2) (Leaf 3)) (Leaf 4)
maptree f (Leaf a)= Leaf (f a)
maptree f (Node xl xr ) = Node (maptree f xl) (maptree f xr)

which can add one to the Leaf element in the tree.

I further look at the function type which are 

*Main> let maptree f (Leaf a)= Leaf (f a) 
maptree :: (t -> a) -> Tree t -> Tree a 

*Main> let maptree f (Node  xl xr ) = Node (maptree f xl) (maptree f xr) 
maptree :: t -> Tree t1 -> Tree a

What do t, a, and t1 mean over here? Is there any reference that I can read for those stuffs?

Thanks.

Upvotes: 1

Views: 293

Answers (2)

rovaughn
rovaughn

Reputation: 1223

We'll start with the first signature:

(t -> a) -> Tree t -> Tree a

This essentially says, "Given a function that takes something of type t and produces an a and also a Tree containing items of type t, produce a Tree containing elements of type a.

t and a are completely arbitrary names that GHCi generated; we could have easily said:

(originalType -> newType) -> Tree originalType -> Tree newType

Although most programmers would write:

(a -> b) -> Tree a -> Tree b

Now, the second signature:

t -> Tree t1 -> Tree a

This signature's strange because, like Hammar pointed out, the two maptree definitions you wrote in GHCi are completely independent. So let's look at the second definition all by itself:

maptree f (Node xl xr) = Node (maptree f xl) (maptree f xr)

Here, the type of f does not matter as you don't apply it to any arguments and you only pass it to maptree, which recursively doesn't care what type f is. So let's give f type t, as it doesn't matter.

Now, similarly, there's no constraint on xl and xr, as they are only passed to maptree which doesn't know their types except that it should be a Tree. Thus, we might as well call their type Tree t1.

We know this function will return a Tree because of the Node constructor, but the previous two types we looked at have no bearing on the type of elements in the tree, so we may as well call it Tree a.

As an example, let's see what happens when we expand the following:

maptree True (Node (Leaf 0) (Leaf 1))
= Node (maptree True (Leaf 0)) (maptree True (Leaf 1))

Which then fails because there's no way for maptree to expand a Leaf in this case.

However, the types work out:

True                   :: t
Node (Leaf 0) (Leaf 1) :: Tree t1
0                      :: t1
1                      :: t1

So that signature was very odd, but it does make sense. Remember to not overwrite definitions, I guess.

Upvotes: 2

hammar
hammar

Reputation: 139910

Identifiers beginning with a lower case letter, like t, a and t1, are type variables when used in a type context. They are placeholders which can be specialized to any type. See this answer for more information on how to read type signatures.

Also note that in GHCi, your example will first define one function which only handles the Leaf case, and then replace it with another which only handles the Node case, unlike in Haskell source files where they will be two cases of the same function. To specify multiple equations for a function in GHCi, separate them with a semicolon:

*Main> let maptree f (Leaf a) = Leaf (f a); maptree f (Node xl xr) = Node (maptree f xl) (maptree f xr)

or use multiline mode:

*Main> :{
*Main| let maptree f (Leaf a) = Leaf (f a)
*Main|     maptree f (Node xl xr) = Node (maptree f xl) (maptree f xr)
*Main| :}

Upvotes: 3

Related Questions