3

So, I've run into this sort of thing a few times in C++ where I'd really like to write something like

case (a,b,c,d) of
     (true, true, _, _ )     => expr
   | (false, true, _, false) => expr
   | ...

But in C++, I invariably end up with something like this:

bool c11 = color1.count(e.first)>0;
bool c21 = color2.count(e.first)>0;
bool c12 = color1.count(e.second)>0;
bool c22 = color2.count(e.second)>0;
// no vertex in this edge is colored
// requeue
if( !(c11||c21||c12||c22) )
{
    edges.push(e);
}
// endpoints already same color
// failure condition
else if( (c11&&c12)||(c21&&c22) )
{
    results.push_back("NOT BICOLORABLE.");
    return true;
}
// nothing to do: nodes are already
// colored and different from one another
else if( (c11&&c22)||(c21&&c12) )
{
}
// first is c1, second is not set
else if( c11 && !(c12||c22) )
{
    color2.insert( e.second );
}
// first is c2, second is not set
else if( c21 && !(c12||c22) )
{
    color1.insert( e.second );
}
// first is not set, second is c1
else if( !(c11||c21) && c12 )
{
    color2.insert( e.first );
}
// first is not set, second is c2
else if( !(c11||c21) && c22 )
{
    color1.insert( e.first );
}
else
{
    std::cout << "Something went wrong.\n";
}

I'm wondering if there's any way to clean all of those if's and else's up, as it seems especially error prone. It would be even better if it were possible to get the compiler complain like SML does when a case expression (or statement in C++) isn't exhaustive. I realize this question is a bit vague. Maybe, in sum, how would one represent an exhaustive truth table with an arbitrary number of variables in C++ succinctly? Thanks in advance.

3 Answers 3

7

I like Alan's solution but I respectfully disagree with his conclusion that it is too complex. If you have access to C++11 it gives you almost all the tools you need. You only need to write one class and two functions:

namespace always {

struct always_eq_t {
};

template <class lhs_t>
bool operator==(lhs_t const&, always_eq_t)
{
    return true;
}

template <class rhs_t>
bool operator==(always_eq_t, rhs_t const&)
{
    return true;
}

}  // always

Then you can write your function in a way relatively similar to ML:

#include <tuple>
#include <iostream>

void f(bool a, bool b, bool c, bool d)
{
    always::always_eq_t _;

    auto abcd = std::make_tuple(a, b, c, d);

    if (abcd        == std::make_tuple(true,  true, _, _)) {
        std::cout << "true, true, _, _\n";
    } else if (abcd == std::make_tuple(false, true, _, false)) {
        std::cout << "false, true, _, false\n";
    } else {
        std::cout << "else\n";
    }
}

int
main()
{
    f(true, true, true, true);
    f(false, true, true, false);

    return 0;
}

In C++ you often want to consider is there a sensible type that I can create that will help me write my code more easily? Additionally, I think if you have a background in ML you will benefit a lot from examining C++ templates. They are very helpful in applying a functional programming style in C++.

5

C++ is traditionally oriented to the individual, and you could never do anything resembling the following regardless of syntax.

if ([a,b,c,d] == [true,true,false, false]) {}

The New C++ standard has some stuff that lets you define arrays of constants inline, and so it is possible to define a class that will take in an array as a constructor and support such comparisons. Something like

auto x = multi_val({a,b,c,d});
if (x == multi_val({true, true, false, false}))
{ ... }
else if (x == multi_val(etc.))

But now to do partial matches like with the _, that's not directly supported and you'd have to make your class even more complex to fudge with that, like using a maybe template type and going

multi_val(true, true, maybe<bool>(), maybe<bool>)

This gets into rather heady C++ territory and definitely not what I would do for something so elementary.

2

For C++11 assuming that you only want to match a fixed number of booleans and can live without the _ pattern matching then [1] (Expand to the number of variables you require).

I'm still working on an alternate solution using templates to match arbitrary types using lambdas or functors for the expressions.

-Edit-

As promised, [2] pattern matching of arbitrary types incl. unspecified values.

Note a couple of caveats:

  1. This code only works with 4 variables (actually my first foray into template metaprogramming). This could very much be improved with variadic templates.
  2. It works but it's not very tidy or well organised. More a proof of concept that would need to be cleaned up before introducing into production code.
  3. I'm not happy with the match function. I was hoping to use initializer lists to pass the expressions to be evaluated and stop on the first match (with the current implementation every matching condition will be executed) - however i couldn't quickly think of how to pass expression matching objects of different types via the single initializer list.

I can't think of a method for either to validate that the truth table is exhaustive.

Cheers,

-nick

[1]

constexpr int match(bool v, int c)
{
    return v ? (1 << c) : 0;
}
constexpr int match(bool a, bool b)
{
    return match(a, 0) | match(b, 1);
}

int main()
{
    int a = true;
    int b = false;

    switch(match(a, b))
    {
        case match(false, false):
            break;
        case match(false, true):
            break;
        case match(true, false):
            break;
        case match(true, true):
            break;
    }

}

[2]

template<typename V1, typename V2, typename V3, typename V4>
class pattern_match_t
{
private:
    V1 value_0;
    V2 value_1;
    V3 value_2;
    V4 value_3;
public:
    typedef std::function<void(V1, V2, V3, V4)> expr_fn;

    template <typename C1, typename C2, typename C3, typename C4>
    pattern_match_t<V1, V2, V3, V4>& match(C1 a, C2 b, C3 c, C4 d, expr_fn fn)
    {
        if(value_0 == a && value_1 == b && value_2 == c && value_3 == d)
            fn(value_0, value_1, value_2, value_3);
        return *this;
    }

    pattern_match_t(V1 a, V2 b, V3 c, V4 d)
     : value_0(a), value_1(b), value_2(c), value_3(d)
    {
    }
};

template<typename T>
class unspecified
{};

template<typename T>
constexpr bool operator==(unspecified<T>, const T&)
{
    return true;
}

template<typename T>
constexpr bool operator==(const T&, unspecified<T>)
{
    return true;
}

template<typename V1, typename V2, typename V3, typename V4>
pattern_match_t<V1, V2, V3, V4> pattern_match(V1 a, V2 b, V3 c, V4 d)
{
    return pattern_match_t<V1, V2, V3, V4>(a, b, c, d);
}

int main()
{

    bool test_a = true;
    std::string test_b = "some value";
    bool test_c = false;
    bool test_d = true;

    pattern_match(test_a, test_b, test_c, test_d)
        .match(true, unspecified<std::string>(), false, true, [](bool, std::string, bool, bool)
        {
            return;
        })
        .match(true, "some value", false, true, [](bool, std::string, bool, bool)
        {
            return;
        });
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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