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
