Use existing types as base functors when possible

[gelisam]

Part of the Merge yaya into recursion-schemes? thread. Here are the comments from that thread which pertain to the topic.

In the yaya documentation, @sellout says that one advantage of yaya over recursion-schemes is that in yaya:

• pattern functors tend to be named independently of their fixed-points. E.g., we use Maybe directly instead of some NatF, XNor a b instead of ListF, and a `AndMaybe` b instead of NonEmptyF.

@gelisam responds:

That's another big philosophical difference: I think names like ConsF are very important in making the code readable. In fact, I think we should use more specialized names, e.g. data ParaSubTree { originalSubTree :: t, recursiveResult :: a } instead of (t, a), in order to improve the readability further.

@phadej responds:

I think we should use more specialized names, ParaSubTree

That's better argued with an example, e.g. how splitAtCommaSpace in #74 would look like with it?

[gelisam]

how splitAtCommaSpace in #74 would look like with it?

I don't yet have a concrete proposal, this was just to give a flavour for the kind of API I had in mind. Nevertheless, here is what splitAtCommaSpace would look like with ParaSubTree.

-- |
-- >>> splitAtCommaSpace "one, two, three"
-- Just ("one","two, three")
splitAtCommaSpace :: String -> Maybe (String,String)
splitAtCommaSpace = para splitAtCommaSpaceF

splitAtCommaSpaceF :: ListF Char (ParaSubTree String (Maybe (String,String)))
                   -> Maybe (String,String)
splitAtCommaSpaceF (Cons ',' (originalSubTree -> ' ':ys))       = Just ([], ys)
splitAtCommaSpaceF (Cons x   (recursiveResult -> Just (xs,ys))) = Just (x:xs, ys)
splitAtCommaSpaceF _                                            = Nothing

[phadej]

What type `distPara` would have. It looks like introducing names would just obscure types (one have to lookup that `ParaSubTree` is just a pair).

…

Sent from my iPhone

On 2 Feb 2019, at 21.56, Samuel Gélineau ***@***.***> wrote: how splitAtCommaSpace in #74 would look like with it? I don't yet have a concrete proposal, this was just to give a flavour for the kind of API I had in mind. Nevertheless, here is what splitAtCommaSpace would look like with ParaSubTree. -- | -- >>> splitAtCommaSpace "one, two, three" -- Just ("one","two, three") splitAtCommaSpace :: String -> Maybe (String,String) splitAtCommaSpace = para splitAtCommaSpaceF splitAtCommaSpaceF :: ListF Char (ParaSubTree String (Maybe (String,String))) -> Maybe (String,String) splitAtCommaSpaceF (Cons ',' (originalSubTree -> ' ':ys)) = Just ([], ys) splitAtCommaSpaceF (Cons x (recursiveResult -> Just (xs,ys))) = Just (x:xs, ys) splitAtCommaSpaceF _ = Nothing — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or mute the thread.

[gelisam]

I feel like the splitAtCommaSpaceF example didn't really clarify what I am aiming for, and since you're clearly doubtful, I don't think further fleshing out that half-baked proposal would be fruitful, as its half-baked nature means you'll have more than enough ammo to shoot it down. Instead, let me explain the goals which I am hoping a more well-thought-of proposal could achieve. If we agree on the goals, then it will be worthwhile to discuss the concrete details; otherwise, I'll just drop it.

When combining recursion-schemes using distPara and friends, the non-recursive function ends up having access to quite a lot of information about each position. For example, in ghisto (distZygoT g (distZygo h)) f, at each recursive position f has access to the value recursively computed by f at that position, the value computed by g at that position, the value computed by h at that position, the Base t constructor at that position, and for each recursive position in that constructor, the values of f, g, and h, and similarly for all the descendants. When pattern-matching on something as big as Cons x1 (CofreeT (EnvT x2 (EnvT x3 (x4 :< Cons x5 (CofreeT (EnvT x6 (EnvT x7 (x8 :< ...)))))))), it's easy to get lost. So I think it would be much easier if we could instead pattern-match on something smaller like Cons y1 y2, and then from y2 we could drill down to the part we're interested in using optics. For example, to get the value computed by h for the recursive position, we could write something like view (zygoL . _2) y2 (the _2 is because h is the second zygo), and to get the value computed by f for the recursive position of the Cons constructor under that (if it's indeed a Cons), we could write something like preview (histoL . _Cons . cataL) y2.

Similarly, when combining recursion-schemes for unfolds, we end up with a lot of different monadic actions we can perform. For example, in gfutu (distGApoT g distApo) f, the f can either produce a seed, produce an alternate seed which will switch to g, produce a sub-tree, or produce some Base t constructors holding seeds, alternate seeds, and sub-trees. When trying to execute one of those effects, we end up having to construct something big like Cons x1 (FreeT (ExceptT (Right (Right (Free (Cons x2 (FreeT (ExceptT (Right (Left x3)))))))))), where it is again easy to get lost. So I think it would be much easier if we could use mtl constraints to directly name the effects we want to perform, something like Cons x1 (futuM (Cons x2 ()) >> paraM x3). We can already use MonadTrans and MonadFree to write Cons x1 (wrap (Cons x2 (pure ())) >> lift (lift (Left x3))), but I think we can do much better.

Does that sound like a laudable goal?