concept Map in category functional programming

This is an excerpt from Manning's book Functional Programming in C#: How to write better C# code. Login to get full access to this book.

An implementation of Map for IEnumerable can be written as follows.

Listing 4.1. Map applies a function to each element of the given IEnumerable

public static IEnumerable<R> Map<T, R> (this IEnumerable<T> ts, Func<T, R> f) { foreach (var t in ts) yield return f(t); }

copy

Map maps a list of T’s to a list of R’s by applying a function T → R to each element in the source list. Notice that in this implementation the results are packaged into an IEnumerable as a result of using the yield return statement.

Maybe you recognized that this is exactly the behavior you get when you call LINQ’s Select method. Indeed, Map can be defined in terms of Select:

public static IEnumerable<R> Map<T, R>
   (this IEnumerable<T> ts, Func<T, R> f)
   => ts.Select(f);

copy

This is potentially more efficient, because LINQ’s implementation of Select is optimized for some specific implementations of IEnumerable. The point is that I’m going to use the name Map, rather than Select, because Map is the standard terminology in FP, but you should consider Map and Select synonyms.

Listing 4.2. Definition of Map for Option

public static Option<R> Map<T, R> (this Option<T> optT, Func<T, R> f) => optT.Match( () => None, (t) => Some(f(t)));

copy

If the given option is None, Map will just return an Option of the expected return type in the None state. If it’s Some(t), where t is the wrapped value, it will feed t to the given function (T → R) and then lift the resulting value into a new Option. You can see this in figure 4.2.

Figure 4.2. Mapping a function over an Option

Intuitively, it can be useful to think of Option as a special kind of list that can either be empty (None) or contain exactly one value (Some). If you look at it in this light, it becomes very clear that the implementations of Map for Option and IEnumerable are consistent: the given function gets applied to all available inner values of the structure.

Implement Map for ISet<T> and IDictionary<K, T>. (Tip: start by writing down the signature in arrow notation.)

Implement Map for Option and IEnumerable in terms of Bind and Return.

This is an excerpt from Manning's book Functional Programming in Java: How functional techniques improve your Java programs. Login to get full access to this book.

This is an instance method of Map that returns a list of all the values in the map:

Listing 6.2. Using Option in a functional Map

11.2.1. Implementing Map

Functional trees, like the red-black tree you’ve developed, have the advantage of immutability, which allows you to use them in multithreaded environments without bothering about locks and synchronization. The next listing shows the interface of a Map that can be implemented using the red-black tree.

Not all tree operations have been delegated because some operations don’t make much sense in the current conditions. But you may need additional operations in some special use cases. Implementing these operations is easy: extend the Map class and add delegating methods. For example, you might need to find the object with the maximal or minimal key. Another possible need is to fold the map, perhaps to get a list of the contained values. Here’s an example of delegating the foldLeft method:

public <B> B foldLeft(B identity, Function<B,
        Function<MapEntry<K, V>, B>> f, Function<B, Function<B, B>> g) {
  return delegate.foldLeft(identity, b -> me -> f.apply(b).apply(me), g);
}

copy

Generally, folding maps occur in very specific use cases that deserve to be abstracted inside the Map class.

11.2.3. Using Map with noncomparable keys

The Map class is useful and relatively efficient, but it has a big disadvantage compared to the maps you may be used to: the keys must be comparable. The types used for keys are usually comparable, such as integers or strings, but what if you need to use a noncomparable type for the keys?