2
\$\begingroup\$

Similar to Partial Function composability in Haskell, I've attempted to implement partial function composability in C++20 via C++ concepts. More details about the problem(for which my solution is available below) from the linked post:

Below is my solution for the CTFP chapter 4 challenges which essentially involves composing partial functions(that don't have defined outputs for all possible inputs i.e. returning a Maybe/std::optional in C++). The challenge is to implement composition, identity(to satisfy category requirements) and try it out with 2 partial functions.

#include <optional>
#include <cmath>
#include <cassert>
#include <concepts>

// C++17 alternative with std::function: http://coliru.stacked-crooked.com/a/d8a8ed976dc59715

namespace detail{
template<typename>
struct unary_fn;

template<typename M, typename R, typename Arg>
struct unary_fn<R(M::*)(Arg)>
{
    using return_type = R;
    using arg_type = Arg;
};

template<typename R, typename Arg>
struct unary_fn<R(*)(Arg)>
{
    using return_type = R;
    using arg_type = Arg;
};

template<typename Lambda>
struct unary_fn : unary_fn<decltype(&Lambda::operator())> { };

template <typename T>
struct is_optional: std::false_type {};

template <typename T>
struct is_optional<std::optional<T>>: std::true_type {};
}

// Concept to check composability
template <typename PartialFn1, typename PartialFn2, typename OutType = detail::unary_fn<PartialFn2>::return_type, typename InType = detail::unary_fn<PartialFn1>::arg_type>
concept SingleArgComposable = requires(PartialFn1 pf1, PartialFn2 pf2, InType elem) {
    requires detail::is_optional<typename detail::unary_fn<PartialFn1>::return_type>::value;
    { pf2(*pf1(elem)) } -> std::same_as<OutType>;
    requires detail::is_optional<OutType>::value;
};

// Given(using std::optional) and safe_root
std::optional<double> safe_root(double x) {
    return x >= 0 ? std::optional{std::sqrt(x)} : std::nullopt;
}

// Q1: Construct the Kleisli category for partial functions (define composition and identity).
template <typename T>
std::optional<T> id(T input) {
    return input;
}

template <typename PartialFn1, typename PartialFn2, typename RetType = detail::unary_fn<PartialFn2>::return_type> requires SingleArgComposable<PartialFn1, PartialFn2, RetType>
auto compose(PartialFn1 firstCallable, PartialFn2 secondCallable) {
    return [firstCallable, secondCallable](auto inValue) {
        auto firstResult = firstCallable(inValue);
        if(firstResult) {
            return secondCallable(*firstResult);
        }
        return RetType{};
    };
}

// Q2: Implement safe_reciprocal
std::optional<double> safe_reciprocal(double input) {
    return (input != 0) ? std::optional{1 / input} : std::nullopt;
}


int main(){
    static_assert(detail::is_optional<std::optional<double>>::value);
    
    // Q1(Testing id + compose)
    assert((safe_root(4.) == compose(id<double>, safe_root)(4.)) && safe_root(4.) == std::optional<double>{2.});
    assert((safe_root(4.) == compose(safe_root, id<double>)(4.)) && safe_root(4.) == std::optional<double>{2.});
    assert((safe_root(-5.) == compose(safe_root, id<double>)(-5.)) && safe_root(-5.) == std::nullopt);

    // Q3: Compose safe_root and safe_reciprocal
    auto safe_root_reciprocal = compose(safe_reciprocal, safe_root);
    assert(*safe_root_reciprocal(0.25) == 2.0);
    assert(safe_root_reciprocal(0) == std::nullopt);
    assert(safe_root_reciprocal(-0.25) == std::nullopt);
}

Coliru Link

Hoping to get suggestions on:

  • C++20 alternatives I can use to avoid having to implement "unary_fn".
  • Any improvements I could make to the SingleArgComposable concept(to make it closer to the Haskell "concept" (b -> Maybe c) -> (a -> Maybe b) -> (a -> Maybe c)). std::function is actually able to come pretty close(coliru link), but I was hoping to do this with concepts.
  • General review for improvements and C++20 features I should be using.
\$\endgroup\$
4
  • \$\begingroup\$ Does std::function not support all this? \$\endgroup\$ Feb 23 at 19:29
  • 1
    \$\begingroup\$ Unfortunately C++ is never going to support "Partial Functions" in the same way. Some of these functional languages allowed partial execution of the function with the given parameters blocking when missing parameters were needed (and re-starting when they were provided). C++ will never be able to do that. Fortunately that feature hardly ever pays of in increased performance. \$\endgroup\$ Feb 23 at 19:34
  • \$\begingroup\$ std::function does support this - I implemented it that way in the C ++17 link above: coliru.stacked-crooked.com/a/d8a8ed976dc59715. I was trying to implement this in a generic way to use regular/member/lambda and std::function using C++20 concepts. \$\endgroup\$
    – tangy
    Feb 23 at 20:29
  • \$\begingroup\$ Agreed, about some of the fancier features. But I've found that the type constraints Haskell provides is a good way to formulate concepts which was what I was trying in the example above. Additionally, a simple FP concept like compose does seem like it would be handy in C++. \$\endgroup\$
    – tangy
    Feb 23 at 20:43
1
\$\begingroup\$

First of all, your unary_fn is totally misguided. You're trying to take a C++ object and ask it "What is your first argument type?" C++ doesn't really do that, because we have overloading. See "Perennial impossibilities of C++" (2018-06-12).

auto abs = [](const auto& x) { return (x < 0) ? -x : x; };
unary_fn<decltype(abs)> u;  // oops, does not compile!

However, to avoid reimplementing the (misguided, wobbly) wheel, you could definitely switch to Boost.CallableTraits: boost::callable_traits<decltype(abs)>::args also does not compile, but it takes less hand-written code to achieve that same non-compilation. ;)


