Find an element in a functional set (guile-pfds)

Find an element in a functional set (guile-pfds)

[Zelphir Kaltstahl]

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

RE: Find an element in a functional set (guile-pfds)

[Maxime Devos via General Guile related discussions]

>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.

You can use escape continuations to do an early exit:

;; On success, return stuff-to-return. Otherwise, return the symbol ‘no-match’.
(let/ec escape
  (bbtree-fold [...] [... when a match is found, use (escape stuff-to-return)] [...])
  'no-match)

Best regards,
Maxime Devos.

Re: Find an element in a functional set (guile-pfds)

[Zelphir Kaltstahl]

On 07.07.24 13:01, Maxime Devos wrote:
>
> >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.
>
> You can use escape continuations to do an early exit:
>
> ;; On success, return stuff-to-return. Otherwise, return the symbol ‘no-match’.
>
> (let/ec escape
>
>   (bbtree-fold [...] [... when a match is found, use (escape stuff-to-return)] 
> [...])
>
>   'no-match)
>
> Best regards,
>
> Maxime Devos.
>
Ah what wonderful idea! I did not think of it! Thank you!

There is one more issue though: The underlying tree implementation cannot be 
accessed from the functions exported by the set module. I guess I could get at 
that using some @@ magical thing?

In the end it would still feel a bit like a hack to hack around the limited 
exports of the module, but I guess I would have exported that function anyway, 
had I to write this implementation, so I figure that would be OK.

-- 
repositories:https://notabug.org/ZelphirKaltstahl

Re: Find an element in a functional set (guile-pfds)

[Zelphir Kaltstahl]

On 07.07.24 13:30, Zelphir Kaltstahl wrote:
> On 07.07.24 13:01, Maxime Devos wrote:
>>
>> >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.
>>
>> You can use escape continuations to do an early exit:
>>
>> ;; On success, return stuff-to-return. Otherwise, return the symbol ‘no-match’.
>>
>> (let/ec escape
>>
>>   (bbtree-fold [...] [... when a match is found, use (escape 
>> stuff-to-return)] [...])
>>
>>   'no-match)
>>
>> Best regards,
>>
>> Maxime Devos.
>>
> Ah what wonderful idea! I did not think of it! Thank you!
>
> There is one more issue though: The underlying tree implementation cannot be 
> accessed from the functions exported by the set module. I guess I could get at 
> that using some @@ magical thing?
>
> In the end it would still feel a bit like a hack to hack around the limited 
> exports of the module, but I guess I would have exported that function anyway, 
> had I to write this implementation, so I figure that would be OK.

OK thanks again for the idea with the continuation. I now have a solution in the 
repository and set-find is implemented. Neat!

-- 
repositories: https://notabug.org/ZelphirKaltstahl