We can add a safe version based on eval but it won't help in polymorphic functions already based of ...

# arrow-contributors

[raulraja]

We can add a safe version based on eval but it won't help in polymorphic functions already based of ap

[Jannis]

Yeah but that, imo, is fine for library functions like some/many or the implementation of traverse, the only thing that sucks is having to define this for every applicative and also forcing every user to do so for their instances.

[raulraja]

Makes sense

[raulraja]

I dislike Eval

[raulraja]

And we can probably get rid of it with a synthetic trampoline

[raulraja]

That can be injected on demand or something similar that makes it stack safe selectively

[Jannis]

Eval is super ugly, I agree! It also has lots of weird ergonomics when using it... I'm not familiar with trampolines, do you have a link for what you have in mind?

[raulraja]

Making these stack safe by default is a huge perf hit in core infra

[raulraja]

We have in arrow some trampolines in free and AndThen

[raulraja]

Where we jump out of the stack before it blows

[Jannis]

Yeah lazyness unsupported by the runtime is bs

[Jannis]

But that does not help with this case at all doesn't it? The problem is that the argument is strict, not that ap is not stacksafe 😕

[Jannis]

I have a similar problem with flatMap. I am currently working on a small parser combinator library based on megaparsec (which uses a church-encoding and hence builds up a large function tower before being evaled and any recursive parser will overflow it if not explicitly lazy with either lazyAp or lazyFlatmap, which I defined)
And in those cases the problem lies in strict arguments and that can only be solved by having them non-strict (eval) I think

[Jannis]

So after thinking about this for a while: Making a computation like foldRight/ap/traverse etc stacksafe on demand (by jumping stack) will end up trying to fully evaluate the structure, so yes it is stacksafe but not lazy. And laziness is needed when working with both infinite structures and strict arguments causing recursion). One idea with a compiler plugin would be to go a similar route strict-data in haskell goes: Keep everything strict but add laziness explicitly using ~ before the type. We could extend this to replace a function annotated with ~ by a function (same name) prefixed with lazy and since every argument can easily be lifted to eval (using eval later) this could be rather safe. We could even derive lazy variants for combinators that don't inspect the element and just pass it around. So a call to ~map (from applicative) which only passes around it's arguments till it reaches ap would only ever need lazyAp to be manually implemented. Also everyone who does not use this gets no extra overhead apart from having to define lazyApp. Could be a rather elegant solution to missing laziness that obsoletes explicit eval use, but I don't know how well it would work in practice and how hard it is to implement

[raulraja]

That sounds like an excellent direction

[raulraja]

Yeah and with plugins we could do it but we would need to find something else beside ~

[Jannis]

I believe it would actually be possible to completely derive a lazyAp function from an existing ap function by unwrapping the wrapped parameter when it is used (using value). If ap is then written in a form that does not use the params unless needed it would work perfectly. A generated lazyAp for option would look something like this ff.value().flatMap { this.value().map(it) }. (Although I'd propose that we should flip ff and this in that case, as it's usually more desirable to have the second parameter lazy). I'll set me a reminder to look into this when the current compiler plugin stuff is somewhat stable (and when I have more time)

[Jannis]

laziness on demand with autogened functions would be perfect, coupled with stacksafety on demand with what you mentioned earlier it would be crazy powerful