Functional Thread 11 : Traversable Functors

[[)roi(]]

Previous Thread
In the last thread we explored algebraic data types and then creating a monadic implementation of a tagged union type in C#.

Index to other threads on functional programming:

• History of Functional Programming / Category Theory
• Category Theory for programmers
• Functional design approach to a problem
• Recursion, Composition, Pipe Forward, Higher Order Function, Side Effects
• Covariance / Contravariance, Reducers / Transducers
• Predictable State Engine
• Functions
• Exception Handling
• Lazy Transformations / Yoneda and Coyoneda
• Monadic Computations / Nullable
• Algebraic Data Types / Tagged Union Types
• Monadic Composition

Represents a class of data structures that conform with the Traversable Functor algebra which is a structure that can be traversed from left to right, performing an action on each element.

Reference:
Applicative Programming with Effects



The two main methods are:

traverse :: Applicative f => (a -> f b) -> t a -> f (t b)

Map each element of a structure to an action, evaluate these actions from left to right, and collect the results.

sequenceA :: Applicative f => t (f a) -> f (t a)

Evaluate each action in the structure from left to right, and and collect the results. For a version that ignores the results see sequenceA.

This will be a fairly code heavy thread, yet the usage difficulty isn't any more difficult when compared with functor's Map/Select method usage.

 

[[)roi(]]

Traversable Functors
We already have studied four of the five algebras that are typically used for data structure manipulation:

• Monoid -- Fold -- Linq's Aggregate
• Functor -- Map -- Linq's Select
• Applicative Functor -- Apply -- Linq's does not include this.
• Monad -- FlatMap -- Linq's SelectMany

The fifth one is Traversable. To traverse means to walk across, and that is exactly what Traversable generalises: walking across a structure, collecting results at each stop.

Traverse resembles the mapping functions we have seen in other data types, however rather than using its function argument to insert functorial contexts under the original structure; as might be done with Map / Select, or to modify the structure as FlatMap / SelectMany does.

Traverse essentially adds an extra layer of context on the top of the structure, which allows for effectful traversals − traversals which produce an overall effect (i.e. a new outer layer of context).


Data types encapsulating Data types
Traversable is used more typically adjacent to Applicative Functor and Monadic processes, where the transitory state of variable is a Monadic Data type that encapsulates another Monadic data type, for example; let's assume we are using the Maybe type as our monadic composition type to hold a state that is either a valid value (Just) or null (Nothing). Now imagine one of the monadic functions returning a List of something; a database query response, or a deserialised web API -- our end result would be a Maybe encapsulating a List; a data type encapsulating another data type.

Code Example:

var r = Just(List(1, 2, 3, 4, 5, 6));
// Maybe<List<int>>[List<int>[ 1, 2, 3, 4, 5, 6 ]];

To access and / or transform the values is a bit awkward, because we need to first evaluate the outer Maybe before we can iterate over the integers contained in the List.

This is a scenario where Traverse can make things a little easier by inverting the data types.

var r = Just(List(1, 2, 3, 4, 5, 6));
// Maybe<List<int>>[List<int>[ 1, 2, 3, 4, 5, 6 ]];

var traversedR = r.Traverse(x => x);
// List<<Maybe<int>>[Maybe<int>[1], Maybe<int>[2], Maybe<int>[3], Maybe<int>[4], Maybe<int>[5], Maybe<int>[6]]

Now we can easily iterate over traverseR; the x => x computation is btw the Id function, meaning we can replace that with a point-free version, e.g.

var traversedR = r.Traverse(Id);
// List<<Maybe<int>>[Maybe<int>[1], Maybe<int>[2], Maybe<int>[3], Maybe<int>[4], Maybe<int>[5], Maybe<int>[6]]

Considering that the need to invert the outer and inner data types is a frequently used operation; the FP implementation will typically implement this as a separate operation called Sequence, which is the same as executing Traverse with the Id function, for example:

var traversedR = r.Traverse(Id);
var sequenceR = r.Sequence();

traverseR and sequenceR results are isomorphic.


