Functional Thread 12 : Partiality and Exceptions related to Kleisli Categories.

[[)roi(]]

Previous Thread
In the last thread we explored Traversable Functors:

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
• Traversable Functors

From Wikipedia...
In category theory, a Kleisli category is a category naturally associated to any monad T. It is equivalent to the category of free T-algebras. The Kleisli category is one of two extremal solutions to the question Does every monad arise from an adjunction?

Recap:
The last time we covered Kleisli was in regards to composition of monadic functions; functions; functions where the type signature of the morphism is:

a -> m a

Where m is a generic variable representing any monadic data type e.g.

• Maybe
• List
• etc.

You can find the previous thread on kleisli composition here: Monadic Composition

The focus of this thread will be on dealing with Partiality and Exception as it's relevant for the category of Kleisli morphisms.

The challenge:
Create the following partial function in code using a monadic data type like Maybe (also called Option or Optional):

e.g, substituting 4 for x will result in an answer of 0.25

Submissions:
Although though the objective of this thread is to solve this problem using a functional approach; All submissions are welcome, including imperative and OOP style code in any language of your choice.

The comparison of approaches in dealing with exceptions and partial functions is after all what this challenge is about; hence focus on safely dealing with invalid input data that could crash your computation of this function.

My Solutions:
I'll be posting code examples for C#, C++, F#, Haskell and an explanation for this late Monday or Tuesday.

This will be a relatively code light thread; my approach will be strictly functional to demonstrate how the use of Kleisli composition and monadic data types helps to represent partial functions and exception handling.

 

[[)roi(]]

Partiality and Exception
Partiality and Exception are not typical topics for a programming article; outside of Framework design or Design by Contract. It isn’t because our functions are partiality and exception free, it’s because code is tested in such a narrow way that tests rarely consider the complete scope of input values.

Our code may have many implicit preconditions that we’ve either never considered or that we never document because the definition of a function doesn't insist on this.

Careful thought of how to avoid partiality and exceptions is the assessment of whether our programs will work reliably across a wide range of input and computation scenarios.

Consider a function that converts an integer to a boolean where 0 is false and 1 is true.

static bool ToBool(int x) {
  if (x == 0) return false;
  else if (x == 1) return true;
}

The function satisfies the design expectations: 0 becomes false and 1 becomes true however the compiler will raise the following error message:

Error: 'ToBool(int)': not all code paths return a value

The compiler picked up that our function doesn't cater for all values of x.


Changing The Design Specifications
We could change the function to deal with every possible value of x by applying the C language rule :

static bool ToBool(int x) {
  if (x == 0) return false;
  return true;
}

Except we're now in violation of the design expectations; invalid values of x return true


Preconditions
To address the design restriction, we could create a function with a precondition to raise an exception for unsupported values; on the expectation that the caller would encapsulate the call in a try catch to safely manage any possible exception.

static bool ToBool(int x) {
  if (x > 1 || x < 0) throw new ArgumentException(); ;
  if (x == 0) return false;
  return true;
}

Whilst this approach arguably works as designed in a synchronous call stack, it poses significant challenges when executed concurrently.


Function Type Honesty
Another issue is that looking at the function signature we're oblivious that this function is a partial function or that it will raise exceptions.

static bool ToBool(int x)

This makes these functions dependent on documentation and testing (two areas worryingly prone to lapses):

1. A partial function’s requirements must be documented
2. Tests must exercise a wide range of inputs to confirm that the output is consistent and expected.

Let’s assume points 1 is satisfied (or at least identified during debugging). We'd still need to satisfy point 2.

Debugging and testing will unlikely validate all scenarios in a non-trivial program; point 2 only excels at validating specific scenarios so unless your tests are extremely comprehensive, it’s likely your users will be able to get one of your functions into a state you've never tested for; increasing the potential for a runtime failure. This of course doesn't even cover the fact that many IDEs and/or code editors do not by default warn about unhandled exceptions; which makes it far easier for mistakes.


Monadic Data Types
The simplest solution to making any partial function into a total function is to change the type signature to include room in the return type to communicate a failure condition. Instead of triggering a fatal error, we can instead communicate the failure condition back to the caller and let them choose how and when to deal with it.

Partial functions including functions with exceptions can converted into a total function via a monadic data type like Maybe (a logical disjunction between a valid and invalid results).

