4
\$\begingroup\$

I've implemented a simple Maybe type around std::function that implements function composition where any function in the composition can fail (causing the entire composition to fail) - in essence, a Maybe monad where operator<< implements bind.

For example,

  // one binary function that cannot fail.
  std::function<int(float, float)> h  =
    [](const float a, const float b) -> int {
                                             return a * b;
                                        };


  // a unary function that CAN fail.
  std::function<std::optional<int>(int)> g =
    [](const int c) -> std::optional<int> {
                                           if (c < 0) return std::nullopt;
                                           else return c;
                                          };
                                                                                    
  // another unary function that CAN fail.
  std::function<std::optional<bool>(int)> f =
    [](const int d) -> std::optional<bool> {
                                            if (d < 10) return true;
                                            else return std::nullopt;
                                           };

  // compose f, g, and h
  auto G = Maybe(f) << Maybe(g) << Maybe(h);

  // evaluate the composition - this maps (float, float) -> optional<bool>
  auto result = G(1.0, 7.0);

  // and check if the computation was successful
  if (result) std::cout << "Result: " << *result << "\n";
  else std::cout << "Computation failed!\n";

Here is my current implementation:

#include <functional>
#include <optional>
#include <iostream>

template <typename TReturn, typename... TArgs>
struct Maybe {

  /**
   * The (lifted) function that we evaluate.
   */
  std::function<std::optional<TReturn>(const std::optional<TArgs>...)> eval_;

  /**
   * Lift a non-failable function into the Maybe monad.
   */
  auto lift(std::function<TReturn(const TArgs...)> const& f) {

    // construct a lambda that implements the Maybe monad.
    return [f](const std::optional<TArgs> ... args) -> std::optional<TReturn> {
        if ((args && ...)) return f(*(args)...);
        else return {};
    };
  }

  /**
   * Lift a (failable) function returning an optional into the Maybe monad.
   */
  auto lift(std::function<std::optional<TReturn>(const TArgs...)> const& f) {

    // this overload is currently necessary so that I can extract the TReturn
    // value type so that `eval_` doesn't pick up another layer of std::optional
    // i.e. std::optional<std::optional<int(float, float)>>.

    // construct a lambda that implements the Maybe monad.
    return [f](const std::optional<TArgs> ... args) -> std::optional<TReturn> {
        if ((args && ...)) return f(*(args)...);
        else return {};
    };

  }

  /**
   * Construct a Maybe from a std::function returning an optional.
   */
  Maybe(std::function<TReturn(TArgs...)> const f) : eval_(lift(f)) {}

  /**
   * Construct a Maybe from a std::function returning an optional.
   */
  Maybe(std::function<std::optional<TReturn>(TArgs...)> const f) : eval_(lift(f)) {}

  /**
   * Apply the Maybe to the given arguments.
   */
  auto operator()(std::optional<TArgs> const... args) const {
    return this->eval_(args...);
  }

  /**
   * Compose the callable in `this` with the callable in `other`.
   *
   * @param other    Another monadic filter instance.
   */
  template <typename TOReturn, typename... TOArgs>
  auto operator<<(Maybe<TOReturn, TOArgs...> const& other) const -> Maybe<TReturn, TOArgs...> {

    // get references to the underlying lifted functions
    // capturing the Maybe instances into the lambda results in a seg-fault
    auto f = this->eval_;
    auto g = other.eval_;

    // construct the coposition lambda
    std::function<std::optional<TReturn>(TOArgs...)> fg =
      [=](TOArgs... args) -> std::optional<TReturn> { return f(g(args...)); };

    return fg;
  }


}; // END: class Maybe

This is targeting C++17 only. Any and all feedback appreciated!

There's currently some duplication in the constructors and the lift method so that I wrap functions that already return std::optional without being wrapped in a second layer of optional i.e. std::optional<std::optional<...>> which makes the composition impossible (I'm sure there is some template trickery that could make this work with just a single method and constructor).

\$\endgroup\$
1
\$\begingroup\$

First issue with this design is that it is going to be slow and non-optimizable. std::function has a couple of features that hide type and implementation and neither is easy to optimize nor cheap. If you make complex functions that run in milliseconds than it is of no problem at all but otherwise consider a different more efficient approach.

Second issue, is that if a function returns std::optional and composed with function that accepts std::optional and does something non-trivial when std::nullopt is supplied then the Maybe composition will change output. I don't think that this is what uses desires.

Also, the naming isn't good Maybe... come up with something more meaningful and intuitive.


To deal with the first issue, first look for an inspiration to std::bind as one can see in the cppreference it doesn't return a std::function but an unspecified type. Why?