Traverse is not limited to just inversion
As mentioned previously Traverse is a functor; or more specifically a functor that not only facilitates inversion of inner and outer data type, it also facilitates effectful traversals with it's higher order function parameter, for example we can not only invert the data types, we can also choose to, as example, filter out the even integers:

var r = Just(List(1, 2, 3, 4, 5, 6));
var evenTraversedR  = r.Traverse(x => x.FlatMap(y => (y % 2 == 0) ? List(y) : List<int>())).ToList();

// List<<Maybe<int>>[Maybe<int>[2], Maybe<int>[4], Maybe<int>[6]]

... and that's it... like our Map / Select method Traverse is a versatile higher order function for transformation of values contained in a datatype; with the added advantage of also inverting the inner and outer data types. We can of course also encapsulate our return type in another data type layer by using Map instead of FlatMap if so needed.

Next post; we'll review how this algebra has been implemented on our various FP data types.

 

[[)roi(]]

Traverse IEnumerable implementation with other data types

public static Maybe<IEnumerable<B>> Traverse<A, B>(this IEnumerable<A> @this, Func<A, Maybe<B>> f) => @this.Fold(Just(Enumerable.Empty<B>()), (a, e) => Just(Append<B>().Curry()).Apply(a).Apply(f(e)));
public static Identity<IEnumerable<R>> Traverse<A, R>(this IEnumerable<A> @this, Func<A, Identity<R>> f) => @this.Fold(Of(Enumerable.Empty<R>()), (a, e) => Of(Append<R>().Curry()).Apply(a).Apply(f(e)));
public static Result<IEnumerable<R>> Traverse<A, R>(this IEnumerable<A> @this, Func<A, Result<R>> f) => @this.Fold(Value(Enumerable.Empty<R>()), (a, e) => Value(Append<R>().Curry()).Apply(a).Apply(f(e)));
public static IO<IEnumerable<R>> Traverse<A, R>(this IEnumerable<A> @this, Func<A, IO<R>> f) => @this.Fold(Enumerable.Empty<R>().ToIO(), (a, e) => Append<R>().Curry().ToIO().Apply(a).Apply(f(e)));
public static Reader<S, IEnumerable<R>> Traverse<S, A, R>(this IEnumerable<A> @this, Func<A, Reader<S, R>> f) => @this.Fold(Enumerable.Empty<R>().ToReader<S, IEnumerable<R>>(), (a, e) => Append<R>().Curry().ToReader<S, Func<IEnumerable<R>, Func<R, IEnumerable<R>>>>().Apply(a).Apply(f(e)));
public static Either<L, IEnumerable<R>> Traverse<L, A, R>(this IEnumerable<A> @this, Func<A, Either<L, R>> f) => @this.Fold(Right<L, IEnumerable<R>>(Enumerable.Empty<R>()), (a, e) => Right<L, Func<IEnumerable<R>, Func<R, IEnumerable<R>>>>(Append<R>().Curry()).Apply(a).Apply(f(e)));
public static Validation<L, IEnumerable<R>> Traverse<L, A, R>(this IEnumerable<A> @this, Func<A, Validation<L, R>> f) => @this.Fold(Success<L, IEnumerable<R>>(Enumerable.Empty<R>()), (a, e) => Success<L, Func<IEnumerable<R>, Func<R, IEnumerable<R>>>>(Append<R>().Curry()).Apply(a).Apply(f(e)));

Sequence IEnumerable implementation with other data types

public static Maybe<IEnumerable<A>> Sequence<A>(this IEnumerable<Maybe<A>> @this) => @this.Traverse(Id<Maybe<A>>());
public static Identity<IEnumerable<A>> Sequence<A>(this IEnumerable<Identity<A>> @this) => @this.Traverse(Id<Identity<A>>());
public static Result<IEnumerable<A>> Sequence<A>(this IEnumerable<Result<A>> @this) => @this.Traverse(Id<Result<A>>());
public static IO<IEnumerable<A>> Sequence<A>(this IEnumerable<IO<A>> @this) => @this.Traverse(Id<IO<A>>());
public static Reader<S, IEnumerable<A>> Sequence<S, A>(this IEnumerable<Reader<S, A>> @this) => @this.Traverse(Id<Reader<S, A>>());
public static Either<L, IEnumerable<A>> Sequence<L, A>(this IEnumerable<Either<L, A>> @this) => @this.Traverse(Id<Either<L, A>>());
public static Validation<L, IEnumerable<A>> Sequence<L, A>(this IEnumerable<Validation<L, A>> @this) => @this.Traverse(Id<Validation<L, A>>());