static Maybe<bool> ToBool(int x) {
  if (x == 0) return Just(false);
  else if (x == 1) return Just(true);
  return Nothing();
}

This converts the previous Partial function into a Total function.

Total Function is a function defined for all possible input values. It also meets all the requirements of a pure function.

Monadic Data Types Make Function Types More Honest.
The Maybe data type also makes the function type more honest, because every input value is catered for and its immediately apparent from the function's type signature; no documentation or comment required.

static Maybe<bool> ToBool(int x)

The built-in equivalent of the Maybe monad in C# is the Option type; for example:

static bool? ToBool(int x) {
  if (x == 0) return false;
  else if (x == 1) return true;
  return nil;
}

The implementation of the Option data type in C# has built in implicit conversions; the bool? return type is syntactic sugar for Option<bool> and the implicit conversion on the Option type lifts the bool return value into a Option type with a success condition; whereas the return nil is implicitly converted into a Option with an error condition.

 

[[)roi(]]

Composition of Partiality and Exception
With similarity to a non trivial computation; a more complex equation can be converted into a set of smaller computations that are composed together to obtain the result.

To demonstrate this; we'll use the equation at the start of this thread; which is a slightly more complex example than previous integer to bool function.




The function is a composition of 3 functions


The goal can be implemented as the following composition of these 3 sub functions

Note:

• f2 is a pure function; where ∀x ∈ R.
• f1 and f3 are partial functions.

Haskell
The Maybe monad can be implemented roughly as follows

instance Monad Maybe where
  return = Just
  join Just( Just x) = Just x
  join _ = Nothing

Our 3 functions can be implemented as follows:

f1 :: (Ord a, Floating a) => a -> Maybe a
f1 x = if x >= 0 then Just(sqrt x) else Nothing

f2 :: Num a => a -> Maybe a
f2 x = Just (2*x)

f3 :: (Eq a, Fractional a) => a -> Maybe a
f3 x = if x /= 0 then Just(1/x) else Nothing

The final composition is achieved using the bind (flatmap) operator:

h :: (Ord a, Floating a) => a -> Maybe a
h x = (return x) >>= f1 >>= f2 >>= f3

C++
The Maybe monad can be implemented roughly as follows

template <class A> using Maybe = std::optional<A>;

template <class A, class B>
Maybe<B> fmap(std::function<B(A)> f, Maybe<A> a) {
  if (a) {
    return f(a.value());
  }
  return {};
}

template <class A>
Maybe<A> pure(A a) {
  return a;
}

template <class A>
Maybe<A> join(Maybe<Maybe<A>> a){
  if (a) {
    return a.value();
  }
  return {};
}

Our 3 functions can be implemented as follows

std::function<Maybe<float>(float)> f1 =
  [](float x) {
    if (x >= 0) {
      return Maybe<float>(sqrt(x));
    }
    return Maybe<float>();
  };

std::function<Maybe<float>(float)> f2 = [](float x) { return 2 * x; };

std::function<Maybe<float>(float)> f3 =
  [](float x) {
    if (x != 0) {
      return Maybe<float>(1 / x);
    }
    return Maybe<float>();
  };

The final composition is achieved using bind (flatmap) function:

auto h(float x) {
  Maybe<float> a = pure(x);
  return bind(f3,bind(f2,bind(f1, a)));
};

F#
The Maybe monad can be implemented roughly as follows

type public Maybe<'a> =
  | Nothing
  | Just of 'a

let public flatmap f m =
  match m with
  | Nothing -> Nothing
  | Just a -> f a
let public ( >>= ) m f = flatmap f m
let public Return a = Just a

Our 3 functions can be implemented as follows:

let f1 x = if x >= 0. then Just (sqrt x) else Nothing
let f2 x = Just (2. * x)
let f3 x = if x <> 0. then Just (1. / x) else Nothing

The final composition is achieved using the bind (flatmap) operator:

let h x = (Return x) >>= f1 >>= f2 >>= f3

Summary
In all the above code examples; f1, f3 functions were converted from partial functions with exceptions into a total function using the Maybe monad. Which means that the final composition of all three functions is also a total function.


Kleisli composition
The composition of monadic functions i.e. function of the signature a -> M B where M is a generic placeholder for a data type like Maybe, or Option, or List, ... i.e. any data type that conforms to the monad algebra laws by implementing essentially a bind (flatmap) higher order function.

Reference: Kleisli Categories from category theory.