haskellcurryingtype-signature

Still confuse how type signature with multiple arrows work


I checked a post before and seems understand. I know

f :: a -> b -> c 

is the curry form of

g :: (a, b) -> c

But as the type signature gets longer than 2 arrows, I feel confused again.

myscanr :: (a -> b -> b) -> b -> [a] -> [b]
myscanr op z [] = [z]
myscanr op z (x:xs) = op x (head qs) : qs
  where
    qs = myscanr op z xs

Are (a -> b -> b) and [b] the input and output? What are the rest in the middle then?


Solution

  • Well conceptually, a function in Haskell has always exactly one parameter. Indeed, in fact the signature:

    myscanr :: (a ->  b -> b ) ->  b ->  [a] -> [b]
    

    is short for:

    myscanr :: (a -> (b -> b)) -> (b -> ([a] -> [b]))
    

    So there is always one parameter, but the result can be a function as well, and we can then provide an argument for that function to obtain a value, or another result, so this is some sort of "chaining".

    You could compare it to a programming language like Python where instead of having a function that accepts several parameters, it each time accepts a single parameter. For example:

    # python
    
    def add(x):
        def addx(y):
            return x + y
        return addx

    So here we have a function add. We can call it with a single parameter x. If we do that, with for example x=4, then it will return another function (where x is scoped). It is only if we then call that function with a parameter (for example y=3), that we get the outcome, like:

    >>> add(4)
    <function add.<locals>.addx at 0x7f1c519e7b70>
    >>> add(4)(3)
    7
    

    Well in Haskell, this model is the standard: every function accepts only a single parameter. But since that is the case, the syntax can be improved. Instead of having to write ((myscanr((+)))(0))([1, 4, 2, 5]), we can write myscanr (+) 0 [1, 4, 2, 5], and Haskell will automatically interpret this as a function call with myscanr as function and (+) as parameter, another function call with as function the result of the previous call and 0 as parameter, and then another function call with as function the outcome of the previous call with [1, 4, 2, 5] as parameter.

    Since syntactically it looks a bit like we have made a call with three parameters, one could say that the (a -> b -> b), b and [a] are the types of the "three parameters". But strictly speaking, that is wrong.