[Haskell-cafe] Point-free style

Daniel Fischer daniel.is.fischer at web.de
Mon Feb 14 05:07:48 EST 2005


Am Montag, 14. Februar 2005 01:24 schrieb Tim Docker:
> Ketil Malde wrote:
>   >        (.) . (.) .(.)
>   >
>   > I entered it into GHCi, and got
>   >
>   >         :: forall a a b c a.
>   >
>   >               (b -> c) -> (a -> a -> a -> b) -> a -> a -> a -> c
>
> I spent a minute or so attempting to intuit the type signature of this,
> before cheating and entering it into ghci also.
>
> Is there a straightforward technique by which type signatures can be
> "hand calculated", or does one end up needing to run the whole inference
> algorithm in one's head?
>
> Tim

An aside first:
Shiqi Cao confused left and right, for (.) is infixr 9 -- it's associative in 
fact, so it doesn't matter for the result.

I'd just phrase the derivation differently:

In (.) . (.), the first (to be applied, that is, the right) (.) has -- what 
else ? -- the type

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

A) The type of the left (.) is an instance of the general type

(y -> z) -> ((x -> y) -> (x -> z)),

with the input type (y -> z) being the output type of the right (.), so we 
find
y -> z === (a -> b) -> (a -> c),
i.e.

y = a -> b
z = a -> c

and x completely arbitrary, hence the type of (.) . (.) is

inputTypeOfRight(.) -> OutputTypeOfLeft(.), 
(b -> c) -> ((x -> y) -> (x -> z)), which we determined as

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

Now rename and drop unnecessary parentheses to get the type

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

To get the type of (.) . (.) . (.), insert this type into A) to find

y = a -> a1 -> b
z = a -> a1 -> c, hence the type of (.) .(.) . (.) is

(b -> c) -> (a2 -> a1 -> a -> b) -> (a2 -> a1 -> a -> c).

-- here is the point where nested parentheses would really obscure rather than 
clarify, in handwriting or LaTeX, different sizes could take care of that. 

Now iteration of the process should be clear.

A question for the point-free society:
Is there any advantage of defining

(.<) = (.) . (.)

rather than

f .< g = \x y -> f (g x y)      -- or f $ g x y ?

Analogous question for (.) . (.) . (.) etc.

And could one define

\f g h x y -> f (g x) (h y)

point-free? I can get rid of x and y by

co2 f g h = flip (flip (f . g) . h),

but that's not satisfactory.

Daniel


More information about the Haskell-Cafe mailing list