# Polymorphic Recursion / Rank-2 Confusion

Dominic Steinitz dominic.steinitz at blueyonder.co.uk
Sun Sep 21 09:35:45 EDT 2003

```Brandon,

I get the error below without the type signature. My confusion was thinking
I needed rank-2 types. In fact I only need polymorphic recursion. Ross
Paterson's suggestion fixes the problem. I stole Even and Odd from Chris
Okasaki's paper on square matrices. They relate to fast exponentation
algorithm. There's something to be said for Zeror and One; as you say they
give the structure in binary.

My motivation in using this type was to see if, for example, I could
restrict addition of a vector to another vector to vectors of the same
length. This would be helpful in the crypto library where I end up having to
either define new length Words all the time or using lists and losing the
capability of ensuring I am manipulating lists of the same length.

Dominic.

hugs

Type checking
ERROR "Test1.hs":23 - Type error in function binding
*** Term           : coal_
*** Type           : (a -> b) -> (c -> [d]) -> Vector_ a e -> b
*** Does not match : (a -> b) -> ((c,c) -> [d]) -> Vector_ a (e,e) -> b
*** Because        : unification would give infinite type

ghci

Test1.hs:25:
Occurs check: cannot construct the infinite type: t = (t, t1)
Expected type: (t, t1)
Inferred type: t
In the first argument of `coalw', namely `w1'
In the first argument of `(++)', namely `(coalw w1)'

----- Original Message -----
From: "Brandon Michael Moore" <brandon at its.caltech.edu>
To: "Dominic Steinitz" <dominic.steinitz at blueyonder.co.uk>
Sent: Saturday, September 20, 2003 11:19 PM
Subject: Re: Polymorphic Recursion / Rank-2 Confusion

> Sorry about the empty message. Send /= Cancel
>
> > Can anyone tell me why the following doesn't work (and what I have to do
to
> > fix it)? I thought by specifying the type of coalw as rank-2 would allow
it
> > to be used both at a and (a,b).
>
> Frank explained why the type you gave wouldn't work. I would like to add
> that your function would type check without the type signature. This
> suggests something here is actively confusing. Do you have any idea what
> caused this problem?
>
> I hope to help teach Haskell to first year students, so I'm trying to
> figure out what parts of the language are hard to get, and how to usefull
> explain things. Anything in pure H98 that trips up an experienced
> programmer is worth some attention.
>
> Completely unrelated, I think Zero and One would be better names than Even
> and Odd because then the string of constructors writes the size of the
> vector in binary, LSB first. I can't see any mnenomic value to Even and
> Odd. How do you interpret Even and Odd?
>
> Thanks
>
> Brandon
>

```