composition with dyadic operator?

Question

I want to do something fairly simple; I am using the operator (++) with Data.Map insertWith, and it works fine, but I want to eliminate duplicates in the value created, so want to compose it with nub.

I tried (nub (++)), (nub $ (++)), (nub . (++)), all to no avail, in that the type of (++) does not match the expected type of nub ( [a] ).

I could of course define an auxiliary function or a lambda, but I think that probably there is a composition which would be clearer.

Hints please!

Answer 1

You can write this as

((nub .) .) (++)

Example:

Prelude Data.List> ((nub .) .) (++) [1,2,3] [3,4,5]
[1,2,3,4,5]

In general, you have

(f . ) g x = f (g x) 
((f . ) . ) g x y = f (g x y) 
(((f . ) . ) . ) g x y z = f (g x y z) 
((((f . ) . ) . ) . ) g x y z v = f (g x y z v)
...

Here's the derivation of this identity for ((nub .) .):

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

(nub .) :: Eq a1 => (a -> [a1]) -> a -> [a1] 
(nub .) = \g x -> (nub (g x))

((nub .) .) :: Eq a2 => (a -> a1 -> [a2]) -> a -> a1 -> [a2]
((nub .) .) = ((\g x -> (nub (g x))) .) = (\g' x' -> (\g x -> (nub (g x))) (g' x'))
            = \g' x' x -> (nub ((g' x') x))

There is a nice article about this (and related) idioms, but it's in Russian :-(

Answer 2

What you want seems to be a composition of binary and unary functions, like this:

compose :: (c -> d) -> (a -> b -> c) -> (a -> b -> d)
compose unary binary a b = unary (binary a b)

And you ask for a point-free version (without mentioning of a and b variables). Let's try and eliminate them one by one. We'll start with b, using the fact that f (g x) = f . g:

compose unary binary a = unary . binary a

a is next. Let's desugar the expression first:

compose unary binary a = ((.) unary) (binary a)

And apply the same composition rule again:

compose unary binary = ((.) unary) . binary

This can be further written as:

compose unary = (.) ((.) unary)

Or even as

compose = (.) . (.)

Here, each (.) 'strips' an argument off the binary function and you need two of them because the function is binary. This idiom is very useful when generalised for any functor: fmap . fmap (note that fmap is equivalent to . when function is seen as a functor). This allows you to 'strip' any functor off, for example you can write:

incrementResultsOfEveryFunctionInTwoDimentionalList :: [[String -> Integer]] -> [[String -> Integer]]
incrementResultsOfEveryFunctionInTwoDimentionalList = fmap . fmap . fmap $ (+1)

So, your result becomes:

(fmap . fmap) nub (++)

Edit:

I think I have found the answer my brain was trying to reproduce: Haskell function composition operator of type (c→d) → (a→b→c) → (a→b→d)