Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Haskell type length + 1

Tags:

haskell

Could anyone help me to explain the type of length + 1 I tried to type into ghci with following command :t length + 1 it returns Num([a]->Int)=>[a]->Int what does this mean? Thx

like image 209
Xiaotong Yang Avatar asked Sep 07 '14 01:09

Xiaotong Yang


1 Answers

Look at the type of +:

> :t (+)
(+) :: Num a => a -> a -> a

So both arguments have to be from the same instance of Num, and it returns one of those. Then look at the type of length:

> :t length
length :: [b] -> Int

(Note that I've changed to use b here as the type variable, but it doesn't change the meaning).

So if you have length + something, then length must have a type that implements Num. Since length's type is already set as [b] -> Int, this means that [b] -> Int needs to be an instance of Num, and something would have to have the same type. Since numeric literals in Haskell are polymorphic, this means that 1 can just has the type Num a => a, and the precise instance can be chosen by context. Since in the expression length + 1, both arguments to + have to have the same type, this means that 1 has to have the same type as length, meaning that if we wrote out all the types explicitly we'd have something like

((+) :: Num ([b] -> Int) => ([b] -> Int) -> ([b] -> Int) -> ([b] -> Int))
    (length :: [b] -> Int)
    (1      :: [b] -> Int)

(Written in prefix form and split onto multiple lines so we can actually read it).

So basically, what this is saying is that in order to add something to length, you have to first define an instance of Num for length's type. The return type of [b] -> Int is just saying that it's returning something of the same type as length.

Is this useful? No, almost certainly not. It's a feature of Haskell's type system that you can write interesting and strange instances of Num for literally any type, but that does not mean that an instance of Num for every type is useful, definable in an intelligent way, or even possible without resorting to undefined.


We could write an instance for Num for this type, but I'll choose to write it inside a newtype because it lets us avoid language extensions.

newtype Silly a = Silly { unSilly :: [a] -> Int }

instance Num (Silly a) where
    fromInteger x = Silly $ const (fromInteger x)
    Silly f + Silly g = Silly $ \l -> f l + g l
    Silly f * Silly g = Silly $ \l -> f l * g l
    negate (Silly f) = Silly $ negate . f
    abs (Silly f) = Silly $ abs . f
    signum (Silly f) = Silly $ signum . f

Then we can use it as

> (unSilly $ Silly length + 1) [1, 2, 3]
4
> (unSilly $ Silly length * Silly length) [1, 2, 3, 4]
16
> (unSilly $ negate $ Silly length) [1, 2, 3]
-3

But this isn't really useful, it adds quite a bit of boilerplate to do something equivalent to

> length [1, 2, 3] + 1
4
> length [1, 2, 3, 4] * length [1, 2, 3, 4]
16
> negate $ length [1, 2, 3]
-3

Although in some examples are kind of cool:

> (unSilly $ Silly head + Silly last) [10, 0, 1, 2, 3, 4, 5]
15

But this only works on lists of type [Int].

like image 182
bheklilr Avatar answered Nov 07 '22 03:11

bheklilr