Function composition and currying

K. Fritz Ruehr fruehr@willamette.edu
Wed, 16 Jul 2003 23:19:55 -0700 (PDT)


I think the cutest way to get what you want here is to define a new
operator as follows:

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

(the choice of symbol is supposed to suggest this new form of
composition with "two prongs" on the right). Then you can use it as
follows, for example:

    f x = x * x

    g a b = a + b

    y = (f .< g) 1 2

I noticed this one day while playing around with a definition like the
one you gave, in terms of curry and uncurry, trying to express it in a
more points-free style.

But Jerzy Karczmarczuk enlightened me as to the full generality possible
along these lines (revealing the whole truth under the influence of at
least one beer, as I recall). Namely, one can define a sequence of
functions (let's use a better notation now, with "c" for composition):

    c1 = (.)                      -- good old composition

    c2 = (.) . (.)                -- my (.<) from above

    c3 = (.) . (.) . (.)

    c4 = (.) . (.) . (.) . (.)

    -- etc.

Each of these gives an appropriate generalization allowing the
composition of a one-argument function with an n-argument one (similar
to the notations used in the usual definitions for primitive recursive
function). That is to say, the types are as follows (the middle three
dots on the second line are an ellipsis, apologies in advance):

    cn :: (a -> b) -> F(t,n,a) -> F(t,n,b)

    cn  = (.)  .  ...  .  (.)      -- n occurrences of (.)

where the awkward phrase "F(t,n,x)" expands as follows via some imagined
macro facility.

    F(t,n,x)  ===  t1 -> t2 -> ... -> tn -> x

(I use a Phi operator, a la type- theoretic Sigma or Pi, when I write
these things out in the privacy of my own home.)

By the way, there is in general a real need to be able to abstract over
these n's, e.g. for zip and relatives as well. I tried unsuccessfully to
do this for my dissertation, Mark Tullsen did a much better job in his,
and various other people have explored other ways (I imagine that Conor
McBride could show us how the use of full dependent types would solve
the problem once and for all, perhaps in his Epigram language).

Of course, what we really want to do is to express this as a fold of
composition over a dynamically generated list of compositions, i.e.:

    c n = foldr (.) id (take n (repeat (.)))

But I think giving this a nice general type, where n is a run-time
argument and the replicated (.)s have distinct but related types,
is quite difficult.

  --  Fritz Ruehr

> Hi,
>
> Hopefully this is a simple question.  I am wanting to know good ways
> of using ".", the function composition operator, when dealing with
> currying functions.
>
> Suppose I have the following functions defined:
>
>   f :: Int -> Int
>   f x = x*x
>
>   g :: Int -> Int -> Int
>   g a b = a + b
>
> ...
>
> But what I really want is a function with signature Int -> Int -> Int.
> The answer is probably:
>
>   (curry (f.(uncurry g))) 1 2
>
> but this seems awfully messy just to do f (g 1 2).
>
> And what if g were a function with three curried arguments?  Then
> uncurry and curry wouldn't apply.  What then?
>
> Is there a better way?
>
> Thanks,
>
> Mark.
>
>
> --
> Dr Mark H Phillips
> Research Analyst (Mathematician)
>
> AUSTRICS - smarter scheduling solutions - www.austrics.com
>
> Level 2, 50 Pirie Street, Adelaide SA 5000, Australia
> Phone +61 8 8226 9850
> Fax   +61 8 8231 4821
> Email mark@austrics.com.au