unofficial mirror of guile-user@gnu.org 
 help / color / mirror / Atom feed
From: Zelphir Kaltstahl <zelphirkaltstahl@posteo.de>
To: Guile User <guile-user@gnu.org>
Subject: Writing a procedure in different style
Date: Sat, 12 Dec 2020 13:22:20 +0100	[thread overview]
Message-ID: <3760549b-b32f-fafc-1291-8e3eda7b3753@posteo.de> (raw)

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



             reply	other threads:[~2020-12-12 12:22 UTC|newest]

Thread overview: 10+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-12-12 12:22 Zelphir Kaltstahl [this message]
2020-12-13  7:06 ` Writing a procedure in different style Taylan Kammer
2020-12-13 11:51   ` Taylan Kammer
2020-12-13 12:29     ` Zelphir Kaltstahl
2020-12-13 14:24       ` tomas
2020-12-13 15:01         ` Zelphir Kaltstahl
2020-12-13 15:43           ` tomas
2020-12-20 17:57             ` Zelphir Kaltstahl
2020-12-21 12:31               ` tomas
2020-12-21 21:29                 ` Zelphir Kaltstahl

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: https://www.gnu.org/software/guile/

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=3760549b-b32f-fafc-1291-8e3eda7b3753@posteo.de \
    --to=zelphirkaltstahl@posteo.de \
    --cc=guile-user@gnu.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).