Is it ok to say higer order functions (map, filter ...) achieve polymorphism?

Question

map(array, f)

I thought higher order functions are polymorphic. Since that operates in many ways. But when I have searched about polymorphism, there was no such thing like 'anonymous functions or higher order functions are polymorphic'.

Although the variable f does various operations and the f is an interface which takes each value in an array as a parameter, It's not polymorphic?

Is it only about types?

I thought like something operates in various ways is polymorphic. like function overloading in C++

Is it wrong to say like that in CS ?

In my view, subtype polymorphism is quite similar with higher order functions.

Answer 1

There's this lovely parable of Anton van Straaten's that likens objects to closures.

Functions

Consider a function. Let's make it concrete and say that it receives a string and returns an integer. (It might, for example, count the number of letters in the string.) In Haskell, such a function might have the type String -> Int.

If you have a higher-order function like the typical functor map (as I assume the OP function represents), you can use any String -> Int function to map a collection of strings to a collection of integers:

ghci> map length ["foo", "bar", "b", "az"]
[3,3,1,2]

You could also write another function with the same type. Let's say, for example, that you wanted to count all the occurrences of a particular character in a string.

ghci> countOccurencesOf ch = length . filter ((==) ch)
ghci> countOccurencesOf 'a' "bar"
1
ghci> countOccurencesOf 'a' "bara"
2
ghci> countOccurencesOf 'b' "bara"
1

This function takes two inputs: a character and a string, but if you partially apply it, you create a new function that takes only a string. This is very similar to a closure.

Such a closure can also be used with the same map function:

ghci> map (countOccurencesOf 'r') ["foo", "bar", "brr"]
[0,1,2]

Thus, it seems reasonable to consider the function input into map as being polymorphic.

Objects

Since objects are isomorphic to closures, we can demonstrate the same idea using objects.

Imagine that we have a mapper over collections. I'll now use C#.

Keeping it concrete, imagine that we define a function that only maps collections of string to collections of integers:

public static IEnumerable<int> Map(IEnumerable<string> source, StringToIntMapping mapping)
{
    var result = new List<int>();
    foreach (var s in source)
    {
        result.Add(mapping.Map(s));
    }
    return result;
}

where StringToIntMapping is an abstract base class:

public abstract class StringToIntMapping
{
    public abstract int Map(string s);
}

You can now repeat the same examples as above by passing polymorphic objects to the Map function. Here, the examples are given as unit tests:

[Fact]
public void CountLetters()
{
    var collection = new[] { "foo", "bar", "b", "az" };
    var actual = Map(collection, new CountLettersMapping());
    Assert.Equal(new[] { 3, 3, 1, 2 }, actual);
}

[Fact]
public void CountOccurences()
{
    var collection = new[] { "foo", "bar", "brr" };
    var actual = Map(collection, new CountOccurencesMapping('r'));
    Assert.Equal(new[] { 0, 1, 2 }, actual);
}

The two polymorphic objects used here are two derived classes:

public sealed class CountLettersMapping : StringToIntMapping
{
    public override int Map(string s)
    {
        return s.Length;
    }
}

public sealed class CountOccurencesMapping : StringToIntMapping
{
    private readonly char c;

    public CountOccurencesMapping(char c)
    {
        this.c = c;
    }

    public override int Map(string s)
    {
        return s.Count(x => x == c);
    }
}

You could now introduce generics to support mapping of any two types:

public static IEnumerable<TResult> Map<T, TResult>(
    IEnumerable<T> source,
    Mapping<T, TResult> mapping)
{
    var result = new List<TResult>();
    foreach (var s in source)
    {
        result.Add(mapping.Map(s));
    }
    return result;
}

public abstract class Mapping<T, TResult>
{
    public abstract TResult Map(T t);
}

In statically typed functional programming languages like Haskell, generics are often called parametric polymorphism. That's a different kind of polymorphism.