Haskell High Order Functions, Function Declaration

Question

I am studying for an exam and I'm confused at this function. Based on the output how do I know that the type declaration of the function is (a -> b -> c)? also, how I can evaluate my function?

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' _ [] _ = []
zipWith' _ _ [] = []
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys

What I understand is that high order functions in haskell mean that they take a function as a parameter and return a function as well, right? how can I call this particular function?

I did this:

zipWith' [1..5] ['a','z','r']

but I know is wrong because I am calling it as if it were the regular zip function that takes 2 lists and returns a tuple. I am just confused at the type declaration

zipWith' :: [a] -> [b] -> [(a,b)]

No-one said a higher-order function has to return a function. The term is a somewhat loose one, but usually means a function that either has a function as a parameter or returns one. zipWith takes a function as a parameter and thus is considered a higher-order function - but it certainly doesn't return a function. — Robin Zigmond
As for how to call zipWith (or your, equivalent, version zipWith`), you haven't supplied it with the function argument. Try, for example, zipWith' (+) [1,2] [3,4] (should be [4,6]). — Robin Zigmond
@RobinZigmond Well, technically it does return a function. It takes a a -> b-> c, and returns a [a] -> [b] -> [c]. — chepner
@wwww Where do you get [a] -> [b] -> [(a,b)]? That is, indeed, the type of zip, but it is also the type of zipWith' (,) (which is zipWith' applied to (,) :: a -> b -> (a,b)). — chepner
@RobinZigmond I think for this question, one actually should explicitly acknowledge currying. It helps explain why the first argument has to have type a -> b -> c instead of just a -> b. — chepner

chepner chepner · Accepted Answer · 2019-03-29T17:48:23

For this answer, we'll acknowledge that all functions are curried. That is, every function has a type a -> b, where a and b are some type.

A higher-order function is one whose type includes a function for either its argument or return type. Return values are easy: it's any function you ordinary think of as taking more than one argument:

take :: Int -> [a] -> [a]. It takes an Int and returns a (polymorphic) function that takes a list and returns a list.
map :: (a -> b) -> [a] -> [b]. It takes a function (literally any function) and returns a function from lists to lists. The types of the return value is determined by the type of the argument.

Higher-order functions that take an function and return something that isn't a function are actually somewhat rare. Perhaps a commenter will point out an obvious one I am overlooking, but until then, consider fix :: (a -> a) -> a.

Now, zipWith' is an example of a higher-order function whose argument itself must be a higher-order function. The general type a -> b can unify with an ordinary function like ord :: Char -> Int (a ~ Char and b ~ Int) as well as a higher-order function like (+) (with a ~ Num t => t and b ~ Num t => t -> t. The type a -> b -> c will only unify with higher-order functions. a may or may not be a function type, but b -> c is an explicit function type.

This means that once you apply zipWith' to some higher-order function, type inference gives you more information about what the types of [a], [b], and [c] must be in the resulting function.

zipWith' (+) tells you that a ~ b ~ c ~ Num t => [t].
zipWith' (,) tells you that a and b are still unrestricted, but c ~ (a, b)
zipWith' (:) tells you that a is unrestricted, but b ~ c ~ [a].

It may also help if you consider that zip :: [a] -> [b] -> [(a,b)] could be defined as zip = zipWith' (,).

Haskell High Order Functions, Function Declaration

1 Answers