DISCOVERY

May 28th, 2019

Haskell Part VI: Functors

Haskell

Java

Functional Programming

Right now I'm learning Haskell, a functional programming language. In my last few Haskell articles I've discussed basic aspects of the language. Now I've begun digging into advanced functional programming concepts. This article discusses functors, a generic way to map functions over objects.

A common pattern in programming is looping through a collection of values and applying a transformation to each. For example, a programmer might loop through a list of integers and increment each value. The imperative approach to this transformation sets up a for loop and iterates over each list index. The functional approach uses the map higher-order function. map accepts two arguments - a collection to iterate over and a function. The function is applied to each item in the collection.

Haskell has a map function defined in the GHC Prelude module1. It accepts a list and a function as arguments.

map :: (a -> b) -> [a] -> [b] map _ [] = [] map f (x:xs) = f x : map f xs

With the map function, list items can be transformed. A basic example is incrementing each item in the list.

main :: IO () main = do print $ map (+1) [1,2,3] -- [2,3,4]

Haskell's map function is useful, however its restricted to just a list data structure. The concept of applying a function across all items in a data structure can be generalized even more than the map function. This is where functors come into play.

Functor

In Haskell (and functional programming in general), a functor provides the ability to map a function across all the items in a data structure or object2. Functors in Haskell are defined by a Functor type class. Types that are instances of Functor implement a function called fmap, which provides mapping functionality.

The Functor type class definition is simple:

class Functor f where fmap :: (a -> b) -> f a -> f b

fmap is a curried function that takes in another function [(a -> b)] and a value whose type is an instance of Functor [f a] as arguments. fmap passes f a to the function (a -> b), resulting in b.

The most basic functor instance is for the list type3.

instance Functor [] where -- fmap :: (a -> b) -> [a] -> [b] fmap = map

For lists, fmap is implemented the same as map. Therefore, it behaves as expected.

main :: IO () main = do print $ fmap (+1) [1,2,3] -- [2,3,4] print $ fmap (*2) [1,2,3] -- [2,4,6] print $ fmap show [1,2,3] -- ["1","2","3"]

The great thing about functors is any parameterized type in Haskell can be made an instance of Functor. For example, the Maybe type which defines a potentially non-existant value can become a functor.

data Maybe a = Nothing | Just a instance Functor Maybe where -- fmap :: (a -> b) -> Maybe a -> Maybe b fmap _ Nothing = Nothing fmap g (Just x) = Just (g x) main :: IO () main = do print $ fmap (+1) (Just 5) -- Just 6 print $ fmap (+1) Nothing -- Nothing print $ fmap (*3) (Just 5) -- Just 15 print $ fmap (*3) Nothing -- Nothing

Custom types can also become functors. For example, my custom Distance type is easily made an instance of Functor.

data Distance a = Miles a | Kilometers a | Meters a deriving (Show, Read) -- Make the 'Distance' type into a Functor instance Functor Distance where -- fmap :: (a -> b) -> Distance a -> Distance b fmap f (Miles x) = Miles (f x) fmap f (Kilometers x) = Kilometers (f x) fmap f (Meters x) = Meters (f x) main :: IO () main = do print $ fmap (+1) (Miles 4.38) -- Miles 5.38 print $ fmap (+1) (Kilometers 7.05) -- Kilometers 8.05 print $ fmap (+1) (Meters 7005) -- Meters 7006 print $ fmap (*3) (Miles 1) -- Miles 3

Distance is a valid functor instance because its data definition is parameterized and it has a type constructor. You can think of Distance as a container type, since it holds a value such as a floating point number. Lists and the Maybe type have similar structures. Types without a parameterized data definition are not valid functors because they don't contain another type4.

Functors are useful for mapping functions across all items contained in an object. They become even more useful in regards to Applicatives and Monads, which I will discuss in upcoming articles.

For now, one last useful functor implementation is a generic function for all instances of Functor to utilize. With the help of a Functor class constant, a function is easily created to increment the items in any Functor instance5.

inc :: Functor f => f Int -> f Int inc x = fmap (+1) x main :: IO () main = do print $ inc [1,2,3] -- [2,3,4] print $ inc (Just 5) -- Just 6 print $ inc Nothing -- Nothing print $ inc (Miles 3) -- Miles 4

