Haskell Function Composition with Map Function

Question

I'm going through the Richard Bird's "Thinking Functionally with Haskell" book and there is a section that I can't understand where he's proving a property of the filter method. What he's proving is:

filter p . map f = map f . filter (p . f)

Previously in the book, he defines the filter as:

filter p = concat . map (test p)
test p x = if p x then [x] else []

This is how he proves the first equation:

    filter p . map f
= {second definition of filter} -- He's referring to the definition I gave above
    concat . map (test p) . map f
= {functor property of map}
    concat . map (test p . f)
= {since test p . f = map f . test (p . f)}
    concat . map (map f . test (p . f))
= {functor property of map}
    concat . map (map f) . map (test (p . f))
= {naturality of concat}
    map f . concat . map (test (p . f))
= {second definition of filter}
    map f . filter (p . f)

What I can't understand is how test p . f is equal to map f . test (p . f).

This is how I tried to test it:

test :: (a -> Bool) -> a -> [a]
test p x = if p x then [x] else []

test ((<15) . (3*)) 4 -- test p .f, returns [4]
(map (3*) . test((<15) . (3*))) 4 -- map f . test (p . f), returns [12]

Can anyone please explain what I'm missing here?

Answer 1

You tested

test (p . f) = map f . test (p . f)

Which is indeed false. The property is actually

test p . f = map f . test (p . f)

Where the LHS associates as

test p . f = (test p) . f

Remember, function application is more tightly binding than any user-definable operator, acting like it's infixl 10. Two identifiers next to each other are always part of a prefix function application. (Except in the case of as-patterns: f xs@ys zs means f (xs@ys) zs.)

To prove the property:

    test p . f
={definition of (.)}
    \x -> test p (f x)
={definition of test}
    \x -> if p (f x) then [f x] else []
={definition of map, multiple times}
    \x -> if p (f x) then map f [x] else map f []
={float map f out of cases}
    \x -> map f (if p (f x) then [x] else [])
={definition of (.)}
    \x -> map f (if (p . f) x then [x] else [])
={definition of test}
    \x -> map f (test (p . f) x)
={definition of (.)}
    map f . test (p . f)

Adapting your example, test (<15) . (*3) means "multiply by 3, ensuring that the result is less than 15." map (*3) . test ((<15) . (*3)) means "ensure that thrice the input is less than 15, and, if so, return thrice the input."