One possible implementation is that it returns a lambda that calls the function with the given arguments. That's it. And in this way it is a see-through method which is easily convertible to std::function and other function/method wrappers. (To implement placeholders feature its complexity raises beyond that of just generating a trivial lambda function that forwards arguments.)

Imagine what std::bind would generate if supplementing each argument was done via an operator and converting to a std::function each time - instead of the variadic template approach? That would be a disaster I assure you.

For instance, boost::format uses operators to fill arguments while fmt::format relies on variadic template approach... and as a result fmt::format is considerably faster both in performance and in compilation time. (Can't blame boost::format as it was implemented and designed way before C++11)

So it would be much better if you wrote a template function that generates a callable from a sequence of callable:

template<typename... Collables>
auto compose_callables(Callables...){...}

This will also allow you to address the second issue about how to properly implement the "optional" feature: suppose you compose f with g to make f(g). And input type of f is Arg and function g returns output std::optional<Arg> then abort the execution whenever the optional has no value. However, forward the argument as is when the function f accepts the same type that g returns even if it is an std::optional of something.

To implement this properly you'll need to stretch some muscles with template meta programming and SFINEA. This is quite challenging for most C++ programmers. Wish you luck if you attempt to.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

You have the exact same comment (Construct a Maybe from a std::function returning an optional) on two different constructors. I don't think the comment was necessary anyway. Both constructors should be explicit, to prevent implicit conversions.

Using return {} instead of return std::nullopt strikes me as needless obfuscation. (In the same way, I wouldn't use return {} when I meant return nullptr.)


Your use of const-qualified function parameter variables is an antipattern (see my blog post "const is a contract"). In this particular case, it prevents you from moving-out-of the parameters, which is exactly what you should want to do here:

static auto lift(std::function<TReturn(TArgs...)> f) {
    return [f = std::move(f)](std::optional<TArgs>... args) -> std::optional<TReturn> {
        if ((args.has_value() && ...)) {
            return f(std::move(*args)...);
        } else {
            return std::nullopt;
        }
    };
}

You're actually very lucky that std::function<TReturn(const TArgs...)> and std::function<TReturn(TArgs...)> happen to be the same type! You use the two spellings inconsistently throughout this code. Stick to the simpler shorter one.


It would probably make sense to try to provide an overload of operator<< taking rvalues on left and/or right, to avoid some copying.

It's surprising that operator<< returns a std::function<...> instead of a Maybe<...>. I don't actually see what that buys you.


As ALX23z said, it's unfortunate that you build everything around std::function instead of around arbitrary callables. For example, I couldn't write

auto f = [](int x) -> std::optional<int> { return (x < 10) ? x + 1 : std::nullopt; };
auto g = [](int y) { return y * 2; };
auto G = Maybe(f) << Maybe(g);
assert(G(5) == 12);
assert(G(12) == std::nullopt);

As I write that, I realize that it's also pretty confusing to me that you picked << to mean "compose with." Wikipedia tells me that the notation I'm familiar with, f ∘ g, is also ambiguous — does it mean "f(g(x))" or "g(f(x))"? Well, I might pick something like

auto g_of_f_of_x = Maybe(f).then(g);
auto f_of_g_of_x = Maybe(f).of(g);

so as to be completely unambiguous.


Using std::function allowed you to cheat around one of the perennial impossibilities of C++: detecting a callable's "argument types." This means you can't use your Maybe with generic lambdas or templates like std::plus<>. If I were writing it, I'd ditch that cheat and try to make it work for generic lambdas from the very beginning.

You can see my worked solution here on Godbolt — notice the left-hand pane using std::function for your f,g,h variables, and the right-hand pane using auto to make them actually lambda types, thus eliminating all the std::function overhead. The meat of my solution is

template<class Callable>
struct Maybe {
    Callable f_;
    explicit Maybe(Callable f) : f_(std::move(f)) {}

    template<class... Args>
    auto operator()(Args&&... args) const
        -> decltype(optional_of(f_(value_of(static_cast<Args&&>(args))...)))
    {
        if ((has_value(args) && ...)) {
            return f_(value_of(static_cast<Args&&>(args))...);
        } else {
            return std::nullopt;
        }
    }
};

template<class T, class U>
auto operator<<(const Maybe<T>& a, const Maybe<U>& b) {
    // "a << b" means "a(b(x))"
    return Maybe([a, b](auto&&... args) {
        return a(b(static_cast<decltype(args)>(args)...));
    });
}

value_of, optional_of, has_value are just overload sets with special overloads for std::optional.

Making this code safe against ADL is left as an exercise for the reader — but I think basically you can just slap a namespace detail around the helper bits and you'll be good to go.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.