5
\$\begingroup\$

In order to improve my understanding of C++ template meta-programming, SFINAE, references, and overall class design, I've tried to implement a Maybe<T> class in C++.

Of course, the class is heavily based off of Haskell's Maybe Monad, and has the same functionality. I am aware that std::optional<T> pretty much does the same thing in C++17, but I decided not to implement it exactly as the standard specifies.

In specific, I've renamed a few functions, and added some of my own (namely, the apply method). More notably, I tried to make it support possible references (by making it use a std::reference_wrapper).

Here is the code below:

maybe.hpp:

#pragma once

#include <utility>
#include <exception>
#include <type_traits>
#include <functional>

namespace maybe {

struct nothing_t {} nothing;

template <typename T>
class Maybe_Base {

public:

    struct bad_access : std::exception {
        virtual const char* what() const noexcept {
            return "Attempted to access a value of a Maybe wrapper that doesn't exist.";
        }
    };


    Maybe_Base():
        val(nullptr)
    {}

    Maybe_Base(nothing_t):
        val(nullptr)
    {}

    template <class... Args>
    explicit Maybe_Base(Args&&... args) {
        val = new T(std::forward<Args>(args)...);
    }

    ~Maybe_Base() {
        if (val)
            val->~T();
        delete val;
    }

    // Is there a way to ensure extraneous copies aren't made? Or is the only option just to delete the copy constructor entirely?
    Maybe_Base(const Maybe_Base<T>& other) {
        if (other.val)
            val = new T(*other.val);
        else
            val = nullptr;
    }

    Maybe_Base& operator=(Maybe_Base<T> other) {
        swap(*this, other);
        return *this;
    }

    friend void swap(Maybe_Base<T>& a, Maybe_Base<T>& b) {
        using std::swap;
        swap(a.val, b.val);
    }

    Maybe_Base(Maybe_Base<T>&& other) {
        this->val = other.val;
        other.val = nullptr;
    }


    inline bool empty() const {
        return val == nullptr;
    }

    inline bool hasValue() const {
        return !empty();
    }

    inline explicit operator bool() const {
        return hasValue();
    }


    T value() {
        if (empty())
            throw bad_access();
        else
            return *val;
    }

    T valueOr(T defaultVal) {
        if (empty())
            return defaultVal;
        return *val;
    }

    const T& operator*() const {
        return *val;
    }
    T& operator*() {
        return *val;
    }

    const T* operator->() const {
        return val;
    }
    T* operator->() {
        return val;
    }


    void clear() {
        val->~T();
        delete val;

        val = nullptr;
    }

    template <class Func, typename... Args>
    std::enable_if_t<    !std::is_void_v<std::invoke_result_t<Func, T, Args...>>
                      && !std::is_member_function_pointer_v<Func>,
        Maybe_Base<std::invoke_result_t<Func, T, Args...>>
    >
    apply(Func f, Args&&... args) {
        if (*this)
            return Maybe_Base<std::invoke_result_t<Func, T, Args...>>{f(this->value(), std::forward<Args>(args)...)};
        return nothing;
    }

    template <class Func, typename... Args>
    std::enable_if_t<     std::is_void_v<std::invoke_result_t<Func, T, Args...>>
                      && !std::is_member_function_pointer_v<Func>,
        void
    >
    apply(Func f, Args&&... args) {
        if (*this)
            f(this->value(), std::forward<Args>(args)...);
    }

    template <class Pointer_To_Method, typename... Args>
    std::enable_if_t<    !std::is_void_v<std::invoke_result_t<Pointer_To_Method, T, Args...>>
                      &&  std::is_member_function_pointer_v<Pointer_To_Method>,
        Maybe_Base<std::invoke_result_t<Pointer_To_Method, T, Args...>>
    >
    apply(Pointer_To_Method f, Args&&... args) {
        if (*this)
            return Maybe_Base<std::invoke_result_t<Pointer_To_Method, T, Args...>>{(this->value().*f)(std::forward<Args>(args)...)};
        return nothing;
    }

