I have been working on implementing a stack-safe Arrow typeclass, and my current implementation is stack-safe both for function-composition and for evaluation. It's still a work in progress, but you can view it here:
The underlying representation is a GADT binary tree of "composed" functions. This replaces the need for nested closures to represent lazy function composition. Therefore, constructing an Arrow type avoids stack overflow.
Arrow evaluation is also fully tail-recursive. It does this by maintaining its own well-typed stack of continuations (the right-hand side of the binary tree). This allows us to fully evaluate composed Arrow types without blowing the stack.
This abstraction might be useful elsewhere. For example, I have an example of a Lazy monad implemented in terms of Arrow, with a stack-safe bind operation. You can find that here:
Keep in mind that parts of this Arrow typeclass implementation might be flawed. I am going off the Haskell definitions, but don't have much experience with Haskell, so I am certain I've made some mistakes. That said, I'm interested in feedback. If this is a good candidate for inclusion in relude, I would be interested in a more detailed discussion.
I have been working on implementing a stack-safe
Arrowtypeclass, and my current implementation is stack-safe both for function-composition and for evaluation. It's still a work in progress, but you can view it here:https://github.com/austindd/reason-arrow
The underlying representation is a GADT binary tree of "composed" functions. This replaces the need for nested closures to represent lazy function composition. Therefore, constructing an
Arrowtype avoids stack overflow.Arrowevaluation is also fully tail-recursive. It does this by maintaining its own well-typed stack of continuations (the right-hand side of the binary tree). This allows us to fully evaluate composedArrowtypes without blowing the stack.This abstraction might be useful elsewhere. For example, I have an example of a
Lazymonad implemented in terms ofArrow, with a stack-safebindoperation. You can find that here:https://github.com/austindd/reason-arrow/blob/main/src/TestLazy.re
Keep in mind that parts of this
Arrowtypeclass implementation might be flawed. I am going off the Haskell definitions, but don't have much experience with Haskell, so I am certain I've made some mistakes. That said, I'm interested in feedback. If this is a good candidate for inclusion inrelude, I would be interested in a more detailed discussion.