Does Function Composition rely on Partial Application?

Question

Does Function Composition rely on Partial Application?

Here's my understanding:

Observe the following functions that have some duplication of function calls:

let updateCells (grid:Map<(int * int), Cell>) =

    grid |> Map.toSeq
         |> Seq.map snd
         |> Seq.fold (fun grid c -> grid |> setReaction (c.X, c.Y)) grid

let mutable _cells = ObservableCollection<Cell>( grid |> Map.toSeq
                                                      |> Seq.map snd
                                                      |> Seq.toList )
let cycleHandler _ = 

    self.Cells <- ObservableCollection<Cell>( grid |> cycleThroughCells
                                                   |> Map.toSeq
                                                   |> Seq.map snd
                                                   |> Seq.toList )

If you’ve noticed, the following code appears in all three functions:

grid |> Map.toSeq
     |> Seq.map snd

Function Composition

Within functional programming, we can fuse functions together so that they can become one function.

To do this, let’s create a new function from the duplicated sequence of functions:

let getCells = Map.toSeq >> Seq.map snd >> Seq.toList

Now if you’re attentive, you will have noticed that we don’t use any arguments when using Function Composition. Hence, the grid value is not used. The reason behind this is because of Partial Application.

Partial Application

I’m still learning all these functional programming techniques. However, my understanding is that partial application is a technique within functional programming that postpones the need to accept a complete set of arguments for a given function. In other words, partial application is the act of deferring the acceptance of a complete set of arguments for a given function in which there is an expectation that the end-client will provide the rest of the arguments later. At least, that’s my understanding.

We can now take a function like:

let updateCells (grid:Map<(int * int), Cell>) =

    grid |> Map.toSeq
         |> Seq.map snd
         |> Seq.fold (fun grid c -> grid |> setReaction (c.X, c.Y)) grid

And refactor it to something like:

let updateCells (grid:Map<(int * int), Cell>) =

    grid |> getCells
         |> Seq.fold (fun grid c -> grid |> setReaction (c.X, c.Y)) grid

Are my thoughts regarding Function Composition being coupled with Partial Application accurate?

Answer 1

Generics

Actually, if you take the expression

let getCells = Map.toSeq >> Seq.map snd >> Seq.toList

and attempt to compile it as a stand-alone expression, you'll get a compiler error:

error FS0030: Value restriction. The value 'getCells' has been inferred to have generic type val getCells : (Map<'_a,'_b> -> '_b list) when '_a : comparison
Either make the arguments to 'getCells' explicit or, if you do not intend for it to be generic, add a type annotation.

The reason it works in your case is because you're using the getCells function with grid, which means that the compiler infers it to have a constrained type.

In order to keep it generic, you can rephrase it using an explicit argument:

let getCells xs = xs |> Map.toSeq |> Seq.map snd |> Seq.toList

This expression is a valid stand-alone expression of the type Map<'a,'b> -> 'b list when 'a : comparison.

Point-free

The style used with the >> function composition operator is called point-free. It works well with partial application, but isn't quite the same.

Application

There is, however, an example of partial function application in this example:

let getCells xs = xs |> Map.toSeq |> Seq.map snd |> Seq.toList

The function snd has the following type:

'a * 'b -> 'b

It's function that takes a single argument.

You could also write the above getCells function without partial application of the snd function:

let getCells xs = xs |> Map.toSeq |> Seq.map (fun x -> snd x) |> Seq.toList

Notice that instead of a partially applied function passed to Seq.map, you can pass a lambda expression. The getCells function is still a function composed from other functions, but it no longer relies on partial application of snd.

Thus, to partially (pun intended) answer your question: function composition doesn't have to rely on partial function composition.

Currying

In F#, functions are curried by default. This means that all functions take exactly one argument, and returns a value. Sometimes (often), the return value is another function.

Consider, as an example, the Seq.map function. If you call it with one argument, the return value is another function:

Seq.map snd

This expression has the type seq<'a * 'b> -> seq<'b>, because the return value of Seq.map snd is another function.

Eta reduction

This means that you can perform an Eta reduction on the above lambda expression fun x -> snd x, because x appears on both sides of the expression. The result is simply snd, and the entire expression becomes

let getCells xs = xs |> Map.toSeq |> Seq.map snd |> Seq.toList

As you can see, partial application isn't necessary for function composition, but it does make it much easier.

Impartial

The above composition using the pipe operator (|>) still relies on partial application of the functions Map.toSeq, Seq.map, etcetera. In order to demonstrate that composition doesn't rely on partial application, here's an 'impartial' (the opposite of partial? (pun)) alternative:

let getCells xs =
    xs
    |> (fun xs' -> Map.toSeq xs')
    |> (fun xs' -> Seq.map (fun x -> snd x) xs')
    |> (fun xs' -> Seq.toList xs')

Notice that this version makes extensive use of lambda expressions instead of partial application.

I wouldn't compose functions in this way; I only included this alternative to demonstrate that it can be done.

Answer 2

Composition depends on first-class functions, not really on partial applications.

What is required to implement composition is that:

• Functions must be able to be taken as arguments and returned as return values
• Function signatures must be valid types (if you want the composition to be strongly-typed)

Partial application creates more opportunities for composition, but in principle you can easily define function composition without it.

For example, C# doesn't have partial application*, but you can still compose two functions together, as long as the signatures match:

Func<a, c> Compose<a, b, c>(this Func<a, b> f, 
                            Func<b, c> g) 
{
    return x => g(f(x));
}

which is just >> with an uglier syntax: f.Compose(g).

However, there is one interesting connection between composition and partial application. The definition of the >> operator is:

let (>>) f g x = g(f(x))

and so, when you write foo >> bar, you are indeed partially applying the (>>) function, ie omitting the x argument to get the fun x = g(f(x)) partial result.

But, as I said above, this isn't strictly necessary. The Compose function above is equivalent to F#'s >> operator and doesn't involve any partial application; lambdas perform the same role in a slightly more verbose way.

---

* Unless you manually implement it, which nobody does. I.e. instead of writing

string foo(int a, int b) 
{ 
    return (a + b).ToString(); 
}

you'd have to write

Func<int, string> foo(int a) 
{ 
    return b => (a + b).ToString(); 
}

and then you'd be able to pass each argument separately just like in F#.

Answer 3

This is more of comment than an answer because it is to large for a comment.

The way I pull arguments off of the stack is to use the fun keyword.

// Standard function with arguments
let add1 x y  = x + y

// Function defining no arguments.  
// I think of the arguments x and y as being on the stack.
let add2 = (+)

// Function defining no arguments.  
// I think of the arguments x and y as being on the stack 
// and being given the names x and y.
let add3 = fun x y -> x + y

let result1 = add1 1 2
printfn "add1: %A" result1

let result2 = add2 1 2
printfn "add2: %A" result2

let result3 = add3 1 2
printfn "add3: %A" result3

when sent to F# interactive produces

val add1 : x:int -> y:int -> int

val add2 : (int -> int -> int)

val add3 : x:int -> y:int -> int

val result1 : int = 3
add1: 3
val it : unit = ()

val result2 : int = 3
add2: 3
val it : unit = ()

val result3 : int = 3
add3: 3
val it : unit = ()

and another example using the function keyword

let charType =
    function
    | n when n >= '0' && n <= '9' -> "number"
    | l when l >= 'a' && l <= 'z' -> "lower case"
    | u when u >= 'A' && u <= 'Z' -> "upper case"
    | _ ->  "other"

let result4 = charType '0'
printfn "charType '0': %A" result4