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 use the somewhat funny-looking (.).(.) combinator:

Prelude> :set -XNoMonomorphismRestriction
Prelude> :m + Data.List
Prelude Data.List> let f = ((.).(.)) nub (++)
Prelude Data.List> :t f
f :: Eq a => [a] -> [a] -> [a]
Prelude Data.List> f "ab" "ac"
"abc"

It's probably gonna be more readable to just use a lambda or an auxilliary function in a where-clause, though.

Answer 2

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 3

I don't think the composition operator you want exists as a single function in any standard library. The shortest way to write it is probably ((.).(.)). Using the Functor definition for ((->) t), you can also write it as fmap . fmap or, if you prefer fmap fmap fmap.

All of the above are pretty cryptic, but the idiom is common enough that many people will recognize what you're doing.

By the way, you may want to avoid calling functions of two arguments "dyadic" in Haskell, because if you extend that terminology to functions of one argument you're going to really confuse people.

See also this question for some related discussion.

You can also find lots of combinators with very intuitive names in this library.

Answer 4

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)

Answer 5

This problem is solved in a particularly simple and beautiful way by semantic editor combinators. Confer:

• Conal Elliott's original article
• An SO answer to a similar question introducing them

Your final composition would look like:

(result.result) nub (++)