make function with 'if' point-free

Question

I have a task in Haskell (no, it's not my homework, I'm learning for exam).

The task is:

Write point-free function numocc which counts occurrences of element in given lists. For example: numocc 1 [[1, 2], [2, 3, 2, 1, 1], [3]] = [1, 2, 0]

This is my code:

addif :: Eq a => a -> Int -> a -> Int
addif x acc y = if x == y then acc+1 else acc

count :: Eq a => a -> [a] -> Int
count = flip foldl 0 . addif

numocc :: Eq a => a -> [[a]] -> [Int]
numocc = map . count

numocc and count are 'point-free', but they are using function addif which isn't.

I have no idea how can I do the function addif point-free. Is there any way to do if statement point-free? Maybe there is a trick which use no if?

Answer 1

I would use the fact that you can easily convert a Bool to an Int using fromEnum:

addif x acc y = acc + fromEnum (x == y)

Now you can start applying the usual tricks to make it point-free

-- Go prefix and use $
addif x acc y = (+) acc $ fromEnum $ (==) x y
-- Swap $ for . when dropping the last argument
addif x acc = (+) acc . fromEnum . (==) x

And so on. I won't take away all the fun of making it point free, especially when there's tools to do it for you.

Alternatively, you could write a function like

count x = sum . map (fromEnum . (==) x)

Which is almost point free, and there are tricks that get you closer, although they get pretty nasty quickly:

count = fmap fmap fmap sum map . fmap fmap fmap fromEnum (==)

Here I think it actually looks nicer to use fmap instead of (.), although you could replace every fmap with (.) and it would be the exact same code. Essentially, the (fmap fmap fmap) composes a single argument and a two argument function together, if you instead give it the name .: you could write this as

count = (sum .: map) . (fromEnum .: (==))

Broken down:

> :t fmap fmap fmap sum map
Num a => (a -> b) -> [a] -> b

So it takes a function from b to a numeric a, a list of bs, and returns an a, not too bad.

> :t fmap fmap fmap fromEnum (==)
Eq a => a -> a -> Int

And this type can be written as Eq a => a -> (a -> Int), which is an important thing to note. That makes this function's return type match the input to fmap fmap fmap sum map with b ~ Int, so we can compose them to get a function of type Eq a => a -> [a] -> Int.