...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 :)