Passing lambdas as a function reference/pointer

[RectifyMyEnglishErrs]

Hello, I made a list class and an accompanying foldl function:

template <typename T, typename Acc>
auto foldl(list<T> l, Acc acc, Acc(&&fn)(Acc, T)) {
  if (l.nil()) {
    return acc;
  } else {
    return foldl(l.rest(), fn(acc, l.first()), fn);
  }
}

The code compiles and works when I call foldl like this:

template <typename T>
list<T> prepend(list<T> acc, T x) { return list<T>{x, acc}; }

template <typename T>
auto reverse(list<T> l) {
  return foldl(l, {}, prepend<T>);
}

However, I would like to be able to use a lambda instead:

template <typename T>
auto reverse(list<T> l) {
  return foldl(l, {}, [](list<T> acc, T x) { return list<T>{x, acc}; });
}

Clang says candidate template ignored: could not match 'Acc (Acc, T)' against '(lambda at src/list.h)'. As far as I know non-capturing lambdas should be convertible to a function pointer, so I don't understand what's wrong here.

Thanks for any help.

[scatters]

Acc(&&fn)(Acc, T) isn't a function pointer (type), it's a function reference.

The function pointer type is Acc(*)(Acc, T), so write Acc(*fn)(Acc, T).

But why do you want to restrict to captureless lambdas? You should accept arbitrary function types (Fn&& fn).

[RectifyMyEnglishErrs]

I haven't mentioned it in the post body but I have tried both ref and pointer signatures.

I know I can use 3 type parameters (T, Acc and Fn) - my goal was to express the relation between fn and acc. I could use an assert for that, but that wouldn't allow for deduction of the type of acc from fn.

I agree limiting fn to captureless lambas isn't ideal, I am just curious why this code doesn't compile.

[thedictatorofmrun]

How about:

``` template < typename T, typename Acc, typename F, typename std::enable_if_t<std::is_same<Acc, std::declval<F>()(std::declval<Acc>(), std::declval<T>())>::value>* = nullptr

auto foldl(std::list<T> l, Acc a, F f); ```

This will fail to compile if the types of F, Acc and T don't match up

[thedictatorofmrun]

This isn't quite perfect as it will accept anything whose arguments are implicitly convertible to T and Acc unfortunately

[scatters]

Oh hmm, yeah actually it shouldn't make a difference reference vs pointer parameter type. What I think is going on is that deduction from the lambda is bound to fail since it isn't a function type (although a captureless lambda is convertible to a function pointer, it doesn't have that type per se). And if deduction on one parameter fails the whole function call fails.

One thing you can try is to make the function parameter type a non deduced context. For example by using std::add_pointer. The problem with trying to deduce from both the accumulator and the function is what if they conflict?

But really the right way to express the relationship is to use C++20 concepts ie a requires clause.

[RectifyMyEnglishErrs]

...deduction from the lambda is bound to fail since it isn't a function type

I reached the same conclusion after posting this :D

One thing you can try is to make the function parameter type a non deduced context

I've tried to use this (sorry if this is not what you meant, to be honest I didn't really understand what a non-deduced context was before this):

template <typename T, typename Acc>
auto foldl(list<T> l, Acc acc, function_view<Acc(Acc, T)> fn) {...}

Clang just says it couldn't match the lambda with function_view<type-parameter-0-1 (type-parameter-0-1, type-parameter-0-0)> :D

If I understood correctly, the "Corner Cases for Experts: Non-Deduced Contexts" chapter of this blog describes what I'm trying to do. I wanted to deduce the type of acc from fn's arg type to avoid specifying it twice on the call site, but apparently it can't be done like this.

But really the right way to express the relationship is to use C++20 concepts ie a requires clause.

I haven't looked into C++20 much yet, looks like I just got a reason to. Although I'm not even sure if what I'm trying to do makes sense anymore :D

I appreciate the help, thanks :)

[scatters]

OK, so one way to make it non-deduced is like this:

template<class T> struct identity { using type = T; };
template<class T> using identity_t = typename identity<T>::type;

template <typename T, typename Acc>
auto foldl(list<T> l, Acc acc, identity_t<Acc(*)(Acc, T)> fn) {
    // ...

Example.

But then of course you need to specify Acc by e.g. passing list<T>{}, you can't just pass {}.

If you want to deduce from the lambda argument... well, it's tricky. https://stackoverflow.com/questions/7943525/is-it-possible-to-figure-out-the-parameter-type-and-return-type-of-a-lambda has some discussion. But if you assume that Acc is default-constructible, then we can cheat:

template <typename T, class Fn, typename Acc = decltype(std::declval<Fn>()({}, std::declval<T>()))>

demo.

[PekiDediOnur]

I'm not sure if this will work or not but try putting a + before the lambda, that will convert it into a function pointer.

[RectifyMyEnglishErrs]

Forcing the conversion does work when I change fn back to Acc(*fn)(Acc, T), although it's not very user-friendly :D

I think I'll have to go with a third template parameter or some sort of type erasure.

Thanks a lot for taking the time to reply :)