Any type that is an instance of Functor can utilize the inc function! This is a really powerful design pattern for function reuse.

The concept of functors isn't limited to Haskell or functional programming. In Java, the Functor type class is represented as an interface6.

public interface Functor<T> { /** * Map a function to values wrapped inside the Functor instance * @param f A function that is applied to the Functor * @param <R> The generic type that will be wrapped in the Functor return value * @return A new instance of Functor */ <R> Functor<R> fmap(Function<T, R> f); }

Classes can implement the Functor interface. This is comparable to creating an instance of the Functor type class in Haskell. The following class creates a list that is also a functor.

public class FList<T> implements Functor<T> { // The FList class uses composition to hold an instance of a List object private List<T> list; /** * Construct an FList object with any iterable collection. Converts the Iterable to a List. * @param iterable - Iterable collection used as the contents of the FList */ public FList(Iterable<T> iterable) { list = new ArrayList<>(); iterable.forEach(list::add); } /** * {@inheritDoc} */ @Override public <R> FList<R> fmap(Function<T, R> f) { List<R> newList = list.stream().map(f).collect(toList()); return new FList<>(newList); } /** * Retrieve the internal list object * @return The Generic list */ public List<T> getList() { return list; } }

Class FList has a concrete implementation of fmap() as required by the Functor interface. For the sake of another example, the following class defines a functor for a pair of values.

public class FPair<T> implements Functor<T> { // The FPair object contains two values of matching types private T item1; private T item2; /** * Construct a pair based on two values of the same type. * @param item1 The first value * @param item2 The second value */ public FPair(T item1, T item2) { this.item1 = item1; this.item2 = item2; } /** * {@inheritDoc} */ @Override public <R> FPair<R> fmap(Function<T, R> f) { return new FPair<>(f.apply(item1), f.apply(item2)); } /** * Get the internal objects and return them as a list * @return A list containing two objects */ public List<T> getPair() { return List.of(item1, item2); } }

The following code confirms that the functors behave as expected when invoking fmap().

public static void main(String... args) { // Testing the Functor implementation of a List FList<Integer> fList = new FList<>(List.of(1,2,3,4)); fList = fList.fmap(x -> x * 2) .fmap(x -> x + 1); List<Integer> list = fList.getList(); assert list.size() == 4; assert list.toString().equals("[3, 5, 7, 9]"); // Testing the Functor implementation of a Pair FPair<Double> fPair = new FPair<>(0.1, 0.2); fPair = fPair.fmap(x -> x + 1) .fmap(x -> x * 2) .fmap(x -> x / 2); List<Double> pairList = fPair.getPair(); assert pairList.size() == 2; assert pairList.toString().equals("[1.1, 1.2]"); }

For completeness, here is the generic inc() function for functors in Java.

static Functor<Integer> inc(Functor<Integer> functor) { return functor.fmap(x -> x + 1); } public static void main(String... args) { // inc() works on lists... FList<Integer> fList2 = new FList<>(List.of(5,6,7,8)); fList2 = (FList<Integer>) inc(fList2); List<Integer> list2 = fList2.getList(); assert list2.size() == 4; assert list2.toString().equals("[6, 7, 8, 9]"); // ...and on pairs of objects FPair<Integer> fPair2 = new FPair<>(1,2); fPair2 = (FPair<Integer>) inc(fPair2); List<Integer> pairList2 = fPair2.getPair(); assert pairList2.size() == 2; assert pairList2.toString().equals("[2, 3]"); }

The same functor pattern works in many different languages!

Working with a functional programming language forces the brain to think about common problems differently. While initially difficult to reason about, functors simply provide a mechanism for mapping a function across different items. Functors also promote the creation of generic code which works for many different types. In my next article I'll build on this knowledge and explore applicatives. All the code from this article is available on GitHub.

[1] "GHC.Base map", https://bit.ly/2YO30Cq

[2] "In Functional Programming, what is a functor?", https://stackoverflow.com/a/2031421

[3] Graham Hutton, Programming in Haskell, 2nd ed (Cambridge, UK: Cambridge University Press, 2016), 154

[4] "Custom Functor instance: Expected kind...", https://stackoverflow.com/a/45235908

[5] Hutton., 156

[6] "Functional Programming in Pure Java: Functor and Monad Examples", https://dzone.com/articles/functor-and-monad-examples-in-plain-java