template <typename PartialFn1, typename PartialFn2, typename OutType = detail::unary_fn<PartialFn2>::return_type, typename InType = detail::unary_fn<PartialFn1>::arg_type>
concept SingleArgComposable = requires(PartialFn1 pf1, PartialFn2 pf2, InType elem) {
    requires detail::is_optional<typename detail::unary_fn<PartialFn1>::return_type>::value;
    { pf2(*pf1(elem)) } -> std::same_as<OutType>;
    requires detail::is_optional<OutType>::value;
};

This code is pretty impenetrable. Whitespace and newlines would help. So would shorter template parameter names; for example, PartialFn1 and PartialFn2 are only one trailing digit different, which tends to get lost in the noise, whereas F and G are much more distinct names that convey the exact same amount of information: "this thing is a type parameter."

You also don't have to say typename OutType; we know it's a Type because it's a type parameter. Just class Out is good enough. (I prefer class because it's shorter, and doesn't get confused with the other meaning of typename inside complicated templates.)

Finally, some helper aliases would... help. :)

template<class F> using unary_arg_t = detail::unary_fn<F>::arg_type;
template<class F> using unary_return_t = detail::unary_fn<F>::return_type;

template<class F, class G, class Out = unary_return_t<G>, class In = unary_arg_t<F>>
concept SingleArgComposable = requires(F f, G g, In x) {

    requires detail::is_optional<unary_return_t<F>>::value;
    requires detail::is_optional<Out>::value;

    { g(f(x).value()) } -> std::same_as<Out>;
};

At this point it's actually just about as easy to eliminate the In and Out parameters.

template<class F, class G>
concept SingleArgComposable = requires(F f, G g, unary_arg_t<F> x) {

    requires detail::is_optional<unary_return_t<F>>::value;
    requires detail::is_optional<unary_return_t<G>>::value;

    { g(f(x).value()) } -> std::same_as<unary_return_t<G>>;
};

Here's another impenetrable token soup:

