CODEWITHSUNDEEP
haskellghc
blue-sky
blue-sky

Reputation: 53876

How to implement recursive function?

Below defines an Algebraic Data Type IntList : 

data IntList = Empty | Cons Int IntList

The function intListProd computes the product of IntList type : 

intListProd :: IntList -> Int
intListProd Empty      = 1
intListProd (Cons x l) = x * intListProd l

But I'm unsure how to create IntList type.

I've tried :

*Main> let x = Cons 3
*Main> :t x
x :: IntList -> IntList

But how to create type IntList so as to invoke intListProd ?

Upvotes: 0

Views: 85

Answers (2)

Gabriel Ciubotaru
Gabriel Ciubotaru

Reputation: 1092

You are creating a new data type:

data IntList = Empty | Cons Int IntList

This basically create you 2 data contructor function:

> :t Empty
Empty :: IntList

> :t Cons
Cons :: Int -> IntList -> IntList

So the first returns an IntList type and the second need 2 parameters ( Int and IntList) and return an IntList.

In your binding you just partially apply Cons function, giving it just 1 param :

*Main> let x = Cons 3

and this is asking you for another IntList to be a complete type. Now, you can obtain an IntList in 2 ways (because you have 2 constructors for this type):

Cons 3 (Empty)

or

Cons 3 (Cons a b) --where a is an Int and b is IntList.

Now for the second, b can be Empty or Const a' b':

Cons 3 (Cons 1 (Empty))

or

Cons 3 (Cons 2 (Cons 1 (Empty))) -- 3 2 1 could be any Int number.

Let's now take a closer at type of the second one:

Cons Int ( Cons Int ( Cons Int ( IntList)))

Remember Cons takes an Int and an IntList and returns an IntList ? 

Cons Int ( Cons Int ( IntList)) --Now doing the same we came up to
Cons Int (IntList) -- Once more
IntList

That means our construction Cons 3 (Cons 2 (Cons 1 (Empty))) have type of IntList and can be used to apply intListProd computation over it.

Upvotes: 1

sepp2k
sepp2k

Reputation: 370377

A Cons cell contains two things: an element and a tail. If the list is only supposed to contain one element, the tail is empty (represented by the nullary constructor Empty). So to represent a list containing 3 as its only element, you use:

let x = Cons 3 Empty

Then :t x will be IntList.

Upvotes: 3

Related Questions