Challenge: Recursive and Accumulating Filter - wikitext kin:list:from[]

#1

I’ve posed a similar question before in discussions around kin filter, taggingtree, etc. I use kin:list:to[] and kin:list:from[] extensively in my hierarchical note-taking system. Each sub-bullet is listed in the list field of it’s parent, etc. Each date has it’s own outline like this, and already I have thousands of notes.

I’m always trying to 1. Speed things up, and 2. Replace plugins with wikitext

There were comments by Jeremy and others (Recursive filter operators to show all tiddlers beneath a tag and all tags above a tiddler - #13 by jeremyruston) that the \function was a step in the direction of allowing the building of a recursive “tree walking”. My challenge is to try to build a \function that replicates each of those (kin:list:from[] and kin:list:to[]) essentially exactly that can be invoked in the same way (inline in a filter).

If I have the luxury of knowing what the “root” tiddler is ahead of time, I can use <$wikify> and a bunch of recursive <$list> widgets to produce a nice ordered list that looks the same and works. In speed testing I’ve actually found it to be very slightly slower than kin:list:from[]. That’s a trade-off I’m likely to make though to not have to rely on a (great but 3rd party) plugin that may stop working some day.

My challenge is however that I sometimes need to be able to generate and parse this list within a filter, meaning I sometimes need to generate the name of the root or note mid-filter, generate the ancestors or descendants on the fly, and filter those, then continue on. I’m also frankly just interested to know if this can be done with \function and I’ve spent quite a few hours trying to figure it out, and I can’t seem to let it go…

Attached is a JSON with a tiddler “Macro” that contains walkthroughs of the data (hierarchical tiddlers provided: Note1 > Note1A…) and what I’ve been able to work out so far. Anyone care to take a crack at it for the challenge? Or can anyone with authority confirm that it can’t be done with \function to put my mind at ease?

tiddlers.json (4.9 KB)

#2

Have you tried the taggingtree operator?, search in discourse, I imagin its faster than both kin and wikify methods. Although its still 3rd party something like it could be added to the core, it only itterates tags though, not other tiddler relationships.

I will see what else I can do, I was already working on it. “Maintainin a watching brief” on how to do it, if possible, what you ask. Ever since Jeremy said that.

The thing is if you can make a recurcive filer the output will still just be a list of tiddlers, where with the macro example, you can add in lots of code for various featrures.

#3

Hi @stobot, it would be easier to provide assistance if you could couch your query in more general terms rather than in reference to a third party plugin that not all of us are familiar with.

Here is a quick take on how the desired functionality might be implemented with custom filters but I have had to make some assumptions about your requirements:

\function self.and.offshoots(t) [<t>]  [.offshoots<t>]
\function .offshoots(t) [list<t>] :map:flat[self.and.offshoots<currentTiddler>] 

{{{  [self.and.offshoots[Date]]  }}}
1 Like
#4

That’s brilliant!! I obviously have a lot to learn from this - I feel like I was close, but even when I make small tweaks to this it stops working, so I’ll go deeper.

The only thing that’d make it better would be to know how to change it so that it can be invoked without a parameter and take the incoming title as t. It must be possible somehow…

Meaning, how would I change the \function call self.and.offshoots such that this would work:

{{{ [[Date]self.and.offshoots[]] }}}

Again, my usecase is that instead of knowing the incoming “root” to be Date, I’ll need to dynamically build it using something like an addprefix[] so would want to go right into it. In many cases I can end that run and add a :map:flat to use currentTiddler, but if I could adjust self.and.offshoots, that’d be great.

I had hoped within self.and.offshoots(t) that I could use <currentTiddler> to refer to the incoming input, but that doesn’t seem to be the case. What’s funny is if you make a function like:
\function .double() [[multiply[2]]
and then invoke like {{{ [[3].double[]] }}} then you get 6, so somehow the incoming value is being used within the function call, but I don’t know how to take advantage of that here.

#5

Try this:


\function self.and.offshoots() [all[]]  [.offshoots[]]
\function .offshoots() [get[list]enlist-input[]] :map:flat[self.and.offshoots<currentTiddler>] 

{{{  [[Date]self.and.offshoots[]]  }}}

Note the use of all[] to reference the input title.

1 Like
#6

Perfect - that works!! Thanks so much!!

#7

Note that I made a quick edit to remove the unused parameters to the custom filters.

1 Like
#8

I’ll add one more post here to wrap up in case others find this - as I filled out the “up” direction as well.

\function .down() [all[]] [.down1[]]
\function .down1() [get[list]enlist-input[]] :map:flat[.down<currentTiddler>] 
\function .up() [all[]] [.up1[]]
\function .up1() [all[]] :map:flat[listed[].up[]]

With the above:

  • .down[] functions like kin:list:from[] and
  • .up[] functions like kin:list:to[]

These are very useful if you happen to be organizing things in a hierarchical manner without tags :slight_smile:

4 Likes
#9

It would be interesting to see if this was doable with a single function but the options that come to mind immediately add too much complexity.

Some untested code off the top of my head follows:

Reverse order:

\function self.and.offshoots() [all[]get[list]enlist-input[]reverse[]]  :map:flat[self.and.offshoots[]] [all[]]

{{{  [[Date]self.and.offshoots[]]  }}}

Or using reduce it might look something like this:

\function self.and.offshoots() [all[]get[list]enlist-input[]reverse[]]  :reduce[self.and.offshoots[]reverse[]format:titlelist[]join[ ]addprefix[ ]addprefix<accumulator>] :and[enlist-input[]] [all[]] :and[reverse[]]

{{{  [[Date]self.and.offshoots[]]  }}}

Also do note that none of the code we have discussed in this thread has any recursion protection.

#10

Wow, this worked for me too! Very impressive! I’m going to setup up an environment to do a speed comparison - will come back and report here.

#11

Hi @saqimtiaz, that is a beautiful WikiText solution for recursively traversing lists/tags of a tiddler making use of the new functionality of v5.3.
I added a unique[] filter at the end since :map:flat doesn’t remove duplicates by itself.
I think adding recursion protection would add some complexity, so I’d be willing to use the built-in recursion protection and just remove its warning in the output.

Thus, for grabbing everything under some ancestor tag it would look like this:

\function self.and.offshoots() [all[]]  [.offshoots[]]
\function .offshoots() [tagging[]] :map:flat[self.and.offshoots<currentTiddler>] +[unique[]] -[[/**-- Excessive filter recursion --**/]]

I’d call the .offshoots[] filter directly, as I usually don’t want the original tiddler(s) in the results.

Also note that the taggingtree[] filter plugin was designed to be a speedy alternative to kin[] for special applications (namely: tagging). This WikiText-based approach is about 25 times slower than taggingtree[] in my tests (where no recursions occured). Although it is elegant and nice, I’ll have to stick with the plugin for large wikis…

Yaisog

2 Likes
#12

I would love to use an alternative, unfortunately I don’t have tags in my setup and they wouldn’t make any sense in my context, so I’m stuck looking at alternatives. Unfortunately I don’t have the javascript knowledge to adapt it to not use tags.

#13

Ok, as a numbers guy, I wanted to run a test.

I built a larger data sample using this (in case anyone thinks they can beat the times).

\procedure actions()
<$list filter="[range[0],[9]]">
<$action-setfield $tiddler={{{ [<currentTiddler>addprefix[note_]] }}} list={{{ [range[1],[9]addprefix<currentTiddler>addprefix[note_]join[ ]] }}}/>
<$list filter="[range[0],[9]addprefix<currentTiddler>]">
<$action-setfield $tiddler={{{ [<currentTiddler>addprefix[note_]] }}} list={{{ [range[1],[9]addprefix<currentTiddler>addprefix[note_]join[ ]] }}}/>
<$list filter="[range[0],[9]addprefix<currentTiddler>]">
<$action-setfield $tiddler={{{ [<currentTiddler>addprefix[note_]] }}} text=""/>
</$list>
</$list>
</$list>
<$action-setfield $tiddler="note" list={{{ [range[0],[9]addprefix[note_]join[ ]] }}}/>
\end
<$button actions=<<actions>>>Run</$button>

Then I put each of the options in it’s own tiddler and closed+opened it with performance monitor. The results so far (median over 11 runs each):

kin plugin            : 37.7 ms
list + wikify         : 53.0 ms
Saq's 2-func          : 37.4 ms
Saq's 1-func (reverse): 41.1 ms
Saq's 1-func (second) : 47.6 ms

So, winner so far is the 2-function option that Saq built so far. I’ve only tested the “down” direction so far, though note I use the “up” direction just as often.

Just because I keep getting asked about tags (though I mentioned my inability to use taggingtree in my opening post), my wiki is an outline (like a streams) where every day I write about a 100 notes in a hierarchical way and every note is a sub of another note. It would be silly to make every single note a tag (I currently have ~ 3000 notes) and would totally destroy my “tag space”, so need to rely on the good old “list” field. I do wonder if the reason that something like taggingtree is faster due to javascript, or due to native TW indexing that’s done on tags? Anyone with deep knowledge of caching know that?

#14

It would be interesting to know the relative performance of the very first form that I posted:


\function self.and.offshoots(t) [<t>]  [.offshoots<t>]
\function .offshoots(t) [list<t>] :map:flat[self.and.offshoots<currentTiddler>] 

{{{  [self.and.offshoots[Date]]  }}}
#15

As far as I can see, the recursive functions work with the list field. So they can work with any “list-like” configuration.

Streams does do exactly that. It uses “stream-list” fields. So IMO it’s just a matter of naming variables in functions in the right way.

Just my thoughts

#16

I think “up” will be heavier, since it needs to look into every tiddler, if its title is part of the list-field.

#17

@saqimtiaz: Just tested your original one with it requiring the parameter. It was very slightly (~1%) faster

@pmario: Yes, all the ones shown work with just list. I was referencing how everyone keeps suggesting the use of taggingtree[] which requires tags to be used. Maybe I don’t understand what you’re telling me? Yes, I suspect that “up” will be more because of the less-direct nature, though there’s less to go through (only a fraction of the list to get up to root as siblings along the way are ignored).

#18

I think there is a strong argument for an optimized version of recursion that could use any filter, you can assign the list to a variable and reuse the variable. The result is best depth first and with loop protection.

  • your @pmario TocP approaches this.

@saqimtiaz demonstrating the recurcive functions is fantastic, and offers a “use when needed solution”.

However If we can wring some improved performance by moving it into javascript we should do it.

  • some consideration to multi parent solutions for genealogy is worthwhile.

In this case we are addressing heirachical data structures which are easy to represent in tiddlywiki, but most structures can be represented such as network structures, tables (entity and relationships), look up indexes and more.

  • I would like to see support for querying such structures efficently and clearly
  • no need to build recursion into filters if you can use operators that do the recursion for you.
#19

FYI Tagging tree has a partner tagstree for up.

#20

This leads me to suspect that the faster performance of the JavaScript based version mentioned has little to do with tags and associated indexers (cache) and more to do with the cost of abstraction via wikitext.

While I often think a fair bit about performance as well, make sure you aren’t overoptimizing where it isn’t needed. In itself, 50ms or so for a large dataset is hardly particularly slow when compared to the time it takes to render or refresh the UI. Of course if you use these to render the UI and if your UI uses a fair few of these filters, that can add up.

Streams does all the tree traversal via wikitext and this has never caused noticeable performance issues even in very large streams. Early versions had some performance issues that were addressed almost exclusively by avoiding macros and simplifying the DOM structure.