Tag: Haskell

foldl and foldr are two functions which make people confused easily. Check the types of them:

foldl :: (b -> a -> b) -> b -> [a] -> b 
foldr :: (a -> b -> b) -> b -> [a] -> b

The common characteristic of them is the result type is the same as accumulator: b. A memo to differentiate them is for foldl: it will traverse the elements from the left of list, and the accumulator also works as the left operand of the binary operator: (b -> a -> b). But for foldr, it goes to the opposite side: it will iterate the elements from the right of list, and the accumulator also works as the right operand of the binary operator: (a -> b -> b).

The other important thing is foldr can operate on infinite list whereas foldl not.

I don’t know other guys, but for me, sometimes I am confused with $ (“application operator”) and . (“function composition”) in Haskell, so I want to write a small summary to differentiate them.

Check the type of these two operators:

> :t ($)
($) :: (a -> b) -> a -> b
> :t (.)
(.) :: (b -> c) -> (a -> b) -> a -> c

For infix operator, $, its left operand should be a function whose type is a->b, the right operand should be the input parameter of this function: a, then get the result b. Check following example:

countWords :: String -> Int
countWords s = length $ words s

words returns a String list which is the input argument of length, then length returns how many words this string has. Run countWords in ghci:

> let countWords s = length $ words s
> countWords "a b c"
3

See . now; maybe another the type notation of . can give you a hand in comprehending it:

(.) :: (b -> c) -> (a -> b) -> (a -> c)

We can think the operands of . are both functions, and the return value is also a function. however, the three functions are not random, but have relationships with their parameters. Modify countWords and run it in ghci:

> let countWords s = length . words s

<interactive>:12:29: error:
    * Couldn't match expected type `a -> [a0]'
                  with actual type `[String]'
    * Possible cause: `words' is applied to too many arguments
      In the second argument of `(.)', namely `words s'
      In the expression: length . words s
      In an equation for `countWords': countWords s = length . words s
    * Relevant bindings include
        countWords :: String -> a -> Int (bound at <interactive>:12:5)

Woops! Error is generated. The reason is the space ” “, or function application has the highest precedence, so words s should be evaluated first:

:t words
words :: String -> [String]

The return value is [String], not a function, so it doesn’t satisfy the type of . who requires the two operands must be functions. Change the countWordsdefinition:

> let countWords s = (length . words) s
> countWords "a b c"
3

This time it works like a charm! For the same reason, the second operand of $ must be consistent with the input parameter of the first operand:

> let countWords = length $ words

<interactive>:18:18: error:
    * No instance for (Foldable ((->) String))
        arising from a use of `length'
    * In the expression: length $ words
      In an equation for `countWords': countWords = length $ words

It is time to warp it up: the operands of . is function, and we can use .to chain many functions to generate a final one which works as the left operand of $, feed it with one argument and produce the final result. Like this:

> length . words $ "1 2 3"
3

The same as:

> length $ words $ "1 2 3"
3

As a newbie of Haskell, I find the life becomes easier once I understand function application:

(1) function application is actually “function call”. For example, define a simple add function who returns the sum of 2 numbers:

# cat add.hs
add :: Num a => a -> a -> a
add a b = a + b

Load it in ghci, and call this function:

# ghci
GHCi, version 8.2.2: http://www.haskell.org/ghc/  :? for help
Prelude> :l add
[1 of 1] Compiling Main             ( add.hs, interpreted )
Ok, one module loaded.
*Main> add 2 4
6
*Main> add 3 6
9

Beware that the tokens in function application are separated by space. So once you see following format:

a b ..

You know it is a function application, and also a “function call”.

(2) function application has the highest precedence. Check following example:

*Main> add 1 2 ^ add 1 2
27

It is equal to “(add 1 2) ^ (add 1 2)” literally.

(3) $ operator is “application operator”, and it is right associative, and has lowest precedence. Check following instance:

*Main> add 1 $ add 2 $ add 3 4
10

The $ operator divides the expression into 3 parts: “add 1“, “add 2” and add 3 4. Because $ is right associative, the result of add 3 4 is fed into add 2function first; then the result of add 2 $ add 3 4 is passed into add 1. It is equal to “add 1 ( add 2 ( add 3 4 ) )” in fact, so $ can be used to remove parentheses.

References:
Prelude;
Calling functions.

As a layman of Haskell, I find being cautious of upper/lower case letters help me a lot to get understanding of functions:

(1) Function name doesn’t begin upper case: it can be lower case (e.g., sqrt) or special characters (e.g., +).

(2) Function has type. Let’s define a new function, incInt:

incInt :: Integer -> Integer
incInt a = a + 1

The above identifies incInt‘s type is “Integer -> Integer“: Integer is type in Haskell, and types begin with upper case. Check another built-in functionsqrt:

Prelude> :t sqrt
sqrt :: Floating a => a -> a

The “Floating a” which is in the left of => is called type constraint: Floating is typeclass, and its values are types which satisfy this typeclass (Floatingtypeclass contains both Float and Double types); a is a type variable which can be any type which belongs to Floating typeclass.

Takeaway:
a) Function name can’t begin with upper case letters.
b) Type, typeclass, type variable occur in function type definition. Type and typeclass begin with upper case letters, and type variable need to begin with lower case letters.