CODEWITHSUNDEEP
haskellfunctiontypesdefinitiontype-inference
Azriel
Azriel

Reputation: 407

haskell and type definition of functions. couple of questions

if i do any isUpper "asBsd", i'll get True.
here, the second element to any is a string.
but, if i do this: 

any ("1" `isInfixOf`) ["qas","123","=-0"]

the second element to any is a list of strings.
how and why this difference between those 2 functions?

another example.
if i write filter isUpper "asdVdf" , i'll get "V".
here, the second element to filter, is a string.
but, if i write this:
filter (isUpper . head) ["abc","Vdh","12"] , i'll get ["Vdh"].
as you can see, the second element to filter is now a list of strings.
why there is a differences and how haskell know's it's right in both cases?

to summarize it:
i don't understand how in the same function, one time haskell get a second element that is a string, and in other time, haskell get a list of strings, in the second element.
one time it happened in any function, and the other time in filter function.
how haskell(and me) know's it's right in both cases?

thanks :-).

Upvotes: 3

Views: 572

Answers (3)

kennytm
kennytm

Reputation: 523284

Because isUpper is a Char -> Bool function and "1" ‘isInfixOf‘ and isUpper . head are [Char] -> Bool functions

"1" `isInfixOf` xxx

can be rewritten as

isInfixOf "1" xxx

We knew the type of isInfixOf is [a] -> [a] -> Bool1. Now the first argument to isInfixOf is "1" which is of type [Char], so we can deduce a is a Char:

     isInfixOf :: [a]    -> [a] -> Bool
       "1"     :: [Char]
//∴ a = Char and
 isInfixOf "1" ::           [a] -> Bool
                =        [Char] -> Bool

That means isInfixOf "1" is now a [Char] -> Bool function.

Now, the type of any is (a -> Bool) -> [a] -> Bool function. As above, 

               any :: (a      -> Bool) -> [a] -> Bool
     isInfixOf "1" :: ([Char] -> Bool)
 //∴ a = [Char] and

any (isInfixOf "1") :: [a] -> Bool = [[Char]] -> Bool

In order to satisfy with the type constraint of any (isInfixOf "1"), the argument must be a string list.

Now consider isUpper. The type of isUpper is Char -> Bool. Hence:

              any :: (a    -> Bool) -> [a] -> Bool
          isUpper :: (Char -> Bool)
//∴ a = Char and
      any isUpper ::                   [a] -> Bool
                   =                [Char] -> Bool

So any isUpper needs to take a string only, instead of a string list.

Finally, isUpper . head. In Haskell, the types of the relevant functions are:

 filter :: (a -> Bool) -> [a] -> [a]
   head :: [a] -> a
isUpper :: Char -> Bool
    (.) :: (b -> c) -> (a -> b) -> a -> c

Hence for filter isUpper, a = Char and the type is [Char] -> [Char], i.e. it needs to take a string as parameter.

And2:

            (.) :: (b    -> c   ) -> (a   -> b) -> a -> c
        isUpper :: (Char -> Bool)
           head ::                   ([b] -> b)
//∴ c = Bool, b = Char, a = [b] = [Char], and
 isUpper . head ::                                 a -> c
                =                             [Char] -> Bool

Thus for filter (isUpper . head), we have a = [Char] and the type is [[Char]] -> [[Char]], i.e. it needs to take a string list as parameter.

Note:

  1. The type of isInfixOf is actually (Eq a) => [a] -> [a] -> Bool as the equality must be valid for type a, but this is irrelevant in our analysis.
  2. I've temporarily changed the variable a to b for head, but it doesn't matter.

Upvotes: 12

yatima2975
yatima2975

Reputation: 6610

Well, that's polymorphism. The type of any is (a -> Bool) -> [a] -> Bool where the type variable a can be anything you like. In the first case it's Char - because the second argument is a list of Chars - and the type becomes (Char -> Bool) -> String -> Bool (remember that [Char] is the same as String!); in the second a is String and the type becomes (String -> Bool) -> [String] -> Bool.

The reasoning for filter is similar.

Upvotes: 4

Tyler
Tyler

Reputation: 22116

A String is actually just list of characters, a [Char]. So if you like, "hello" is shorthand for ['h', 'e', 'l', 'l', 'o']. Therefore in both cases, you're getting a list of something, it's just that one case is a list of Char and the other case is a list of Strings (or a list of lists of chars, if you like).

Upvotes: 5

Related Questions