C++11 Support for Higher-Order List Functions

Dependency Inversion in OOP means that you code against an interface which is then provided by an implementation in an object.

Languages that support higher language functions can often solve simple dependency inversion problems by passing behaviour as a function instead of an object which implements an interface in the OO-sense.

In such languages, the function's signature can become the interface and a function is passed in instead of a traditional object to provide the desired behaviour. The hole in the middle pattern is a good example for this.

It let's you achieve the same result with less code and more expressiveness, as you don't need to implement a whole class that conforms to an (OOP) interface to provide the desired behaviour for the caller. Instead, you can just pass a simple function definition. In short: Code is often easier to maintain, more expressive and more flexible when one uses higher order functions.

An example in C#

Traditional approach:

public IEnumerable<Customer> FilterCustomers(IFilter<Customer> filter, IEnumerable<Customers> customers)
{
    foreach(var customer in customers)
    {
        if(filter.Matches(customer))
        {
            yield return customer;
        }
    }
}

//now you've got to implement all these filters
class CustomerNameFilter : IFilter<Customer> /*...*/
class CustomerBirthdayFilter : IFilter<Customer> /*...*/

//the invocation looks like this
var filteredDataByName = FilterCustomers(new CustomerNameFilter("SomeName"), customers);
var filteredDataBybirthDay = FilterCustomers(new CustomerBirthdayFilter(SomeDate), customers);

With higher order functions:

public IEnumerable<Customer> FilterCustomers(Func<Customer, bool> filter, IEnumerable<Customers> customers)
{
    foreach(var customer in customers)
    {
        if(filter(customer))
        {
            yield return customer;
        }
    }
}

Now the implementation and invocation become less cumbersome. We don't need to supply an IFilter implementation anymore. We don't need to implement classes for the filters anymore.

var filteredDataByName = FilterCustomers(x => x.Name.Equals("CustomerName"), customers);
var filteredDataByBirthday = FilterCustomers(x => x.Birthday == SomeDateTime, customers);

Of course, this can already be done by LinQ in C#. I just used this example to illustrate that it's easier and more flexible to use higher order functions instead of objects which implement an interface.

You can roughly emulate map/filter by using foldRight (or foldLeft) with cons as the given reduction function. For example foldRight(f, L, initial) where L = [x,y,z] might be expanded to

f(x, f(y, f(z, initial)))

This means that you can't process x until you've processed f(z, initial) and then f(y, ...). You're creating a dependency that doesn't exist with map/filter.

As for map ordering...

(A) collection.map(a => a.map(b => ...))

(A) takes a collection and then applies the map function to each element, this implies that each element is a "mappable" collection. This inner map will then return the processed list (which is a list) and so each element of collection will remain a collection. This is how you would map a function onto each element of a list of lists, and the result would again be a list of lists.

(B) collection.map(a => ...).map(b => ...)

(B) processes each element of a list and forms those results into a new list. This list is then processed again with a second map function giving yet another list.

(A) is for processing the inner elements of a list ("sub-elements" if you like). (B) is for processing a list multiple times. If we write (B) concretely as

collection.map(a => f(a)).map(b => g(b))

we can see it is equivalent to

collection.map(a => g(f(a)))

It might help you to write them out as for loops. (A) will use embedded loops where as (B) will use two sequential loops.

This is not the difference between fold and unfold. Neither (A) nor (B) is a fold as the list structure present, however deeply nested, is preserved. Fold creates a scalar from a list, while unfold (not too familiar with it) takes a scalar and produces a list according to some rule.

EDIT: @Giorgio was right to suggest flatMap. It's an interesting variation on map. Let's say we're mapping a list of Xs to a list of Ys, so we pass map a function f:X->Y. Suppose we have another calculation g that takes an X but returns multiple Ys g:X->[Y]. In this case we would use flatMap. map takes the results of f and puts them into a list. flatMap takes the results of g and concatenates them together.

Ex. Say we have a list of lists L = [[1,2,3],[4,5,6]]

L.map(a => a.map(b => b * 2))

gives [[2,4,6],[8,10,12]]. But say we want each number doubled in one list, no sub-lists. Then we would call

L.flatMap(a => a.map(b => b * 2))

which gives [2,4,6,8,10,12]. Note that our inner function a => a.map(b => b * 2) takes and returns a list.