    template <class Pointer_To_Method, typename... Args>
    std::enable_if_t<     std::is_void_v<std::invoke_result_t<Pointer_To_Method, T, Args...>>
                      &&  std::is_member_function_pointer_v<Pointer_To_Method>,
        void
    >
    apply(Pointer_To_Method f, Args&&... args) {
        if (*this)
            (this->value().*f)(std::forward<Args>(args)...);
    }

private:
    T* val;
};

template <class T, bool = std::is_reference_v<T>>
class Maybe;

template <class T>
class Maybe<T, false> : public Maybe_Base<T> {

public:
    template <typename... Args>
    Maybe(Args&&... args): Maybe_Base<T>(std::forward<Args>(args)...) {}
};

template <class T>
class Maybe<T, true> : public Maybe_Base<std::reference_wrapper<std::decay_t<T>>> {
    typedef std::reference_wrapper<std::decay_t<T>> Wrap_Type;
public:
    template <typename... Args>
    Maybe(Args&&... args): Maybe_Base<Wrap_Type>(std::ref(args)...) {}

    T value() {
        return Maybe_Base<Wrap_Type>::value().get();
    }

};

} // namespace maybe

And here's a small test .cpp file to make sure the implementation works:

#include <iostream>
#include <memory>
#include <optional>

#include "maybe.hpp"

struct foo {
    int i;

    foo(int i_): i(i_) {}
    foo() {}

    void bar(int j) {
        std::cout << "Bar." << ' ' << i*j << std::endl;
    }

    ~foo() {
        std::cout << "Deleting a foo..." << std::endl;
    }
};

maybe::Maybe<char> letter(int i) {
    if (i >= 0 && i < 26)
        return maybe::Maybe<char>(i + 'A');
    return maybe::nothing;
}

int main() {

    maybe::Maybe<std::unique_ptr<foo>> i{ std::make_unique<foo>(8) };

    maybe::Maybe<std::unique_ptr<foo>> j = std::move(i);

    maybe::Maybe<foo> f{12321};

    std::cout << std::boolalpha << j.hasValue() << ' ' << i.hasValue() << std::endl;

    f.apply(&foo::bar, 2);



    int p = 7;
    maybe::Maybe<int&> q = p;



    std::cout << q.value() << std::endl;

    p = 8;

    std::cout << q.value() << std::endl;

    // Could I possibly do something simpler like `q = 6`?
    q.value() = 6;

    std::cout << p << std::endl;

    q.apply([] (int a) { std::cout << a << std::endl; });
    std::cout << q.apply([] (int a) { return a + 1; }).value();


    maybe::Maybe<char> c = letter(12);
    std::cout << c.value() << std::endl;
}

Is there anything that I seem to have messed up, or situations I've overlooked? I'm specifically concerned in making sure that the implementation is efficient, and has easy use.

\$\endgroup\$
4
\$\begingroup\$
  • Use std::unique_ptr. (It's much safer and easier than manual memory management).

  • bug: The delete operator will call the object destructor. We should not call the destructor manually. (A perfect example of why we should use std::unique_ptr and avoid this entirely :D ).

  • Note that std::optional doesn't allocate memory itself, but keeps the contained object on the stack. This could be done with a boolean flag and std::aligned_storage or perhaps with std::variant.

  • value and valueOr can be const functions. value should perhaps return a reference, and have const and non-const versions.

  • opinion: I really dislike that std::optional overloads operator-> and operator*. They're unnecessary and make it less obvious what the type is. It's not a pointer type (at least semantically), so I don't think they make sense. Personally I'd skip them.

  • If we're creating a special case for reference types, and hiding the std::reference_wrapper internally, we need to re-implement the other access functions, not just value(). Currently the reference_wrapper is exposed through valueOr, operator* and operator->.

    (This results in a subtly different implementation for "reference maybes", and I don't know if that's a good thing or not. However, I feel like we should either hide the std::reference_wrapper entirely, or let the user create a Maybe<std::reference_wrapper<T>> themselves if they need one).

  • The apply methods are very interesting. :)

    • I think we need const versions (for calling const member functions of types contained in const Maybe's).

    • Since the Maybe can also store simple POD types, where the apply functions do not make sense, perhaps apply should be implemented as a set of free functions (and named invoke_maybe or something similar). This would provide a calling syntax more consistent with std::invoke and std::bind. It would also allow invoke_maybe to be implemented for other classes, such as std::function (or std::optional), returning an empty Maybe if necessary.

    • feature request: Note that std::invoke lets us access member variables, not just member functions. This doesn't appear to be supported with the current apply implementation, but would be pretty cool.

\$\endgroup\$
  • \$\begingroup\$ Thank you for the feedback! I'll be making the changes you mentioned. A few questions though: 1) Why is it bad to call the destructor manually? I understand it's better to use a unique_ptr overall, but why is it specifically a bug to call the destructor manually? 2) For the assignment operators, I tried using the copy-and-swap idiom. Does this only apply to copy-assignments? I thought it was supposed to implement both assignment operators, to simply the code. Am I correct, or did I use CAS wrong? \$\endgroup\$ – Andrew P. Jan 16 at 2:32
  • 2
    \$\begingroup\$ 1) Since delete calls the destructor itself, we end up with two destructor calls, which is undefined behaviour. (Everything in C++ depends on having one destructor call. Once that happens, the object lifetime is deemed to have ended.) 2) You're quite right. My bad. \$\endgroup\$ – user673679 Jan 16 at 8:14
