Consider adding index retrieval functions

[vittorioromeo]

I encountered the need of functions that can give me the indices of elements matching a specific predicate in a sequence in a real development situation. I propose the addition of the following functions, whose goal is to allow users to quickly retrieve the indices of elements in sequences depending on a predicate:

• hana::indices_of_matching
• hana::indices_of
• hana::index_of_first_matching
• hana::index_of

---

hana::indices_of_matching(xs, predicate) returns a Sequence containing all the indices of the elements in xs that match predicate.

// pseudocode
hana::indices_of_matching = [](auto&& xs, auto&& predicate) {
        return hana::make_basic_tuple(/* some hana::size_c indices ...*/);
    }

---

hana::indices_of(xs, key) returns a Sequence containing all the indices of the elements in xs that are equal to key.

// pseudocode
hana::indices_of = [](auto&& xs, auto&& key) {
        return hana::make_basic_tuple(/* some hana::size_c indices ...*/);
    }

Satisfies:

indices_of(xs, key) == indices_of_matching(xs, equal.to(key))

---

hana::index_of_first_matching(xs, predicate) returns an hana::optional<hana::size_t> contaning:

• hana::just<x>: if xs contains at least one element matching predicate, where x is the index of the first such element.
• hana::none: if xs does not contain any element matching predicate.

---

hana::index_of(xs, key) returns an hana::optional<hana::size_t> contaning:

• hana::just<x>: if xs contains at least one element equal to key, where x is the index of the first such element.
• hana::none: if xs does not contain any element equal to key.

Satisfies:

index_of(xs, key) == index_of_first_matching(xs, equal.to(key))

---

---

In addition, I propose some functions to "select" a subsequence of elements given a sequence of indices, and functions to invert the selection:

• hana::invert_indices
• hana::slice_inverse

---

hana::invert_indices(xs, indices): given a Sequence xs and a Sequence of indices indices, return the full sequence of xs's indices minus indices. (It "filters out" indices).

Example:

// pseudocode
auto seq = [a, b, c, d, e, f]; // length = 6
auto indices = [0, 3, 4];
auto inv_indices = hana::invert_indices(seq, indices);
assert(inv_indices == [1, 2, 5]);

Satisfies:

length(hana::invert_indices(xs, indices)) == length(xs) - length(indices).

---

hana::slice_inverse(xs, indices): given a Sequence xs and a Sequence of indices indices, returns a subset of xs only containing the elements at positions not in indices.

Satisfies:

hana::slice_inverse(xs, idxs) == hana::slice(xs, hana::invert_indices(xs, idxs)).

[ricejasonf]

I kind of like the name index_if for the function that takes a predicate, of that is not too easily confused with index_of. It would be consistent with existing functions like find_if.

[ldionne]

This has been requested before on StackOverflow. I'll add this to the library in a future version, since there seems to be interest.

[ldionne]

I just needed that again for another StackOverflow question. There really is a need for this.

[ricejasonf]

For that last one, I suggested using a map.

[ScottFreeCode]

I kind of like the name index_if for the function that takes a predicate, of that is not too easily confused with index_of.

I see what you did there. 😆

[ricejasonf]

I can do a PR for index_if if you're interested. I'd almost think that it would have to be for Sequence as Iterable is not necessarily finite.

It could behave like detail::index_if in that it returns an out of bounds index if no element satisfied the predicate.

fwiw I'm currently using detail::index_if to get around not being able to get an element by its type

  template<typename Tag>
  struct get_impl<Tag, hana::when<hana::Searchable<Tag>::value>>
  {
    template <typename Store, typename Key>
    static constexpr decltype(auto) apply(Store&& s, Key&& k)
    {
      if constexpr(hana::Sequence<Store>::value)
      {
        // FIXME using hana::detail
        using Pred = decltype(hana::compose(hana::equal.to(hana::typeid_(k)), hana::typeid_));
        using Pack = typename hana::detail::make_pack<Store>::type;
        return hana::at_c<hana::detail::index_if<Pred, Pack>::value>(
          std::forward<Store>(s)
        );
      }
      else
      {
        return hana::at_key(std::forward<Store>(s), std::forward<Key>(k));
      }
    }
  };

[ldionne]

Would love that. Hmm, could it be defined on Iterables that are also Foldable? Basically, Foldable means they have to be finite, so I think that would do the trick.

Actually, if I think about it, we could also implement if on infinite Iterables, but it would never terminate if the predicate does not return true at a finite index.

[ldionne]

This has been partially addressed by #329.

[ricejasonf]

The indices_of_matching function was also requested here https://stackoverflow.com/questions/44935075/sequence-of-indices-of-tuple-elements-satifying-predicate-in-hana

What if we called it filter_indices? I could see a filtered view using this as well.

If it is welcome I can do a PR for this. Let me know.

I just noticed there is a detail::filter_indices too.

[ldionne]

I'm somewhat uneasy about adding this, since it seems a bit special-purpose. For example, there is nothing like this in the C++ standard library (for iterators), since this can be built easily enough on top of existing algorithms. Also, the SO answer shows:

constexpr auto get_indices_of = [](auto tuple, auto predicate){
    constexpr auto indices = to<tuple_tag>(range_c<std::size_t, 0, size(tuple)>);
    return filter(indices, [=](auto i){ return predicate(tuple[i]); }); 
};

which seems like a perfectly valid (and simple enough) way of implementing this using Hana. I want to be careful to keep the interface somewhat minimal to avoid bloat and loss of consistency.

Out of curiosity, what concept would an hypothetical filter_indices be associated to?

[ricejasonf]

Since it would be just folding an index sequence from an Iterable, I would say it would be for Iterable just like index_if.

I remember you mentioning something about a Sliceable concept a while back that would assume some of the algorithms currently under MonadPlus.

BTW I'm not hardcore for this or anything.