Point-free style and using $

Question

How does one combine using $ and point-free style?

A clear example is the following utility function:

times :: Int -> [a] -> [a]
times n xs = concat $ replicate n xs  

Just writing concat $ replicate produces an error, similarly you can't write concat . replicate either because concat expects a value and not a function.

So how would you turn the above function into point-free style?

Answer 1

In Haskell, function composition is associative¹:

f . g . h == (f . g) . h == f . (g . h)

Any infix operator is just a good ol' function:

2 + 3 == (+) 2 3
f 2 3 = 2 `f` 3

A composition operator is just a binary function too, a higher-order one, it accepts 2 functions and returns a function:

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

Therefore any composition operator can be rewritten as such:

f . g == (.) f g
f . g . h == (f . g) . h == ((.) f g) . h == (.) ((.) f g) h
f . g . h == f . (g . h) == f . ((.) g h) == (.) f ((.) g h)

Every function in Haskell can be partially applied due to currying by default. Infix operators can be partially applied in a very concise way, using sections:

(-) == (\x y -> x - y)
(2-) == (-) 2 == (\y -> 2 - y)
(-2) == flip (-) 2 == (\x -> (-) x 2) == (\x -> x - 2)
(2-) 3 == -1
(-2) 3 == 1

As composition operator is just an ordinary binary function, you can use it in sections too:

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

Another interesting binary operator is $, which is just function application:

f x == f $ x
f x y z == (((f x) y) z) == f x y z
f(g(h x)) == f $ g $ h $ x == f . g . h $ x == (f . g . h) x

With this knowledge, how do I transform concat $ replicate n xs into point-free style?

times n xs = concat $ replicate n xs
times n xs = concat $ (replicate n) xs
times n xs = concat $ replicate n $ xs
times n xs = concat . replicate n $ xs
times n    = concat . replicate n
times n    = (.) concat (replicate n)
times n    = (concat.) (replicate n) -- concat is 1st arg to (.)
times n    = (concat.) $ replicate n
times n    = (concat.) . replicate $ n
times      = (concat.) . replicate

¹^{Haskell is based on category theory. A category in category theory consists of 3 things: some objects, some morphisms, and a notion of composition of morphisms. Every morphism connects a source object with a target object, one-way. Category theory requires composition of morphisms to be associative. A category that is used in Haskell is called Hask, whose objects are types and whose morphisms are functions. A function f :: Int -> String is a morphism that connects object Int to object String. Therefore category theory requires Haskell's function compositions to be associative.}

Answer 2

You can use this combinator: (The colon hints that two arguments follow)

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

It allows you to get rid of the n:

time = concat .: replicate

Answer 3

You can easily write an almost point-free version with

times n  =  concat . replicate n

A fully point-free version can be achieved with explicit curry and uncurry:

times  =  curry $ concat . uncurry replicate

Answer 4

Get on freenode and ask lambdabot ;)

<jleedev> @pl \n xs -> concat $ replicate n xs
<lambdabot> (join .) . replicate

Answer 5

By extending FUZxxl's answer, we got

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

(.::) :: (d -> e) -> (a -> b -> c -> d) -> a -> b -> c -> e
(.::) = (.).(.:)

(.:::) :: (e -> f) -> (a -> b -> c -> d -> e) -> a -> b -> c -> d -> f
(.:::) = (.).(.::)

...

Very nice.

Bonus

(.:::) :: (e -> f) -> (a -> b -> c -> d -> e) -> a -> b -> c -> d -> f
(.:::) = (.:).(.:)

Emm... so maybe we should say

(.1) = .

(.2) :: (c -> d) -> (a -> b -> c) -> a -> b -> d
(.2) = (.1).(.1)

(.3) :: (d -> e) -> (a -> b -> c -> d) -> a -> b -> c -> e
(.3) = (.1).(.2)
-- alternatively, (.3) = (.2).(.1)

(.4) :: (e -> f) -> (a -> b -> c -> d -> e) -> a -> b -> c -> d -> f
(.4) = (.1).(.3)
-- alternative 1 -- (.4) = (.2).(.2)
-- alternative 2 -- (.4) = (.3).(.1)

Even better.

We can also extend this to

fmap2 :: (Functor f, Functor g) => (a -> b) -> f (g a) -> f (g b)
fmap2 f = fmap (fmap f)

fmap4 :: (Functor f, Functor g, Functor h, functro i) 
   => (a -> b) -> f (g (h (i a))) -> f (g (h (i b)))
fmap4 f = fmap2 (fmap2 f)

which follows the same pattern.

It would be even better to have the times of applying fmap or (.) parameterized. However, those fmap or (.)s are actually different on type. So the only way to do this would be using compile time calculation, for example TemplateHaskell.

For everyday uses, I would simply suggest

Prelude> ((.).(.)) concat replicate 5 [1,2]
[1,2,1,2,1,2,1,2,1,2]
Prelude> ((.).(.).(.)) (*10) foldr (+) 3 [2,1]
60