CODEWITHSUNDEEP
haskell
August
August

Reputation: 1819

Haskell: General type of function pushing element to a list

Given a general function

cons x xs = x:xs

How would one give it a general type? I tried doing

cons:: a -> [b] -> [c]

But it does not seem to work

Upvotes: 0

Views: 93

Answers (2)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477533

A list is defined as (pseudocode):

data [a] = [] | a : [a]

Therefore a list can only contain elements of the same type: either it is an empty list ([]) so it does not contain any elements, or it is a CONS (:) and then the head is of type a and so is its tail [a].

Therefore if you define:

cons x xs = x : xs

Haskell takes a look at the signature of the constructor: a : [a]. So it derives that x is an a, xs is an [a], and (x:xs) is an [a] as well (the head of the data statement).

As a result, the most general type signature of cons is:

cons :: a -> [a] -> [a]
cons x xs = x : xs

You cannot define a cons with x :: a and xs :: [b] (with a different from b) since in that case you invoke the constructor (:) :: a -> [a] -> [a] with conflicting types.

In Haskell, you usually do not have to write type signatures. If you omit them, Haskell will fill in the most generic one. You can use :t in the ghci interactive shell to obtain the type of a function. Like:

Prelude> let cons x xs = x : xs
Prelude> :t cons
cons :: a -> [a] -> [a]

Finally note you do not need to define a cons function, you can simply use (:):

cons :: a -> [a] -> [a]
cons = (:)

Upvotes: 1

Davislor
Davislor

Reputation: 15154

Remember, a and b are potentially different types, and here you want to be able to add an a to the list. So, you want both lists to be type [a].

cons :: a -> [a] -> [a]
cons = (:)

Upvotes: 1

Related Questions