Determining the type of a function

Question

I am trying to figure out the way Haskell determines type of a function. I wrote a sample code:

compareAndIncrease a b = if a > b then a+1:b:[] else a:b:[]

which constructs a list basing on the a > b comparison. Then i checked its type with :t command:

compareAndIncrease :: (Ord a, Num a) => a -> a -> [a]

OK, so I need a typeclass Ord for comparison, Num for numerical computations (like a+1). Then I take parameters a and b and get a list in return (a->a->[a]). Everything seems fine. But then I found somewhere a function to replicate the number:

replicate' a b | a ==0 = [] | a>0 = b:replicate(a-1) b

Note that normal, library replicate function is used inside, not the replicate' one. It should be similar to compareAndIncrease, because it uses comparison, numerical operations and returns a list, so I thought it would work like this:

replicate' :: (Ord a, Num a) => a -> a -> [a]

However, when I checked with :t, I got this result:

replicate' :: Int -> t -> [t]

I continued fiddling with this function and changed it's name to repval, so now it is:

Could anyone explain to me what is happening?

It seems to deduce 0::Int here

Niklas B.
– Niklas B.

2014-06-22 17:02:59 +00:00
Commented Jun 22, 2014 at 17:02 — Niklas B.
– Niklas B., Commented Jun 22, 2014 at 17:02

dfeuer · Accepted Answer · 2014-06-22 18:38:49Z

GHCi is a great tool to use here:

*Main> :type replicate replicate :: Int -> a -> [a]

You define replicate' in terms of replicate (I rename your variables for clarity):

replicate' n e | -- blah blah blah | n > 0 = e : replicate (n - 1) e

Since you call replicate (n - 1), the type checker infers that n - 1 must have type Int, from which it infers that n must have type Int, from which it infers that replicate' has type Int -> a -> [a].

If you wrote your replicate' recursively, using replicate' inside instead of replicate, then you would get

*Main> :type replicate' replicate' :: (Ord a, Num a) => a -> a1 -> [a1]

Edit

As Ganesh Sittampalam points out, it's best to constrain the type to Integral as it doesn't really make sense to replicate a fractional number of times.

Actually, after writing it recursively I got (Ord a, Num a) instead of (Eq a, Num a) because I am using comparison, but your answer is right :)

Ganesh Sittampalam · Accepted Answer · 2014-06-22 17:33:50Z

The key flaw in your reasoning is that replicate actually only takes Int for the replication count, rather than a more general numeric type.

If you instead used genericReplicate, then your argument would be roughly valid.

genericReplicate :: Integral i => i -> a -> [a]

However note that the constraint is Integral rather than Num because Num covers any kind of number including real numbers, whereas it only makes sense to repeat something an integer number of times.

Collectives™ on Stack Overflow

Determining the type of a function

2 Answers 2

Edit

1 Comment

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Edit

1 Comment

Comments

Related