I posted this question in the user mailing list

It was ignored

Is there anything wrong with it ?


Nothing wrong at all. You let the reader know exactly what your problem is and even explain things that not everyone would know. Maybe it's just a slow day on the mailing list. I'll hack around a bit with tree-il, just so I can better see what you mean.


Out of curiosity: what things I explained that not everyone would know ?


"Curly brackets are like parentheses but for dictionary like structures in Clojure"

Since I don't work in Clojure, I appreciate this kind of information. That's all. 😃​


the discussion evolved

take a look at the thread, you might be interested

In my position, it is just my lack of knowledge haha.
Hope you can get help !

@AbbieNormal all of the immutable dictionary-like structures in clojure are trees, a variation called HAMT. there are other types of tree with similar properties that are easier to make, such as AVL and red-black trees. i've never made one in scheme but maybe they exist already?


thank you Alan

note taken

I'll see if there's anything similar in Scheme


@AbbieNormal It's kind of hard to help you without some minimal code example to see what you've tried and reproduce your issue. I don't really understand the "going up" comment either, all tree processing I did so far just needed plain recursion, no backtracking or other tricks of that kind. Neither do I understand why you're bringing up persistent data structures and zippers, they don't seem to be related at all. Some code would surely help clear up that confusion.


As for "going up", please take a look at the procedure I'm referring to

As you can see, its second argument is called "up"

"up" is supposed to be a procedure that will be called when the visit of the tree steps up

And my problem is exactly that I don't know how to write such procedure to pass to "tree-il-fold" as the "up" argument


As for having some code to reproduce the issue, I have no code

The issue is that I don't know how to write the code

The only scrap of code I have does nothing, it only uses pk here and there to understand what is passed to the "down" and "up" procedures


as for persistent data structures and zippers, maybe they aren't actually related at all

I was just trying to figure out which is my use case and which tools i should have used

If I was wrong, no problem

I just want to build a new tree made of cons cells out of a tree-il tree

@AbbieNormal Thanks for the extra context. The docstring of that procedure refers to this PDF which might help you understand the context:

The document suggests that the foldts procedure is designed to be used for context-sensitive transformations of trees, where it's beneficial to know when you descend and ascend in the tree. If you don't need that information, pre-post-order is sufficient for transforming trees, I've used it occasionally to do basic XML processing. So you might be using the wrong procedure for the task.

Finally, looking back at tree-il.scm there's the print-tree-il procedure for pretty-printing the tree. It's using unparse-tree-il internally which uses pattern matching to convert what looks like records into s-expressions. Perhaps you can adapt that for your task?


> So you might be using the wrong procedure for the task.

That's exactly what I needed

Thanks 🙏

I have a hard time in reading papers

I have some sort of reading phobia


As for the print-tree-il procedure, it just prepose the string "#<tree-il ~S> " to the scheme code obtainded by unparsing the tree-il

The result is an articulated string of scheme code that's all but pretty

And by the way, I don't want to print scheme code

I want to print a data structure

No, pre-post-order will do

Thanks again 🙏


Do you think that I should mention this discussion on the mailing list in order to make the community aware of it ?

@AbbieNormal I'd follow up with a short summary what you've found. See on what to avoid :blobcatfingerguns:


Should I post on the mailing list, I'd reply to my own original post andI'd inclde links to the relevant threads here on the fediverse

I've also been suggested to state my intentions to how to make the experience less confusing

I can envision 3 steps:

1) a patch with an example usage of pre-post-order, taken from the Racket documentation, or from Andy Wiongo's paper

I started reading the paper, anyway


2) send a patch to the manual to clarify that the set of use cases covered by pre-post-order and the foldts operators can be seen as distinct

3) finishing reading the paper and possibly send a patch for the manual with examples of usage of the foldts operators too

Yeah, @wasamasa is a nice person and usually apt in such things. that's sound advice!

@AbbieNormal Hi there. I'm not on the #guile mailing list, but I program in both Clojure and Guile (though mostly Clojure).

I'm not familiar with the tree-il structure, but it sounds like you are just trying to replicate a tree structure using lists. This is the most natural thing in the world in just about any Lisp, so I'm guessing your fold-based solution might be slightly overkill here.

@AbbieNormal Here's the usual approach:

1. Define a function process-node that will take a tree-il node as input and returns your desired representation of it, using lists or vectors.

2. Define a function child-nodes that will take a tree-il node as input and returns a list of its immediate children. If there are no children, return an empty list.

@AbbieNormal 3. Define the following depth-first traversal function to convert your tree-il structure into your new list-based tree structure:

(define (tree-il->tree root)
(cons (process-node root)
(map tree-il->tree
(child-nodes root))))

4. Run tree-il->tree on your tree-il's root node to produce a list-based tree. In this structure, the car of each list is the parent node, and the cdr contains a list of all the child nodes.

5. Profit!


yes, tree-il-fold is probably overkill, as was suggested here:

I don't remember if children can be extracted from a tree-il record but I appreciate your suggestion

Thanks 🙏


I've been thinking a bit about this

The reason why I ended up attempting to create a new tree from a tree-il one using tree-il-fold is because I was examinating the code of an lsp server in Guile

Reading that code I stumbled into a use of tree-il-fold


I didn't understand it and felt that in order to study its behaviour I would have needed to have a tree-il pretty printed

And somewhat I ended up assuming that tree-il-fold was a general purpose tool and I could have used it for my use case


Now I can have a tree-il like tree pretty printed but I still need to understand tree-il-fold

Wel i observed the arguments that it passes to "down" and "up" and in what order

I think I understood what it does

Should I make an animation of a tree visit made by tree-il-fold I could envision every stroke

So that's all good

I'm writing this because I felt it was important to document my inner process

@AbbieNormal Hi again. I might suggest taking a step back and thinking about the underlying CS theory here.

In Lisps, we use recursions instead of loops for repeated operations. Note that any loop can be represented with a recursion but every recursion cannot be represented by a loop. Thus recursions are a superset of loops.

@AbbieNormal Looping operations are represented with linear recursions. These are the common operations that we have canonically encoded as map, filter, reduce, and their friends. That is, they traverse linear sequences of data from beginning to end.

@AbbieNormal However branching recursions are the ones that do not map directly to loops. You may remember from CS classes that recursion is usually introduced first to deal with the case of branching recursions because they cannot be easily represented with the imperative for or while loops. This inevitably leads to confusion among a number of students because they are trying to grapple with the new concept of recursion while applying it to the more challenging use case.

@AbbieNormal My point being: Tree traversal of any kind is an operation that by definition relies on branching recursion. Therefore, when you try to traverse it using a linear recursive operation like fold/reduce, you are not much better off than a person trying to accomplish the same task with a for/while loop. You are trying to force the tree to be linear, which is why you are running into trouble here.

@AbbieNormal Now having said all that, I'm going to assume that tree-il-fold has implemented internally a branching recursion that effectively linearizes the tree structure for processing with a fold/reduce operation. You should investigate this implementation and determine whether the order in which it sequences the tree's nodes are what you expect and want. If not, my advice would be to just use standard branching recursive operations like the traversal algorithm I posted.


this paper defines the operator used by tree-il-fold AND by some other procedures for processing sxml !

Sign in to participate in the conversation

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!