template <typename PartialFn1, typename PartialFn2, typename RetType = detail::unary_fn<PartialFn2>::return_type> requires SingleArgComposable<PartialFn1, PartialFn2, RetType>
auto compose(PartialFn1 firstCallable, PartialFn2 secondCallable) {
    return [firstCallable, secondCallable](auto inValue) {
        auto firstResult = firstCallable(inValue);
        if(firstResult) {
            return secondCallable(*firstResult);
        }
        return RetType{};
    };
}

Rewritten to let in some natural light:

template<class F, class G, class R = unary_return_t<G>>
auto compose(F f, G g)
    requires SingleArgComposable<F, G>
{
    return [=](auto x) -> R {
        if (auto fx = f(x)) {
            return g(*fx);
        }
        return std::nullopt;
    };
}

If this were production code, I would change all the by-copy stuff to use move semantics:

template<class F, class G, class R = unary_return_t<G>>
auto compose(F f, G g)
    requires SingleArgComposable<F, G>
{
    return [f = std::move(f), g = std::move(g)]<class X>(X&& x) -> R {
        if (auto fx = f(std::forward<X>(x))) {
            return g(std::move(*fx));
        }
        return std::nullopt;
    };
}

Oh, and about halfway through the code you seem to have forgotten about all that unary_fn stuff you had started out with. Clearly, if you want compose(f,g) to itself be composable, you either have to

  • throw out all that unary_fn stuff because it can't handle generic lambdas such as compose(f,g), or

  • make compose(f,g) return a non-generic lambda.

For example:

template<class F, class G>
auto compose(F f, G g)
    requires SingleArgComposable<F, G>
{
    return [=](unary_arg_t<F> x) -> unary_return_t<G> {
        if (auto fx = f(x)) {
            return g(*fx);
        }
        return std::nullopt;
    };
}

Now you can do compose(f, compose(g, h)) and so on.

\$\endgroup\$
0
\$\begingroup\$

I looked at chapter 4 and the safe sqrt example:

Here: safeSqrt is your partial function.

#include <cmath>
#include <iostream>
#include <optional>

auto safeSqrt = [](double x)
{
    if (x != 0) {
        return std::optional<double>{sqrt(x)};
    }
    return std::optional<double>{};
};

int main()
{
    std::cerr << sqrt(4) << "\n";

    auto x = safeSqrt(4);
    std::cerr << x.value() << "\n";
}
\$\endgroup\$
6
  • 1
    \$\begingroup\$ Apologies - could you clarify your suggestion? - is there a mistake in the way i've implemented safe_root above. Also my question was more so asking on suggestions re: the SingleArgComposable concept used. \$\endgroup\$
    – tangy
    Feb 23 at 20:32
  • 1
    \$\begingroup\$ @tangy Why does the above not solve the problem. You have optionals and composed a function using another function. \$\endgroup\$ Feb 23 at 22:17
  • 1
    \$\begingroup\$ But I didnt really have any problem(I had already got the composition working), was more so looking for feedback on improving the code. The safeSqrt you've provided is equivalent to the safe_root I've already written. \$\endgroup\$
    – tangy
    Feb 23 at 22:29
  • \$\begingroup\$ @tangy I am trying to understand why you need any of your code. It seems that it can be done much more simply by using auto/lambda and a couple of lines of code. What is so special that the above pattern does not solve your problem. Maybe I just don't understand what you are trying to achieve? \$\endgroup\$ Feb 24 at 0:25
  • \$\begingroup\$ Completely agreed - it can be implemented in a shorter/cleaner way via lambdas. However, my understanding is that applying type constraints via concepts can help with (1) Clearer error messages (2) Making the normally implicit requirements of the function explicit and imposing the same to ensure that inputs meet preconditions. For example in the link here I'm able to erroneously pass in and execute compose with a non partial function which could be caught at compile time with the concept: coliru.stacked-crooked.com/a/5fc1f5e4dd686416 \$\endgroup\$
    – tangy
    Feb 24 at 1:49

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.