Error when trying to use function composition in Haskell

Question

I have just began recently to learn Haskell, more specifically on the topics of function composition, partial functions, maps, filters and sectioning. On one of the exercises am asked to modify the twoFilters function by using function composition.

I have read a few wikis on . but am having quite a hard time getting it to work correctly. As i understand it, it works by performing the functions b . a on alphabetical order and returning the result. In other words x = foo a and then foo b of x. However after applying several "variations/possibilities" with the bellow two filters functions i cant get it to compile due to errors.

greaterThanOne :: Int -> Bool
greaterThanOne = (>1)

lessThanTen :: Int -> Bool
lessThanTen = (<10)

twoFilters :: [Int] -> [Int]
twoFilters xs= filter lessThanTen (filter greaterThanOne xs)

These two being the unsuccessful attempts I had most confidence on;

twoFilters xs = filter (lessThanTen . greaterThanOne xs)

twoFilters xs = filter (lessThanTen xs . greaterThanOne xs)

Where on the reasoning am I going wrong?

Answer 1

The attempts you were confident about are a simple failure in your logic: the dot operator works like this:

(f.g)(x) = f(g(x))

So, trying to compute an example of 5 gives:

lessThanThen(greaterThanOne(5)) = lessThanTen(True) -- that can't be right, can it???

What you want is a lambda and &&:

filter (\x-> (lessThanThen x) && greaterThanOne(x))

Alternatively, you can use two filters:

filter lessThanTen . filter greaterThanOne $

Answer 2

Enter the wonderful world of Applicative Functors:

import Control.Applicative

greaterThanOne = (>1)

lessThanTen = (<10)

twoFilters = filter ((&&) <$> greaterThanOne <*> lessThanTen)

twoFilters [1,2,3,4,5,6,7,8,9,10]
-- [2,3,4,5,6,7,8,9]

Read Learn you a Haskell - Applicative Functors for a detailed explanation.

Answer 3

You can't compose those two functions like this. f . g works like composition in maths, i.e. is equivalent to f(g(x)). That means the outer function must take an argument of a type that inner function returns, in your case the outer function would have to be Bool -> Bool.

You can write your twoFilters using composition operator like this:

twoFilters = (filter lessThanTen) . (filter greaterThanOne)

Answer 4

(.) expects a function which takes one argument and returns a value, but you pass it a Bool value in:

lessThanTen . greaterThanOne xs

which is wrong.

Here:

lessThanTen xs . greaterThanOne xs

you're trying to compose two Bool values, but you should've composed two functions which return Bool values.

Answer 5

One issue it that function application has highest precedence. So lessThanTen . greaterThanOne xs tries to compose lessThanTen with the result of greaterThanOne xs (which doesn't work to start with, the function works on integers, not on lists thereof). Likewise, lessThanTen xs. greaterThanOne xs tries to compose the results of those function calls (assuming they'd make sense in the first place), not the functions themself.

Another problem is a misunderstanding of . - (f . g) x is equivalent to f (g x), i.e. the result of the first function is the argument for the second. So the type of g must be (a -> b) and the type of f must be (b -> c) (both b are the same type variable!). What you want to apply both functions to the same argument and join the results with &&. There's no existing functions for this as far as I know (at least Hoogle didn't find anything for (a -> Bool) -> (a -> Bool) -> a -> Bool). You'll have to make your own:

both f g x = f x && g x

Alternatively, you coudl just stick to filtering twice (which isn't as bad as it sounds thanks to lazy evaluation) - filter (>1) $ filter (<10) xs.

Answer 6

As i understand it, it works by performing the functions b . a on alphabetical order and returning the result. In other words x = foo a and then foo b of x

This could be written in Haskell as

let x = foo a in 
foo b x

(where does foo come from?) but the correct

(b . a) x = let y = a x in
            b y

Or, shorter:

(b . a) x = b (a x)

Now, filter lessThanTen (filter greaterThanOne xs) has a similar shape to the right side of this definition, if you remember you could write it as (filter lessThanTen) ((filter greaterThanOne) xs):

((filter lessThanTen) . (filter greaterThanOne)) xs

Presumably what you actually want is filter ??? xs, but that should be enough to go on with.

Answer 7

You have it almost right. I find the easiest way to start learning function composition with . is to use $ first instead.

So you have a list

twoFilters xs = xs

You want to filter by greaterThanOne

twoFilters xs = filter greaterThanOne $ xs

You additionally want to filter by lessThanTen

twoFilters xs = filter lessThanTen $ filter greaterThanOne $ xs

Now move from left to right, replacing all $s with . except for the last $

twoFilters xs = filter lessThanTen . filter greaterThanOne $ xs

You could use parenthesis instead of $ now:

twoFilters xs = (filter lessThanTen . filter greaterThanOne) xs

Or just define the function pointfree:

twoFilters = filter lessThanTen . filter greaterThanOne

The parenthesized version is the most important, I think. It shows that you fuse the two partially-applied functions filter lessThanTen and filter greaterThanOne into one mega-filtering function, with . and then you apply the list to it. You need to parenthesize them because . binds less tightly than function application via whitespace (space can be considered an uber-high-fixity version of $). Remember, when you use ., you are fusing two functions together to form one mega-function.

It is relevant to inspect the type signature of .

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

The functions you feed it have to "line up" with very particular type signatures (they have to be compatible for fusing). But honestly, the key is learning to recognize when function application (with space) is binding more tightly than you intend and messing up the type signatures of functions you are trying to compose. That's how it was for me, anyways.