fmap API that accepts an arbitrary walk does not use function f

[gaurav-arya]

In the signature fmap(walk::AbstractWalk, f, x, ys...) in the public API, the function f is ultimately not used. Arguably, since this API does not use f, it should be deprecated and replaced by something that is not called fmap (which should be reserved for the special case of an ExcludeWalk where f is applied).

However, these changes should be made with caution due to potentially breaking effects. See the body of PR of #61 for some additional info.

Edit: it's possible #32 helps with a lot of this

[ToucheSir]

I don't remember the exact decision behind this, but @darsnack might.

[darsnack]

That's looks like leftover from before AnonymousWalk but I can't see the commits due to a rebase. Either way, I agree that f should be removed at the least. Probably making the future API "walk-first" by calling the walk directly is better. Calling it a map seems wrong.

[gaurav-arya]

To me, renaming the function to recursivewalk (with the f removed), changing the standard fmap as well as fcollect to call it , and deprecating the fmap with first-arg walk sounds like a very appealing plan and also easy to do without touching the rest of Functors. The name recursivewalk is appealing to me because it turns an arbitrary walk which takes in any recurse function into a walk function which enforces self-recursion.

I'd be interested to hear what other's thoughts are though, because if we make a breaking change let's make sure we're at least doing it right:) also unaware whether or not people have actually been using this API in practice

[ToucheSir]

In my mind and APIs in other programming languages, walk already implies recursive. We do muddy the waters a bit in Functors by turning it into a noun, but if anything that's more reason to not use it for function names.

[gaurav-arya]

Since all the walks are callable structs I think it's fair to call it a verb? (Except with the dispatch hidden as the 0th arg, so hm maybe that's a noun :)

So I guess the first question is if we want to keep the (walk::AbstractWalk)(recurse, xs...) API? I.e. walk a specific node but with an arbitrary recursive function for the children. I was sort of working off that assumption, in which context making the recursion-enforcing version be recursivewalk made some sense (but yeah, I see the verb vs noun inconsistency now...)

[gaurav-arya]

Can I ask how #32 fits into all this?

[darsnack]

Taking in a recurse function separately is what makes the various walks composable.

[gaurav-arya]

I agree, I just thought that there might be other ways of doing the same thing that don't require #61, by replacing recurse with an outer_walk that isn't a fancy closure and is by default equal to the walk itself. This would enforce recursion in the usual walk API with the callable structs, I think.

But I think the current approach is also fine and pretty readable, and more flexible in case that flexibility is somehow needed in the future -- just mentioned it due to @ToucheSir 's comment that walks should enforce self-recursion. (Although actually, do we think this flexibility of allowing something other than recursion is unnecessary?)

What do we think of the general approach of keeping walks.jl as is, deprecating the fmap signature and replacing its functionality with an appropriate verb? (dowalk, runwalk, etc.?)

[gaurav-arya]

Sigh, nerd-sniped myself into doing a prototype of the idea for getting rid of the recurse construction: #63

[gaurav-arya]

Okay, empirical evidence suggests that there does not exists a non-breaking solution beyond keeping the current fancy recurse closure, and just renaming the function something like runwalk and deprecating the old one.

[darsnack]

Yeah storing the outer walk in a field is something I considered in #43, but I decided against it. It can result in silent errors if the walk isn't constructed properly. Part of the usability of fmap(walk, ...) (or recursivewalk(walk, ...)) is that we define the recursion for you so that it works correctly.

[gaurav-arya]

It was really close to non-breaking to simply set walk(x, ys...) to recurse to itself by default, i.e. recurse=walk by default, which didn't require extra fields. Sadly, this broke dispatch for multiple Functors since walk(x, y) was erroneously dispatched to walk(recurse, x), and it would be breaking to require custom walks to annotate recurse::AbstractWalk. So I went with a separate function runwalk for the recurse on itself functionality.

[ToucheSir]

Can I ask how #32 fits into all this?

Absolutely. The core idea is that, much like one can express map(f, list) as foldl((acc, x) -> cat(acc, f(x)), list) for "flat" sequences, one can do the same for structures. So while fmap is currently our lowest-level traversal operation, it can actually be built upon a lower-level folding primitive. Being able to support arbitrary reductions would allow us to support uses like FluxML/Optimisers.jl#57 efficiently.

Implementation-wise, #32 is out of date because it predates all the walk changes that came with Functors 0.4. However, post 0.4 fmap(::AbstractWalk, ...) itself has actually morphed into a sort of fold function—pass the right walk type and it's no longer even a map function! Indeed, you've already noticed this and responded with #65. My main point here is that of naming: FP literature gives us a much richer list of terms to choose from (fold, reduce, traverse, etc) before resorting to the somewhat cumbersome runwalk.

[gaurav-arya]

The way I understand the library, it seems like so long as all these primitives (fold, reduce, traverse, etc.) all ultimately rely on running a recursive walk, they would all still need a low-level primitive that is agnostic to what sort of transform it is doing, like runwalk or some other such name (maybe traverse works? But the point is that the name should be agnostic to the type of transform, since this function really takes absolutely any walk and has no semantics at all beyond recursing that walk). So my thinking in #65 was that this could set the stage for such a redesign of the higher-level transformation primitives, introduction of a ReduceWalk etc. which seems to me a largely orthogonal problem, that would reduce the need for using a lower-level primitive such as runwalk, but presumably still rely on it internally with an appropriately constructed walk? I don't have an immediate need for #65 though and as an end user of the library my main usability issue has been resolved by #59, so happy to hold off if you think a fundamental redesign like #32 should be done first

[gaurav-arya]

In other words,.something like runwalk is an implementation detail, that exposes the barebones implementation chosen by Functors.jl to implement the higher-level functional transforms, to give the user greater flexibility. This flexibility would ideally rarely be needed once the higher-level functional transforms are improved as you say. Is there a good functional analogue to something as flexible as runwalk?

[ToucheSir]

The way I understand the library, it seems like so long as all these primitives (fold, reduce, traverse, etc.) all ultimately rely on running a recursive walk, they would all still need a low-level primitive that is agnostic to what sort of transform it is doing, like runwalk or some other such name (maybe traverse works?)

Well, fundamentally runwalk is a traversal function. That's why StructWalk.jl calls it postwalk and why I put a note about post-order traversal in #32. You're right in identifying that walk customization means it's not strictly a generalized fold, but I'd posit we have better names for this than the literal oxymoron that is runwalk.

[gaurav-arya]

Looking at #32, right, I can see that. (Maybe the cache field should be stripped out of Fold and should be the responsibility of a walk or walk wrapper to make it truly minimal). And the oxymoron point is fair, didn't realize:)

[This was mostly in reply to your original comment. About your edit that it might be more general than a generalized fold: I actually don't clearly see why since your fold looks nearly as minimal as my runwalk barring the cache (ah, maybe it's the isleaf check), but in any case I don't think I have a strong desire for whatever additional functionality is missing from a generalized fold, so the direction #32 is going in makes total sense to me now.]

[CarloLucibello]

So do we have a plan for closing this? #65?