a low overhead helper function.

[bethandtownes]

Hi kymk

I learnt a bit of functional programming and came up with a few handy functions. And I would like to share them with you. The `fminbnd_if' function below is useful in solving a handful of DP problems. The example problem is from Leetcode 1000 (https://leetcode.com/problems/minimum-cost-to-merge-stones/description/)

#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()

template <typename T, int I, int J, int K> 
using tensor = std::array<std::array<std::array<T, I>, J>, K>;

// type alis for range
template <typename S>
using linear_range = tuple<S, S, S>;

// given a function f and linear range(a, b). find min f(x) for all x such that x in [a, b) and p(x) == true.
template <typename F,
          typename TDomain,
          typename TRange = std::invoke_result_t<F, TDomain>,
          typename UnaryPredicate,
          typename TFallback>
TRange fminbnd_if(const F& f,
                const UnaryPredicate& p,
                const TFallback fallback,
                const linear_range<TDomain>& range) {
  auto [from, to, step] = range;
  if (auto init  = [&]{
    for (TDomain i = from; i < to; i += step) if (p(i)) return make_optional(i);
    return std::optional<TDomain>{};
  }(); not init) return fallback();
  else {
    TRange acc = f(*init); 
    for (int i = *init + step; i < to; i += step) if (p(i)) acc = std::min(acc, f(i));
    return acc;
  }
}

// y combinator for optimizing recursive lambdas.
template <class F>
struct y_combinator {
  F f;

  template <class... Args>
  decltype(auto) operator()(Args&&... args)  const { return f(std::ref(*this), std::forward<Args>(args)...); }

  template <class... Args>
  decltype(auto) operator()(Args&&... args)  { return f(std::ref(*this), std::forward<Args>(args)...); }
};

// deduction guide
template <class F> y_combinator(F) -> y_combinator<F>;

template <typename T>
auto static_range_sum_module(const vector<T>& x) {
  return [&,
          prefix_sum = [&](){
            vector<int> built {0};
            return (std::partial_sum(all(x), std::back_inserter(built)), built); }()](int i, int j) {
    return prefix_sum[j + 1] - prefix_sum[i];
  };
}

class Solution {
 public:
  int mergeStones(vector<int>& stones, int K) {
    const int n = size(stones);
    const int maxk = 30 + 2;
    const int maxs = 30 + 2;

    auto partial_sum_of_stones = static_range_sum_module(stones);

    auto mergable = [&](int i, int j, int m) {
      if (i == j) return m == 1;
      else        return (j - i + 1 - m) % (K - 1) == 0;
    };

    auto f = y_combinator{[&,
                           memo = tensor<optional<int>, maxs, maxs, maxk>{}](auto && f, int i, int j, int m) mutable {
      if (memo[i][j][m])         return *memo[i][j][m];
      if (not mergable(i, j, m)) return -1;
      else if (i == j)           return 0;
      else if (m == 1)           return f(i, j, K) + partial_sum_of_stones(i, j);
      return *(memo[i][j][m] = fminbnd_if([&](int x) { return f(i, x, 1) + f(x + 1, j, m - 1); },
                                          [&](int x) { return (mergable(i, x, 1) and mergable(x + 1, j, m - 1));},
                                          []{ return -1; },
                                          linear_range<int>(i, j, K - 1)));
    }};

    return f(0, n - 1, 1);
  }
};

[kmyk]

fminbnd_if does below, right? For given

• a set X = { a, a + d, a + 2d, …, a + (N - 1)d },
• a totally ordered set Y,
• a function f : X → Y, and
• a predicate p ⊆ X,

fminbnd_if computes min { f(x) | x ∈ X and p(x) } in O(N) if it exists.

---

If my understanding is correct, this fminbnd_if itself is too specific and I'm not so interested. Of course it seems useful for the LeetCode problem, but unusable for other problems.

However, the style of functional programming is good one :+1: This style is useful, and valuable to know even if you don't use the style. By the way, in Haskell, a purely functional programming language, your fminbnd_if can be written just as minimum $ map f $ filter p [from, from + step, to - 1], or like below. If you are interested in functional programming, I recommend try to learn Haskell :smile:

fminbnd_if :: (Num x, Ord y) => (x -> y) -> (x -> Bool) -> y
fminbnd_if f p fallback (from, to, step) =
    let ys = map f $ filter p [from, from + step, to - 1]
    in if ys == [] then fallback else minimum ys

[bethandtownes]

wow. This is really concise code. Too bad that leetcode does not support haskell:( I think in c++20 with ranges c++ will gain similar expressive power coupled with lazy eval. But so far with c++17 standard it might not be possible:((