2
\$\begingroup\$

To be frank, I'm not sure it really is a Maybe implementation. It's actually not very different from a smart pointer (well, maybe not that smart since the destructor deletes the underlying value twice, as @user673679 points out :). By the way I don't think that a smart pointer -or any pointer- is a bad approximation of the Haskell Maybe type: it can be either nullptr (Nothing) or pointing to some value (Just some_value). Of course, std::optional would probably be more efficient, since it stores the optional value on the stack, but I don't believe it's a conceptual leap towards Maybe either: the real difference between pointers and std::optional on the one hand, and Maybe on the other hand is that Maybe is a sum type, that is a type that can be either one of different types, whereas pointers or std::optional are types with a well-defined null/void value.

Implementing sum types in C++ is rather difficult. The standard library's sum type -std::variant- is rather cumbersome and has drawn convincing complaints. But it's also a path to a lot more power than you could reach with pointers or optional: they can be a good approximation of Maybe, but not of Either, for instance, which isn't fundamentally different though, and a lot more powerful.

So what would Maybe as a sum type look like in C++? I would say something like:

#include <variant>

struct Nothing {};

template <typename T>
struct Just {
    Just(const T& t) : value(t) {}
    Just(T&& t) : value(t) {}
    Just() = default;

    T value;   
};

template <typename T>
using Maybe = std::variant<Nothing, Just<T>>;

So, how would you use it then? Creating one looks very much like what you did:

Maybe<char> letter(int i) {
    if (i >= 0 && i < 26) return Just<char>('A' + i);
    return Nothing();
}

Now, what can you do with it? Maybe is a functor in the Haskell sense, so you need a way to map a function onto it. The Haskell signature is : (a -> b) -> F a -> F b. The C++ implementation would be along the lines:

template <typename Fn, typename T>
auto fmap(Fn fn, const Maybe<T>& mb) {

    using return_type   = decltype(fn(std::declval<T>()));    

    auto visitor = [fn](auto&& arg) -> Maybe<return_type> 
    {
        using Type = std::decay_t<decltype(arg)>;
        if constexpr(std::is_same_v<Type, Nothing>) return Nothing();
        else return Just<return_type>(fn(arg.value));
    };

    return std::visit(visitor, mb); 
      /* visit is the *apply* you're looking for: given a visitor with 
         overloads for any type the variant can contain a value of, it 
         will apply the correct overload on the value it contains */
}

Now Maybe is also a monad. If you want to implement the >>= (aka bind), whose signature in Haskell is (a -> M b) -> M a -> M b, it isn't very different:

template <typename Fn, typename T>
auto bind(Fn fn, const Maybe<T>& mb) {

    using return_type = decltype(fn(std::declval<T>()));    

    auto visitor = [fn](auto&& arg) -> return_type 
    {
        using Type = std::decay_t<decltype(arg)>;
        if constexpr(std::is_same_v<Type, Nothing>) return Nothing();
        else return fn(arg.value);
    };

    return std::visit(visitor, mb);
}

Here's a link to those few snippets of code if you feel like exploring that vein.

\$\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.