From: Zelphir Kaltstahl <zelphirkaltstahl@posteo.de>
To: Guile User <guile-user@gnu.org>
Subject: Find an element in a functional set (guile-pfds)
Date: Sun, 7 Jul 2024 10:56:17 +0000 [thread overview]
Message-ID: <0ca50c28-6926-4020-934c-b4ad9c193e92@posteo.de> (raw)
Hello Guile Users!
I have questions regarding sets, functional sets from guile-pfds
(https://github.com/ijp/pfds), to be precise:
Is there a way to "find" an element in the set? I know that the sets are backed
by balanced binary trees in guile-pfds and that those bbtrees have
(bbtree-contains? ...)
(https://github.com/ijp/pfds/blob/master/bbtrees.sls#L581), which should be
capable of giving me a specific element, but only, if I know the key. However,
the problem is, that is expects a key, and not a predicate, that could check any
arbitrary attribute of an item in the tree. Maybe bbtree-fold can be used, but
that would not "early exit" as soon as it has found an item, that satisfies some
specified predicate. And on the set data structure itself, I only see set-fold,
which might be able to be used that way.
What I would like to have is something like find from find from SRFI-1 for
lists, but for functional sets.
Why would I want that?
Because then I would not need to convert form set to list to check, whether the
set contains any element satisfying my predicate. I need the uniqueness property
of sets, but I also need the ability to check whether there is any element, that
satisfies a predicate and I want to use a functional data structure, to avoid
any problems with concurrency. -- Perhaps there is another data structure, that
I could easily implement or even use already, that fulfills these requirements?
My specific use-case is the so called "fringe" (the next nodes to visit) in a
breadth-first search algorithm. Each iteration I need to update the fringe, but
nodes of the previous fringe can have partially the same neighbors and often do
have such, so I want to avoid having duplicates in the fringe, so I used sets.
But then I need to check, whether any node of the fringe satisfies the stop
criteria or goal condition of the search and that is the point, where I
currently convert back to a list. That wouldn't be too critical, if there could
not exist graphs, in which the fringe can become huge, where this can become a
performance problem.
My code is here:
https://codeberg.org/ZelphirKaltstahl/guile-algorithms/src/commit/bf0b4a5482ca28416c24317c6151652eb424e668/search/breadth-first-search.scm
One idea I have is to use both a list and a set. A list to build the actual
fringe and a set to check for uniqueness using (set-member? ...) and only cons
onto the list, if the node is not yet in the set. Then return only the list as
the actual fringe. However, if the fringe is large, that also means using more
memory, for the lack of a better data structure.
I also thought about this (lookup ...) function of bbtrees
(https://github.com/ijp/pfds/blob/master/bbtrees.sls#L184). While it is elegant
to pass in a function that does something to the value that is found by using
the key to search, this does not allow for finding an element that satisfies
arbitrary predicates. But then again it is more natural for a tree structure to
go through the binary tree by comparing keys, which is how it gets to log2(n)
time complexity, if balanced. Hm. And converting the bbtree to a list incurs the
same cost again as set to list conversion, so that is no improvement.
Perhaps I should fork that repository, but I don't understand how binary trees
are balanced in a functional way yet and as such do not understand the
set-underlying data structure yet.
Lastly: Does anyone know what is up with Ian J. Price? (please do not share any
private information, if you have it, if the person it relates to does not
consent) Is there any hope of sending PRs? It seems the maintainer is entirely
unresponsive and I don't yet have their knowledge to improve things. A lot of
studying lies in front of me to get there, I think.
Best regards,
Zelphir
--
repositories: https://notabug.org/ZelphirKaltstahl
next reply other threads:[~2024-07-07 10:56 UTC|newest]
Thread overview: 4+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-07-07 10:56 Zelphir Kaltstahl [this message]
2024-07-07 11:01 ` Find an element in a functional set (guile-pfds) Maxime Devos via General Guile related discussions
2024-07-07 11:30 ` Zelphir Kaltstahl
2024-07-08 19:28 ` 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=0ca50c28-6926-4020-934c-b4ad9c193e92@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).