Type of any in Haskell?

Question

I've recently started trying to learn Haskell by reading LearnYouAHaskell and random articles from the internet.

I'm having hard time understanding more sophisticated function types.

Some examples that I understand.

> :t map  
map :: (a -> b) -> [a] -> [b]

It takes in a function (which takes a and gives out b, i.e a and b can be of different types) and a list of a's and return a list of b's.

> :t fst  
fst :: (a, b) -> a

Takes in a tuple of 2 elements (allows different types) and returns the first one.

> :t any  

At a higher level, I understand any. It takes in a function and a list and returns true if any of the list entries return true for that particular function. I've used it in Python and JavaScript as well.

Questions

• I don't understand how does any :: Foldable t => (a -> Bool) -> t a -> Bool translate to the above.

  • (a -> Bool) is the predicate. Takes in an argument and returns true or false.
  • t a -> Bool Bool is the end result of any. According to my understanding t and a represent the predicate and the list. Why aren't they separated by a ->

• How to go about understanding type signatures in general and how to dig deeper so that I can approach them myself?

Answer 1

any :: Foldable t => (a -> Bool) -> t a -> Bool

Here Foldable t means, that t is an instance of type class Foldable.

Foldable is a type class and if type t is an instance of the type class Foldable we know from the t a part of the signature or from the definition of the type class Foldable, that t is actually a type constructor.

So t a is a type and therefore t a -> Bool is a function, that maps a value of type t a to Bool. This function will be closure, which will apply the predicate to each "element" of the value of type t a, until it finds one, that yields True under the predicate or it doesn't find such an element returning either True or False in the respective cases. (The actual implementation might be very different.)

For example [] is an instance of the type class Foldable and therefore t a could be a list of something. In this case, we can also write [a] instead of [] a.

But there are other type constructors, which can be instances of Foldable, for example some kinds of trees.

Answer 2

It might be helpful to note that until recently, the signature was actually

any :: (a -> Bool) -> [a] -> Bool

This was generalised during the Foldable Traversable in Prelude proposal: now the container of values need not be a list, but can as well be e.g. an array:

Prelude> import qualified Data.Vector as Arr
Prelude Arr> :set -XOverloadedLists
Prelude Arr> let a = [1,2,3] :: Arr.Vector Int
Prelude Arr> any (>2) a
True

Answer 3

Type signature is a mark up designation of the function indicating the types to be processed and how the function can be partially applied.

Foldable t => (a -> Bool) -> t a -> Bool

By Foldable t it first says any function can work with any data type which is an instance of Foldable type class.

The first parameter, (a -> Bool) is obviously a function which takes a single element (a) from our foldable data type and returns a Bool type value. It's the the callback of .some(callback) in JavaScript. When you apply this parameter to any you will be returned with a function of type;

t a -> Bool

Now we are left with a single function which takes only one parameter and returns a Bool type (True or False) value. Again t a is a data type which is a member of the Foldable type class. It can be a [] but a Tree too provided that the data type has foldMap function defined under an instance to Foldable. It's the myArr part in JavaScript's myArr.some(callback) except that it doesn't have to be an array.

Answer 4

t a isn't separated by a -> because the t a is the instance of foldable, ex: List a, or Tree a. Let's go back to map for a second. The version you gave is specialized to lists; a more general version (which, as an accident of history, is called fmap in most versions of Haskell) has type fmap :: Functor f => (a->b) -> f a -> f b. Where is your input list in this signature? It's the f a. Now, returning to any the t a is the second argument, the instance of Foldable you're folding over, the list or tree or whatever.

You'll read that all functions in Haskell really have only 1 argument, and we're seeing that here. any takes it's first argument (the predicate) and returns a function that takes a foldable (the list, tree, etc) and returns a Bool.

Answer 5

t a does not represent the predicate and the list. As you've already correctly pointed out before, (a -> Bool) is the predicate. t a just represents the list, except it doesn't have to be a list (that's why it's t a instead of [a]). t can be any Foldable, so it could be [], but it could also be some other collection type or Maybe.