We have to do similarly add an extension method for each other data type that we want to be able to traverse with; here for example is the implementation for the Maybe data type:


Maybe Traversable

public static IEnumerable<Maybe<B>> Traverse<A, B>(this Maybe<A> @this, Func<A, IEnumerable<B>> f) => @this.Fold(nothing: () => Enumerable.Empty<Maybe<B>>().Append(Nothing<B>()), just: a => f(a).Map(Just));
public static Identity<Maybe<B>> Traverse<A, B>(this Maybe<A> @this, Func<A, Identity<B>> f) => @this.Fold(nothing: () => Identity<Maybe<B>>.Of(Nothing<B>()), just: a => f(a).Map(Just));
public static Result<Maybe<B>> Traverse<A, B>(this Maybe<A> @this, Func<A, Result<B>> f) => @this.Fold(nothing: () => Value(Nothing<B>()), just: a => f(a).Map(Just));
public static IO<Maybe<B>> Traverse<A, B>(this Maybe<A> @this, Func<A, IO<B>> f) => @this.Fold(nothing: () => Nothing<B>().ToIO<Maybe<B>>(), just: a => f(a).Map(Just));
public static Reader<R, Maybe<B>> Traverse<R, A, B>(this Maybe<A> @this, Func<A, Reader<R, B>> f) => @this.Fold(nothing: () => Reader<R, Maybe<B>>.Pure(Nothing<B>()), just: a => f(a).Map(Just));
public static Either<L, Maybe<B>> Traverse<L, A, B>(this Maybe<A> @this, Func<A, Either<L, B>> f) => @this.Fold(nothing: () => Right<L, Maybe<B>>(Nothing<B>()), just: a => f(a).Map(Just));
public static Validation<L, Maybe<B>> Traverse<L, A, B>(this Maybe<A> @this, Func<A, Validation<L, B>> f) => @this.Fold(nothing: () => Success<L, Maybe<B>>(Nothing<B>()), just: a => f(a).Map(Just));

Maybe Sequence

public static IEnumerable<Maybe<A>> Sequence<A>(Maybe<IEnumerable<A>> @this) => @this.Traverse(Id<IEnumerable<A>>());
public static Identity<Maybe<A>> Sequence<A>(Maybe<Identity<A>> @this) => @this.Traverse(Id<Identity<A>>());
public static Result<Maybe<A>> Sequence<A>(Maybe<Result<A>> @this) => @this.Traverse(Id<Result<A>>());
public static IO<Maybe<A>> Sequence<A>(Maybe<IO<A>> @this) => @this.Traverse(Id<IO<A>>());
public static Reader<R, Maybe<A>> Sequence<R, A>(Maybe<Reader<R, A>> @this) => @this.Traverse(Id<Reader<R, A>>());
public static Either<L, Maybe<A>> Sequence<L, A>(Maybe<Either<L, A>> @this) => @this.Traverse(Id<Either<L, A>>());
public static Validation<L, Maybe<A>> Sequence<L, A>(Maybe<Validation<L, A>> @this) => @this.Traverse(Id<Validation<L, A>>());

...and that's it, we simply need to create an extension method for every inner / outer data type combination -- because unfortunately C# unlike Haskell does not allow functions that are generic over both the element and data types i.e. the ability to generically specify the int; element type and generically specify the Maybe or List data types.

This boilerplate code repetition is related to what's referred to as Higher Kinded Types (HKTs), or Higher Kinded Polymorphism, or Parametricity on data type constructors. It is also the same reason why our implementations for every other algebra requires an explicit extension method implementation.


To add this to your project and / or to access the code
For a complete set of the FP data types including Traverse and Sequence, you can either add the following Nuget (Endofunk.FX) to your app, or copy the relevant code from here:
https://github.com/endofunk/Endofunk-FX