CODEWITHSUNDEEP
haskell
dijam
dijam

Reputation: 678

Understanding Haskell Type

I have managed to implement a mock filter functions (after lots of attempts)

filter' :: (Num a, Eq a) => (a -> Bool) -> [a] -> [a]
filter' a [] = []
filter' a (x:xs) = if a x
  then x : filter' a xs
  else filter' a xs

What I don't clearly understand is the type declaration 

filter' :: (Num a, Eq a) => (a -> Bool) -> [a] -> [a]
-- filter' (<10) [1,2,3] 
-- output = []

We pass in (<10) [1,2,3]. However in the type declaration (a -> Bool) we pass in a which comes from the list recursively and the output is either true or false. However what about the expressing the test (<10)? Why don't we add another Bool?

Upvotes: 2

Views: 118

Answers (1)

Mark Seemann
Mark Seemann

Reputation: 233477

The type of your filter' function is only so constrained because you've declared that it is. If you don't declare the type, the compiler will infer a more tolerant type: (a -> Bool) -> [a] -> [a]. This is the same type as the built-in filter function:

Prelude> :type filter
filter :: (a -> Bool) -> [a] -> [a]

The expression (< 10) is a so-called section. It's a partially applied function.

The operator < is itself a function:

Prelude> :type (<)
(<) :: Ord a => a -> a -> Bool

You can read this as: < is a function that takes two arguments, both of the generic type a. The type a must belong to the typeclass Ord. When you call < with such two values, a Bool value is returned.

Since Haskell functions are curried, you can call a function with only some of the arguments. The return value is a new function that 'waits for the remaining arguments':

Prelude> :type (< 10)
(< 10) :: (Num a, Ord a) => a -> Bool

This type is a little more constrained, because the literal 10 is inferred to belong to the Num typeclass. Since < is in use, the original constraint for that (Ord) is still in effect as well.

The expression [1,2,3] is is by the compiler inferred as:

Prelude> :type [1,2,3]
[1,2,3] :: Num t => [t]

The values all belong to the Num typeclass. When you use all of these types together, you get the union of all the inferred types:

Prelude> :type filter (< 10) [1,2,3]
filter (< 10) [1,2,3] :: (Num a, Ord a) => [a]

The Num typeclass is inferred because of the use of literals, and the Ord typeclass is inferred because of the use of the < operator.

Upvotes: 8

Related Questions