7
\$\begingroup\$

I'm trying to implement few higher order functions from Haskell in C++. Below are the definitions of takeWhile, groupBy, and group.

I would appreciate it if someone can review and comment if the implementation takes care of all scenarios. Should I be using universal refs for parameters to these functions? Please let me know of any other comments, too. Please assume C++14 standard and above. Also, if there are existing implementations that I can use to study and refer to, please point me to them too.

#include <vector>
#include <utility>

template <typename fwd_iter, typename predicate>
auto takeWhile(fwd_iter first, fwd_iter last, predicate p) -> std::pair<fwd_iter, fwd_iter>
{
    auto till = (first);

    for (; till != last; till++) {
        if (!p(*till)) {
            break;
        }
    }

    return { first, till };
}

// something similar to std::greater or std::less.. is there something for equality??
struct equal {
    template <typename T>
    constexpr bool operator()(const T &lhs, const T &rhs) const
    {
        return lhs == rhs;
    }
};

// predicate type should be : typename *fwd_iter -> typename *fwd_iter  -> bool) 
template <typename fwd_iter, typename predicate, 
    typename container = std::vector<std::pair<fwd_iter, fwd_iter>>>
auto groupBy(fwd_iter first, fwd_iter last, predicate pred)
{
    auto current = first;
    container ret;

    while (current != last) {
        auto t = takeWhile(current, last, [&](auto x) {return pred(*current, x); });
        current = t.second;
        ret.emplace_back(t);
    }

    return ret;
}

template <typename fwd_iter>
auto group (fwd_iter first, fwd_iter last)
{
    return groupBy(first, last, equal());
}
\$\endgroup\$
7
\$\begingroup\$
  1. struct equal is kind of useless. There's std::equal_to, which does the same thing.

  2. You can make the design more flexible (and more standard library-like) by passing an output iterator to the groupBy and group function instead of creating a new container inside the function. It's useful if the user wants to write pairs that represent groups to an existing container or to a C-style array.

\$\endgroup\$
  • 2
    \$\begingroup\$ Isn't (2) one of the reasons why STL functions are not composable? And one of the motivating factors for the ranges library? Returning a container of users choice can be made more composable than the STL style function signature? Please let me know if my understanding is incorrect. Thanks. \$\endgroup\$ – user3169543 Sep 23 '17 at 20:35
  • 2
    \$\begingroup\$ @user3169543 It won't be composable either way (at least, not in way you can compose different functions on sequences in functional programming languages like Haskell). You can always compose them by creating an intermediate container, anyway. It might've been more composable if other functions took containers, not iterators as their inputs (in that case, one would be able to write things like map(f, filter(pred, container))), but it's not the case with the standard library. \$\endgroup\$ – kraskevich Sep 23 '17 at 20:47

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.