haskellfunction-composition

How does the function composition (.) operator work with multiple compositions?


I know that the dot (.) operator is defined to take three arguments(two functions and a value of type "a"), and works by the application of applying the argument to the function on the right, and the function on the left is applied to the output of the application of the left side, like follows:

-- Associativity: infixr 9
(.) :: (b -> c) -> (a -> b) -> a -> c
(f . g) x = f(g x)
-- Or in another format
f . g = \x -> f(g x)

Now, that's what's confusing with more than one application with the dot operator in a function composition, consider this:

With an infix operator like (+), it takes two arguments of types within the "Num" class.

(+) :: Num a => a -> a -> a

-- An application would look like this:
> 4 + 3
7

-- With more applications composed with (+)
> 4 + 3 + 2
9

-- Which is fine, since the last application
-- still takes two arguments of the legitimate types,
-- which is a value of type within "Num" class, as follows
> (4 + 3) + 2
-- 7 + 2
9

But with the dot operator, as follows. The last function composition with the dot operator should instead take the output of the application "reverse . take 3 $ map (*2) [1..]", which is "[6,4,2]" of the previous function composition.

If that's what I said, the dot operator takes a value instead of a function and a value on the right side, how is it supposed to work?

> replicate 4 . reverse . take 3 $ map (*2) [1..]
[[6,4,2],[6,4,2],[6,4,2],[6,4,2]]

Isn't it supposed to be like follows for its middle step?

-- And it's not going to work, since the dot operator
-- is defined to take three arguments of two functions
-- "(b -> c)" and "(a -> b)"
-- and the value of type "a"
replicate 4 . [6,4,2]

Since an application of dot operator takes three arguments and then returns a result of a value of type "a".

So the part "reverse . take 3 $ map (*2) [1..]" on the left side should be evaluated to "[6,4,2]"

Why is it not?


Solution

  • You are getting confused by currification (more on this later). You can think of (.) as taking two arguments (as (+) does).

    -- Associativity: infixr 9
    --                             |- this parens. aren't necessary, but It helps to make them explicit
    (.) :: (b -> c) -> (a -> b) -> (a -> c)
    --     |- input 1  |- input 2  |- result function 
    

    Now, because (.) it is right assoc the two lines of code below are equivalent

    replicate 4 . reverse . take 3   
    replicate 4 . (reverse . take 3) -- by right assoc. property
    

    in order to make this more explicit let me rewrite the code above

    -- original
    doSomething = replicate 4 . reverse . take 3 $ map (*2) [1..]
    
    -- original with explicit parenthesis
    doSomething = ( replicate 4 . (reverse . take 3) ) (map (*2) [1..])
                  |               |- right assoc  -| | |              |
                  |                                  | |              |
                  |- these four are the result of deleting $ symbol  -|
    
    -- factor out each parenthesis. Types are monomorphise for clarity.
    doSomething = (replicateFour . takeThreeAndReverse) evenNumbers 
      where replicateFour       = replicate 4      -- :: [Int] -> [[Int]]  
            takeThreeAndReverse = reverse . take 3 -- :: [Int] -> [Int]
            evenNumbers         = map (*2) [1..]   -- :: [Int]
    

    Now, the technique we are applying here is called currying. Which can be summarize as "a function which takes two arguments can be re-written as a function taking one argument and returning another function taking one argument."

    Some python code for the sake of understanding

    # The following two are equivalent functions. 
    def add(x, y):
      return x + y
    
    def add_curry(x):
      def inner(y):
        return x + y
      return inner # we return a function not a value
    
    add(3, 4) == add(3)(4) # notice double function call in RHS
    

    Now, all haskell functions are curried, this actually make a lot of sense on a functional language because if simplifies a lot composition and makes the language more ergonomic in most situations (altough, this is an opinion and someothers may ague differently)

    Currying can be a headache in the beginning but eventually It fells pretty natural. The best way to overcome it is by doing a lot of exercises and trying to use a lot of partial application