Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

More efficient implementation of Gen.apply #272

Closed
TysonMN opened this issue Jan 16, 2021 · 2 comments
Closed

More efficient implementation of Gen.apply #272

TysonMN opened this issue Jan 16, 2021 · 2 comments

Comments

@TysonMN
Copy link
Member

TysonMN commented Jan 16, 2021

This is a spin off from #260 (comment).

Gen.apply is currently implemented by calling Gen.bind.

let apply (gf : Gen<'a -> 'b>) (gx : Gen<'a>) : Gen<'b> =
bind gf <| fun f ->
bind gx <| (f >> constant)

This works but doesn't have the best performance. In particular, I think the current implementation exacerbates recursion that lacks tail calls.

@TysonMN
Copy link
Member Author

TysonMN commented Jan 24, 2021

I don't think this is an issue any more for two reasons.

First, I thought implementing apply via bind was possibly the sole cause of why certain code resulted in a stack overflow. It is at not the most fundamental issue since map along suffers from stack overflows (c.f. #289).

Second, I wondered if the applicative behavior of apply and the monadic behavior of bind were different. I now think they are the same.

@TysonMN TysonMN closed this as completed Jan 24, 2021
@TysonMN
Copy link
Member Author

TysonMN commented Dec 20, 2021

Second, I wondered if the applicative behavior of apply and the monadic behavior of bind were different. I now think they are the same.

I was wrong; these behaviors are different. This blog post does a good job explaining the difference.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant