Make FreeApplicative stack safe #1151
Comments
|
I would be interested as well, @adelbertc are there any pointers how to do this? |
|
freeAp might have stack size issue when traversing but the issue might be in traverse method of Array which will be solved in this PR: sanctuary-js/sanctuary-type-classes#19 but you might have issue with quadratic complexity of free applicative on which here are some related issues:
and helpful links: |
|
Recently I have Implemented FreeApplicative (Par in safareli/free#31) which has btw same issue is in scalaz/scalaz#1301 too |
|
Attn @edmundnoble |
|
@safareli Can you explain how your Par implementation works, specifically |
|
@edmundnoble can you clarify this part:
|
|
Eff's implementation of Free, for example, has something akin to |
Hope this makes sense if not let me know: // data Par f a where
// Pure :: {x :: a} -> Par f a
// Lift :: {i :: f a} -> Par f a
// Ap :: {f :: Par f (a -> b), x :: Par f a} -> Par f b
// TypeRep f = { of :: forall a. a -> f a}
// foldPar :: (Applicative g) => Par f a ~> (Ɐ x. f x -> g x, TypeRep g) -> g a
foldPar(f, T) {
// `argsF` contains Par structures which will eventually be applied to some function
const argsF = [this /*:: Par f a */]
// `fns` contains Par structures which resolve to some function
const fns = []
// we have a loop which runs until we have something to return
while (true) {
// we pop last Par object from `argsF`
// we have guaranty that argsF will not be empty here
let argF = argsF.pop()
// if the `argF` is `Ap` node
if (Ap.is(argF)) {
// we get length of argsF {{{{{{{TK add why}}}}}}}
const lengthInitial = argsF.length
// until `argF` is `Ap`
while (Ap.is(argF)) {
// so Ap node of type `Par f b` has structure like this:
// {f :: Par f (a -> b), x :: Par f a}
// so here we try to go dig into `f` part to be able to obtain
// function `a -> b` and in this process we push the `x :: Par f a`
// to `argsF` so if initially `` looked like :
// argsF = [Ap(Ap(Pure(x => y => x + y), Pure(1)), Pure(2))]
// fns = []
// after this loop ends we would have
// argsF = [Pure(2), Pure(1)]
// argF = Pure(x => y => x + y)
argsF.push(argF.x)
argF = argF.f
}
// now as we went as deep as possible in `f` branch of `Ap` node `argF`
// is either `Pure` node with function or `Lift` with some instruction
// in both cases we now need to interpret it i.e create pure value in target
// structure using `of(val, T)` or cal `f` with instruction which will return
// interpret the instruction into target structure. in both cases they will
// eventually produce some function for which we have arguments in `argsF`
// so `foldArg(argF, f, T)` transforms `Free f (a -> b)` into `g (a -> b)`
// and then we create the internal object which contains the `g (a -> b)` and
// number of arguments it needs to take by diffing initial length of argsF
// (which was 0 for the example case 2 so length will be 2) with current length
// if `f = x => new Identity(x)) and `T.of = f` then
// fns at this point will be `[Identity(x => y => x + y)]`
fns.push(Fn(foldArg(argF, f, T), argsF.length - lengthInitial))
// at this point we have "consumed" top `Ap` node from `argsF` and we `continue`
// if there will be `Ap` nodes in the `argsF` this part will try to simplify
// again and again
continue
}
// at this point argT is not Ap node so it's either Pure or Lift which we can
// interpret into g as we did in `Ap` case
const argT = foldArg(argF, f, T)
// if `fns` is empty this means we are done and we return argT
if (fns.length === 0) {
return argT
}
// at this point we must have a function in fns which we pop
let fn = fns.pop()
// and we apply `argT :: g a` to `fn :: g (a -> b)` and we will get `g b`
let res = ap(fn.f, argT)
// we check how meny times we needed to apply to the `fn`
// if it's more then 1 then the `res` contains function (curried) which
// wants to take more arguments which would be in the `argsF`
if (fn.length > 1) {
// so we need to push the `res` to the `fns` but with smaller `length`
// and continue everything
fns.push(Fn(res, fn.length - 1))
continue
}
// at this point the `fn` has no more arguments so we check if there are other
// Par objects which evaluate to some function in `fns` and if we have one
while (fns.length > 0) {
// we pop it from the `fns`
fn = fns.pop()
// and apply `res` to it
res = ap(fn.f, res)
// here we check if result will need more arguments
if (fn.length > 1) {
// in which case we push it to the `fns` with smaller `length`
fns.push(Fn(res, fn.length - 1))
break
}
}
// if we reach this position then and `fns` is empty
if (fns.length === 0) {
// then we are done 🎉
return res
}
}
}
// Internal helper function for foldPar it folds only Pure and Lift nodes
const foldArg = (node, f, T) => {
// check if `node` is `Pure` node and if so
if (Pure.is(node)) {
// take it's pure value and put it in T
// i.e. call `pure`/`return` of the target structure
return of(T, node.x)
// if `node` is `Lift` node then
} else if (Lift.is(node)) {
// we call `f` with instruction contained in the `Lift` node
// with interprets the instruction into target structure and we return it
return f(node.i)
}
}
// Internal helper structure for foldPar it contains an Applicative containing
// a function and information on how many argument it needs
// type Fn g a b = { fun:: g (a -> b), length:: Number}
const Fn = (f, length) => ({ f, length }) |
No description provided.
The text was updated successfully, but these errors were encountered: