Haskell usage of data type

Question

I am reading making our own types and typeclasses in learn you a haskell.

In section Algebraic data types intro I notice:

data Point = Point Float Float deriving (Show)  
data Shape = Circle Point Float | Rectangle Point Point deriving (Show)

surface :: Shape -> Float
surface (Rectangle (Point x1 y1) (Point x2 y2)) = abs (x2 - x1) * abs (y2 - y1)

In surface (Rectangle (Point x1 y1) (Point x2 y2)), we indicate the parameters for Rectangle are of type Point.

However, in section Recursive data structures:

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)
singleton :: a -> Tree a  
singleton x = Node x EmptyTree EmptyTree  

treeInsert :: (Ord a) => a -> Tree a -> Tree a  
treeInsert x EmptyTree = singleton x  
treeInsert x (Node a left right)   
    | x == a = Node x left right  
    | x < a  = Node a (treeInsert x left) right  
    | x > a  = Node a left (treeInsert x right)

We don't indicate left's and right's data types are Tree a in treeInsert x (Node a left right). How does the compiler know their type?

luqui · Accepted Answer

I think you have a misconception here:

In surface (Rectangle (Point x1 y1) (Point x2 y2)), we indicate the parameters for Rectangle are of type Point.

This does indicate that the parameters are of type point, but perhaps not in the way that you think. The "Point" in Point x1 y1 is not a type -- it's a constructor which happens to be named the same way as the type it constructs. If we declared Point as

data Point = MakePoint Float Float

then you would say

surface (Rectangle (MakePoint x1 y1) (MakePoint x2 y2))

For clarity, I will continue using MakePoint for the constructor and Point for the type. It is legal Haskell to name these the same because the compiler can always tell from context, but humans sometimes have more trouble.

Within the context

surface (Rectangle (MakePoint x1 y1) (MakePoint x2 y2)) = ...

we know that the subexpression MakePoint x1 y1 has type Point from two different places. One is that the constructor Rectangle has type

Rectangle :: Point -> Point -> Shape

so we know that both of its arguments must be points (this is outside-in type inference, where we get the type of something from the context in which it's used); and the other is that the constructor MakePoint has type

MakePoint :: Float -> Float -> Point

so we know that MakePoint x1 y1 represents a value of type Point (this is inside-out type inference, where we get the type of an expression from its components). The compiler, in a way, uses both of these approaches and makes sure that they match.

However, sometimes one or the other of these kinds of information is lacking, for example x1 in our example. We have no inside-out information about x1 (well, we would if we looked at the right hand side of the equation, which the compiler also does, but let's ignore that for now), all we have is that the arguments to the MakePoint constructor must be Floats, so we know that x1 must be a Float. This is valid and inferred by the compiler; there is no need to state it explicitly.

In the Tree example there is more confusing naming going on (which, once you get this, ceases to be confusing and begins being helpful, but it's good to draw a clear distinction at the start), so I'm going to rename the first argument of Node to from a to v:

treeInsert :: (Ord a) => a -> Tree a -> Tree a  
treeInsert x EmptyTree = singleton x  
treeInsert x (Node v left right)   
    | x == v = Node x left right  
    | x < v  = Node v (treeInsert x left) right  
    | x > v  = Node v left (treeInsert x right)

The same thing is happening with left and right as was with x1 above: there is no inside-out structure to use, but we know that the Node constructor takes an a and two Tree as, so v must be of type a, and left and right must be of type Tree a. The compiler deduces this from the context.

Haskell usage of data type

Answers (2)

Related Questions