Hello Guile Users!
I've been using PEG parsing lately a few times, for advent of code and
needed to write a procedure, which would give me a subtree of the
peg-tree, searching by any criteria. So what I did is writing a
procedure, which takes a predicate and if that predicate is #t then I
would collect the subtree for which it is true into a list.
Problem was, that those subtrees could be on different depths of the
tree, depending on the grammar I defined. So my initial version would
give me back all occurrences of any predicate fulfilling subtree, but in
a list, which was not flat. So I thought for a few hours on and off, how
I could solve it and tried various incantations of (list ...) (cons ...)
and (append ...), for the recursive calls of the procedure, but none
would get the resulting list in ways I wanted. Then I had an idea: I
could use a continuation! I would "flatten" the structure, by giving the
continuation of "where else to look for more subtrees" as an argument
and could later on put it all on the same level. Perhaps this is
difficult to describe and here is my code:
~~~~
(define find-in-tree*
(λ (peg-tree filter-proc)
(define traverse
(λ (subtree cont)
(simple-format (current-output-port)
"working with subtree ~a\n"
subtree)
(cond
[(null? subtree) (cont)]
[(pair? (first subtree))
(traverse (first subtree)
(λ () (traverse (cdr subtree) cont)))]
[(filter-proc (first subtree))
(cons subtree (cont))]
[else
(traverse (cdr subtree) cont)])))
(traverse peg-tree (λ () '()))))
~~~~
(I know, I could probably use a named let here, but somehow I like the
current form of it with the inner define, SICP style.)
(I've only tested this for the parsing here:
https://notabug.org/ZelphirKaltstahl/advent-of-code/src/b676eb5ad7f1c61c84585346ebf36f9fb9f6f8d1/2020/day-07
in puzzle 1. I should probably write some tests for it, for more wildly
nested trees. The procedure is in peg-tree-utils.scm. The program can be
called with `guile -L . puzzle-01.scm input`.)
I am wondering however, whether there is a way to write the procedure
without resorting to mutation (so no hash table or vector) and
continuations. I could not find the correct version without using
continuations. Not that using continuations is inherently bad, I simply
think perhaps there is an alternative version, which is simple, but
which I could not find.
Best wishes,
Zelphir
--
repositories: https://notabug.org/ZelphirKaltstahl
