I  mean, the search() function is arguably broken in that it is hard
to imagine a worse designed function.  But it does "work".  Did you
read the manual?

https://en.wikibooks.org/wiki/OpenSCAD_User_Manual/Other_Language_Features#Search

As you invoke it in your example you're searching for "M" and "3".
You need to search for ["M3"] if you want to look for the string "M3"
instead of the individual characters.

On Sun, Feb 13, 2022 at 5:12 PM A. Craig West acraigwest@gmail.com wrote:

I misunderstood the documentation when I read it the first time, the
behaviour IS correct. Not very intuitive, but correct...

On Sun, Feb 13, 2022 at 5:24 PM Adrian Mariano avm4@cornell.edu wrote:

Totally agree, I had lots of problems understanding it, and a lot of the wiki is from my
experiments.

But it is also very flexible.

Now if we can only get rid of the Warning when something is not found.
Often not finding something is just as valid as a match.

--
This email has been checked for viruses by AVG.
https://www.avg.com

On Sun, Feb 13, 2022 at 5:31 PM MichaelAtOz oz.at.michael@gmail.com wrote:

The warning is inconsistent. In the version of the code that tgried to
search for the string directly, I got the warning, but if I search for a
list of one string, it does not give the warning.

Actually a lot of the wiki is from my experiments.  There is only a
warning when something is not found if you search for characters of a
string in a list of lists.  This is arguably a useless case anyway, so
it isn't much of a limitation.

As the wiki says, first about the search argument:

Can be a single string value. Search loops over the characters in the
string and searches for each one in the second argument. The second
argument must be a string or a list of lists (this second case is not
recommended). The search function does not search for substrings.

Why is the second case not recommended?  Below it says:

If match_value is a string and this parameter is a list of lists then
the characters of the string are tested against the appropriate index
entry in the list of lists. However, if any characters fail to find a
match a warning message is printed and that return value is excluded
from the output (if num_returns_per_match is 1). This means that the
length of the output is unpredictable.

There is a much more serious limitation.  Suppose you want to search
for 5 in a list:

echo(search([5], [5,7,[5,6]],0));

returns [[0,2]], which means it hits on the both 5 and [5,6].  So if
you actually just want to find matches to 5 you have to go back and
check all the hits and see which ones actually match.  We've had to
do stuff like this in BOSL2 to make things robust.  (What if a list
doesn't contain what you think it does?)

On Sun, Feb 13, 2022 at 5:31 PM MichaelAtOz oz.at.michael@gmail.com wrote:

Yes, it's been done in userspace here:  https://www.thingiverse.com/thing:526023

On Sun, Feb 13, 2022 at 5:36 PM Father Horton fatherhorton@gmail.com wrote:

Sorry, I hadn't looked in a while, at some stage it was my experiments to build on...probably  more
than 8 years ago.

I noticed the warning when someone asked about a very old Thingi
https://www.thingiverse.com/thing:415487  I did in another time, pre warnings.

It checks if text contains letters with a decent so it can offset write() texts position
appropriately.

function decentOther(text) =

                    (search(text,[ ["g"],["j"],["p"],["q"],["y"] ]) == [])

                    ? 0

                    : 1;

At the time the most straight forward test, now a warning for each letter in the text.

--
This email has been checked for viruses by AVG.
https://www.avg.com

Yes, I was definitely building on the work of those who went before with
the wiki.  For your example you just need to rewrite the search as
search(text,"gjpqy").  I can't imagine why anybody thought issuing a
warning when you don't find something was a good idea.  But like I said,
it's a use situation that never needs to be used, so it doesn't create any
limits.  Just don't do that.

On Sun, Feb 13, 2022 at 6:08 PM MichaelAtOz oz.at.michael@gmail.com wrote:

On 2/13/2022 3:14 PM, Adrian Mariano wrote:

Nor can I.  But removing a warning is a compatible change...

The warning itself seems broken because no matter what the string key is it
only warns about the second letter. Or perhaps I don't understand search. I
have never used it because it is pretty incomprehensible to me.

On Mon, 14 Feb 2022 at 16:36, Jordan Brown openscad@jordan.maileater.net
wrote:

I feel certain that I fell into this rabbit hole the first time I tried to
use search for something. I believe my solution then was to wrap it in more
meaningful functions

On Mon, 14 Feb 2022, 11:45 nop head, nop.head@gmail.com wrote:

Yeah, that is surely the way to go.  The trouble is that it's harder
to do than it appears.  Suppose you want to find the first match.  So
you do search([5], [3,4,[5,6],3,5]).  Search returns the index 2
referring to [5,6] which is wrong.  So how do you find the first
match?  You need to look for the second match now?  Or find all
matches from the beginning?  There's not really a good solution.  I
mean, you could assume that this case is rare and just recurse,
looking for the 2nd match if it fails.  But it's complicated.

On Tue, Feb 15, 2022 at 12:10 AM A. Craig West acraigwest@gmail.com wrote:

It's not wrong, it's what it does.
If you have a data in a wrong structure, you will get wrong results. GIGO
So if you only want to operate on atomic entries in an unknown structure of course it is more work.

list=[3,4,[5,6],3,5,7,9,5,4,3];
//    0,1,2    ,3,4,5,6,7,8,9
function searchAtomic(needle,haystack,nth=0) =[
for (i = search([needle], haystack , 1e12) )
for (r = i)
if (!is_list(haystack[r]))
r ][nth];
echo(searchAtomic(5, list));    // 4
echo(searchAtomic(5, list,1));  // 7
echo(searchAtomic(5, list,9));  // undef

--
This email has been checked for viruses by AVG.
https://www.avg.com

If your goal is to write a normal search that returns the items that
actually match, then it's wrong.  The code you show chooses the
option of finding all matches and then looking through that result for
the desired output.  What if your list has a million entries and the
desired result is in position 8, and there are half a million positive
results.  Then maybe that's not an efficient way to do it.  So it it
better to write that method the way you did?  Or is it better to write
it as a recursive function that calls search repeatedly---in principle
a quadratic algorithm.    Or is it better to just write a recursion
that walks the list and looks for the first match and doesn't use
search()?  The point I'm getting at is that the whole benefit of using
search() with the option to return only N hits is that it presumably
can save time vs searching the entire list, and you give up that
advantage if you want actual matches instead of the quirky type
matches it returns.

On Tue, Feb 15, 2022 at 2:12 AM MichaelAtOz oz.at.michael@gmail.com wrote:

"Goal", "normal search", "actually match".
You use the tools available, don't blame the hammer because you want to use a screw.

You miss my point, IF you use appropriate data structures, it works.
If you have garbage structures you get garbage, it is entirely up to you.

search() does as advertised, it is not inherently wrong, use it the right way, it works.

[and you get warnings...just because your choice of haystack is a vector of vectors, does not mean
a non-match is a warning...I argued on GitHub...]

--
This email has been checked for viruses by AVG.
https://www.avg.com

MichaelAtOz oz.at.michael@gmail.com wrote:

You miss my point, IF you use appropriate data structures, it works.

Do your consider garbage a list mixing types, for instance, with singletons
and vectors? Aren't you blaming the patient for a wrong medical diagnosis?

I understand the rationale behind the function search(). It has an argument
index_col_num to allow the specification of the vector component of the
input list entries it should search. Its default is 0, that is, the first
component. But the trouble is we don't have a way to specify the search
target should be just singleton entries. The default value of
index_col_num means we want to search singletons and lists. (It is
interesting that when index_col_num has a value other than 0 singletons
are ignored by search() )

You may not consider that is a wrong design but it is a bad design. A very
bad one.

Function search() should not have a default for index_col_num. If the
argument is missing (undef) it should look just for matching singletons.
And if index_col_num is given, it should look only that entry in vectors.

It is dangerous to use a hammer working sometimes as a hatchet even if you
know this is what it does.

I sense a little more emotion than usual around this topic.  I don't use
Search at all, but as a community we should be able to have this
conversation based solely on the merits of the technical issues at hand.

Jon

On 2/15/2022 11:21 AM, Ronaldo Persiano wrote:

I was imprecise in the alternative behavior of search() I suggested in my
last message. It should be:

Function search() should not have a default value for index_col_num. If
the argument is missing (undef), search() should look just for matching
full list entries (either a singleton or a vector). And if index_col_num is
given, it should look only at the prescribed column of vectors that have
that column.

Despite the disputable warnings, function search() doesn't like to report
errors even when it should. For instance, if some of the arguments
num_returns_per_match or index_col_num is not a positive integer,
the function resets the argument to its default value. That is bad because
the argument value might be defined elsewhere and the bug will not be
evident because search() will silently return a valid response. To report
an error in these cases seems a better choice.

echo(search([5], [[1,2], 5, [5,1]],num_returns_per_match =
"a",index_col_num = []));
// ECHO: [[1, 2]]

Em ter., 15 de fev. de 2022 às 13:21, Ronaldo Persiano <
rcmpersiano@gmail.com> escreveu:

To add a little bit more to what Ronaldo wrote, the problem is being
robust and avoiding unexpected outcomes.  I am a library author and am
not in control of what a user does.  So no, it is not entirely up to
me that the data is valid.  I have to assume the user may do something
stupid.  Also, accidents happen.  You think p is a value but it's a
vector.  You made a mistake.  One can question what the right outcome
is in this case.  Ideally perhaps an error, but the behavior shouldn't
be puzzling and surprising, which unfortunately the behavior of
search() is.

The design of search() is bad because what is arguably the most basic
case is impossible to perform.  You can only do it though fussy
workarounds that compromise the performance.  I would say it's much
more important to fix this than the warning message.

On Tue, Feb 15, 2022 at 7:51 AM MichaelAtOz oz.at.michael@gmail.com wrote:

On 15.02.22 23:11, Jordan Brown wrote:

I'd call the last one the only option.

ciao,
Torsten.

On Tue, Feb 15, 2022, at 5:21 PM, Adrian Mariano avm4@cornell.edu wrote:

It might be instructive to determine when the search facility was added to
OpenSCAD and look at any discussion around it at that time.  Things like
this have a history, and that might explain some things.

If you believe the documentation on search, it’s intent is to be some kind
of generalized facilty for searching. On reading that, my BS detector went
off.  Was it a False Alarm?

It’s treatment of strings as inputs seems at first glance to be somewhat
arcane.  If a single input string results in the matching of the individual
characters of the input string as separate matches, one has to ask why.  If
that’s the intent, aren’t there much better syntactic ways to express such
an idea?.

I’m guessing but the right question to ask about this might be:  Is this a
bug, a design error or something else. If it’s something else, somebody
needs to explain it better than the present documentation.  It’s confusing
some pretty smart people.

-Pat

On 16.02.22 00:02, Patrick Callahan wrote:

What a perfect time to ask that question :-)

The answer is: exactly 10 years ago to the day!

(+/- timezones, clock just rolled over to Feb, 16th here)

For the historians:
https://github.com/openscad/openscad/pull/90

And maybe some more recent discussion here:
https://github.com/openscad/openscad/pull/1318

I'm not sure there's much more use in digging into this
than curiosity.

A more interesting question seems to be what a future
replacement could look like.

ciao,
Torsten.

I would say that the basic search behavior would be that search([x],list)
returns exactly those indices, i,  such that list[i]==x is true.  I think
that's what Ronaldo meant by "matching full list entries".  No special
behaviors relating types or whether things are or are not vectors or
lists.  You never search inside vectors.  You just perform a simple
equality test.  If you search for 5 and an entry in list is [5,5] then
they are different, so it is not a match.  If you search for [5,5] then
[5,5] would be a match in a larger list that might be
[[1,1],[2,2],[3,3,3,3,3],4,5,[5,5]].

On Tue, Feb 15, 2022 at 6:14 PM MichaelAtOz oz.at.michael@gmail.com wrote:

Thanks Torsten!

On Tue, Feb 15, 2022 at 7:21 PM Torsten Paul Torsten.Paul@gmx.de wrote:

History’s important.  I read through it and found it worthwhile.

Replacement or perhaps renaming.  Several have suggested that there are
valid use cases for the search function as written.  The thread contains at
least one example of this from Oz. It might be worth taking a look at
specific examples where it’s used, especially if it’s used in any library.

I’d take a look at the claim of generality in the documentation.  I think
that’s a problem.  Also, the documentation focuses on what the search
does. Perhaps a bit more about how it might be useful would clarify the
current situation.  Certainly those who proposed it and worked on it 10
years ago found it useful.

Note that they also found it buggy and confusing.  Perhaps a move away from
an attempt at generality might help.  Specific language features for
specific types.  More than one kind of search.  Maybe more than one
matching engine and different ways to return the result of the search.

Specific issue I’d take with the current search , . design are the
equivalence of “abc” with [“a”, “b”, “c”].  I’m sure that’s a source of a
whole bunch of confusion.  If it’s needed functionality to re-interpret a
string this way, it should be an option, not a default. "
-pat

On 2/15/2022 4:03 PM, Patrick Callahan wrote:

I assume (without looking at the implementation or historical record)
that the string behavior derives from the fact that OpenSCAD strings
look a lot like arrays.

Consider:

v[3]

len(v)

for (i = v) ...;

which all work on both arrays and strings.

I don't feel like writing one right now, but I suspect that an obvious
implementation of "find the elements of array b that are in array a",
that does not attempt to handle strings, would work with strings exactly
as search() works.

search([1,2,3], [6,4,3,5,2,1])

search("abc", "fdceba")

produce the same result:  [5,4,2].

Obvious?  Perhaps not.  But at least sort of consistent.

On 16.02.22 01:03, Patrick Callahan wrote:

Right, maybe it will stay forever, it certainly has seen
lots of interesting uses and made feature possible that
would not have worked otherwise.

But we also need to consider, there's new features that
maybe just need to be made easier to use, e.g. some of
the "search in array" cases can be done without any new
core feature:

find_index = function(v, pred)
[ for (i = 0;i < len(v);i = i + 1) if (pred(v[i])) i];

first_in_vector = function(v) function(e) e[0] == v;
last_in_vector = function(v) function(e) e[len(e) - 1] == v;

a = [["M3", 3, false], ["M4", 4, true], ["M5", 5, "x", false]];

echo(find_index(a, first_in_vector("M4")));
// ECHO: [1]
echo(find_index(a, last_in_vector(false)));
// ECHO: [0, 2]

ciao,
Torsten.

Maybe leave “search” alone and give the new function a new name? Is “find”
taken?

On Tue, Feb 15, 2022 at 6:38 PM Torsten Paul Torsten.Paul@gmx.de wrote:

Everything that search() does can be done without search() in
userspace, and without function literals.  The whole reason for the
existence of search is that it is fast.  For example, the searchAtomic
posted earlier in the thread is about 500 times slower on a long list
when the item to find is near the beginning, because search() stops
when it finds the item.  The example using find_index with the
function literal is 50 times slower than native search().

Perhaps the idea of first_in_vector() and similar searching functions
would be useful if it were implemented natively in OpenSCAD and ran
really fast, with short circuiting when the item is found.

I tried looking in the BOSL2 source to see what uses of search() I
could find.  Most of them are to find all hits of entire list entries,
it appears.  There are a few that look for first hit, and one or two
that look for first entry of a list of lists.  Some of the "first hit"
uses are just to supply this capability to users---that is, I don't
know if it's actually useful.  Overall I think "find all" entries of a
plain list is the most typical use case.

On Tue, Feb 15, 2022 at 7:38 PM Torsten Paul Torsten.Paul@gmx.de wrote:

Exactly, so adapting existing search() is warranted rather than userspace solutions.

IFF it is a simple fix & doesn't break backward compatibility.

A new find() (e.g.) will not materialise in a hurry.

Function search() should not have a default value for index_col_num.

Unfortunately that would be breakage.

I would say that the basic search behavior would be that search([x],list) returns exactly those
indices, i,  such that list[i]==x is true.  I think that's what Ronaldo meant by "matching full
list entries".  No special behaviors relating types or whether things are or are not vectors or
lists.  You never search inside vectors.  You just perform a simple equality test.

That is not how it was first designed, for better or worse. It can't do that without breakage.

So a parameter exact=true,

search([x],list,exact=true) -> indices, i where list[i]==x, up to num_returns_per_match,

by implication the two must be matching type.

Noting search([x,y],list,exact=true) -> indices i where list[i]==x and list[i]==y, up to
num_returns_per_match

if instead you want to find '[x,y]' you'd do search([[x,y]],list,exact=true) as per the current
usage.

Alternatively, index_col_num=-1, does NOT look inside sublists

search([5], [3,4,[5,6],3,5],,-1) -> [4]

search([[5,6]], [3,4,[5,6],3,5]) -> [2]  as it does now,

search([[5,6]], [3,4,[5,6],3,5],,0)) -> [[2]] ditto (as I think that implies
num_returns_per_match=0)

--
This email has been checked for viruses by AVG.
https://www.avg.com

Em qua., 16 de fev. de 2022 às 02:23, MichaelAtOz oz.at.michael@gmail.com
escreveu:

Why wouldn't index_col_num=-1 also be a breakage ?
Currently (in version 2021.1), all the following calls return [[2,4]] :

search([5], [3,4,[5,6],3,5],0,0)
search([5], [3,4,[5,6],3,5],0,-1)

search([5], [3,4,[5,6],3,5],0,0.5)

search([5], [3,4,[5,6],3,5],0,"a")

search([5], [3,4,[5,6],3,5],0,undef)

search([5], [3,4,[5,6],3,5],0)

Many last year changes broke several existing codes and library functions
as it has been reported here. They were justifiable because they avoided a
spread of undef. So change without breakage is not an unbreakable rule.

What special case requires the current behavior of search of looking at
atomic and vectors when index_col_num=0?

On 2/21/2022 4:11 PM, MichaelAtOz wrote:

search() is difficult to understand at the best of times... gluing on an
additional bit of complexity will make it incrementally worse.

It seems like it should be possible to come up with a find() that's
more understandable and as powerful, or at least nearly as powerful. 
(It would start with treating strings as atomic data items, not as
arrays of characters, at least by default.)

But I admit that I haven't tried to write down what the specification
for such a function would be.

Is it consistent to treat strings as atomic data types?  Right now, if
you want to search for 5 you need to write search([5],...) and if you
want to search for "hello" you do search (["hello"],...) so the
behavior is consistent.

I actually think there's no value in being able to search for multiple
things, and just extra confusion.  There are two reasons for this.
One is that in practice it just never seems to be needed.  In BOSL2 we
never use search() to search for more than one item.  The second
reason is that there is no computational advantage to providing this
feature.  If you really need to search for multiple items you can
use a list comprehension, and the run time is identical.  Instead we
always write search([item],....)[0].  Of course, there's the other
issue that we often might be interested in searching for approximate
matches (within epsilon), which points towards a find function that
looks for a function to be satisfied instead of just simple equality.
I don't know if this ends up being a big enough efficiency gain to
make it worthwhile.  But if we had a find that took a predicate and
returned the entries on which the predicate is true (like was
suggested a ways up) and it ran as fast as search() does right now
with a default predicate of simple equality testing, that seems like
it would be pretty useful, and if you really want to look at the 17th
position in a vector your predicate can do it, so it provides all the
power and more compared to search() without any interface complexity.

Perhaps it could be:  find(search_target, list, num_matches)

where if search_target is a function, it returns all i such that
search_target(list[i]) is true, and otherwise it returns all i such
that list[i]==search_target.

Of course, this is only worthwhile if it's fast the way the current
search() is.  if list can also be a range then you have the
possibility of testing a predicate on a list of values without having
to construct the list first.  Not sure if that gives a speed advantage
or not.

On Mon, Feb 21, 2022 at 7:16 PM Jordan Brown
openscad@jordan.maileater.net wrote:

things, and just extra confusion.

Perhaps, other may think differently, including the original author.

In 2015 clothbot, the author said:

"A few comments/history behind my original writing of search():

When I wrote it (in 2012):

 1. The 'undef' didn't exist as a return option so I settled on returning empty lists which

could be detected (list of length 0) as 'no match' conditions - it predated the Value rewrite of
the code-base.

 2. The 'concat' list construction operator didn't exist; I needed a way to search for a

string-of-characters (aka. an ordered list of character values) and get the results back in order,
as a list.

 3. The 'let' operator didn't exist.

 4. Lists were statically defined; [ for() . ] dynamically generated lists weren't possible.

 5. Function recursion was (and still is to some degree) dog-slow for more 'elegant' list

construction approaches.

 6. The text() module didn't exist.

       - See example023.scad combined with MCAD/fonts.scad for insight into how I was

generating text, and the original motivation behind coding up search().

 7. The no-match warnings are gone as of last week; you'll have to build from source to see

that.

It's not buggy, just written within the constraints of the time. ;-)"

search() is a legacy of its time.

However, changing search() to not match on multiples/sub-vectors, is IMHO too much of a breakage.
There is 10 odd years of search() usage in the wild.

My suggestion provides a means to do atomic search, without breaking 'normal' past usage.

It does not make search simpler, that requires something new, but it give you built-in speed,
likely sooner.

I don't particularly need this, so I'm not wasting my breath any further.

--
This email has been checked for viruses by AVG.
https://www.avg.com

Except to note, I thought I had used search() for something I did a long time ago.

Turns out I used lookup() - key/value match, based on the structured data mechanism in
MCAD/stepper.scad

As long as you work-around* the 'linearly interpolate if there's no exact match' bit, it is another
built-in speed option.

• e.g. using predefined variables as in stepper.scad as the keys.

I never tested performance.

But it is not a generalised search.

--
This email has been checked for viruses by AVG.
https://www.avg.com

Why is important to not break code that uses clumsy syntax in the first place? Why not just get it right?
Cheers, RobW

On 22 February 2022 5:37:29 pm AEDT, MichaelAtOz oz.at.michael@gmail.com wrote:

Yeah, I suspected that the reason for handling lists might have been the
non-existence of list comprehensions.  But that no longer applies.

I would approve of modifying search() to add "atomic search".  I don't
really care which syntax is chosen to make it happen.  I proposed find()
with a function predicate as a way of showing that a simple definition
could be constructed that would be just as powerful as search(), where all
the cases that really never actually arise can be handled by choosing a
suitable function, so you can do everything if you really need to, and in
fact you can do some other useful and interesting things like approximate
search.

In answer to Rob, the reason it's important to not break code is that it
means you have taken someone's working code and made it not work any more.
That's annoying.  My code worked yesterday.  What's going on?  And how do I
fix it?  Why should I care that search() has a stupid syntax if I've got
thousands of lines of code that use it that I've written between 2012 and
today that I'm just using and not re-coding all the time?

On Tue, Feb 22, 2022 at 1:22 AM MichaelAtOz oz.at.michael@gmail.com wrote:

On 2/21/2022 11:27 PM, Rob Ward wrote:

Because it really annoys people when their program that's been working
for years stops working - especially if fixing it makes it incompatible
with older versions of the platform.

Sometimes you just need to bite it and do that, but it's something to be
avoided.  I wouldn't do it for a function, where there's plenty of
namespace and you can just create a new function and relegate the old
one to a "legacy" pile.

On Tue, Feb 22, 2022 at 12:16:01AM +0000, Jordan Brown wrote:

Hmm. I think this would not be the best idea.

I would suggest that a string is an array(vector) of characters.

Now... find would need an argument of "what to find" and an
array of those to find it in.

so if we define:
find (<needle>, <haystack>);

then
find ('s', "haystack");
would find it in the 4th position at index 3.

and
find ("pear", ["apple", "pear", "banana"]);

would find it in the second spot index 1.

I was hoping it would also automatically be able to find substrings,
but writing this convinced me that's something different.

Roger. 

P.S. My mail is down. You'll get this probably (long) after I've
written/sent this.

--
** R.E.Wolff@BitWizard.nl ** https://www.BitWizard.nl/ ** +31-15-2049110 **
**    Delftechpark 11 2628 XJ  Delft, The Netherlands.  KVK: 27239233    **
f equals m times a. When your f is steady, and your m is going down
your a is going up.  -- Chris Hadfield about flying up the space shuttle.

On 2/22/2022 4:38 AM, Rogier Wolff wrote:

Your thinking parallels a discussion that Adrian and I have been having.

Our current thoughts on the "find" function are roughly:

• find(needle, haystack) returns a single integer, or undef if not found.
• find(needle, haystack, some-option) returns multiple matches as a list.
  o Not clear on what some-option is.  Obvious is something like
  "limit=n", perhaps with n=0 meaning "all", but n=0 being "all"
  is a bit wrong and it's not clear that there are real use cases
  for anything other than "first" and "all".  Maybe "all=boolean",
  or maybe find() versus findall().
• needle can be any OpenSCAD value for which equality is defined, or a
  function.
• If needle is a function, it's called for each entry in the haystack,
  and it should return true if the entry matches the desired criteria.
  o Obscure case:  this disallows searching for a function.  If
  you really want to do that, wrap the function and each of the
  elements of the haystack in lists, so that you are searching for
  a list.  Alternatively, use a function to compare with the
  desired function.
• No explicit provision for searching for "any of these".  The use
  case seems limited, and having a list for "needle" is ambiguous with
  searching for a list - especially given the equivalence between
  strings and lists.  Note that you can use a function to implement
  "search for any of these".
• No explicit provision for "search by column".  You can use a
  function.  Also note that objects, when support is added for user
  programs to create them, will address a number of the use cases there.
• find(char, string) will work as you suggest, because of string-list
  equivalence, but is not considered a primary goal.
• substring searches are out of scope.  (But if there was a separate
  substring search function, you could use it in a needle function.)

(Adrian, did I miss any points?)

The case where the needle is a function is very powerful, and can be
used to address a lot of less-common cases.  However, it's not clear how
fast it is - and it looks slow.  Using list comprehension and "for ...
if ..." as a proxy for "find all", it appears that using a function to
do a simple comparison may be over a hundred times slower than a simple
search(), and only slightly faster than a recursive solution.

On 2/25/2022 10:30 AM, Ronaldo Persiano wrote:

I ran a few tests, using list comprehension as a proxy for find().

x = [ for (i = [0:99999], j=[0:99]) i+j ];
//y = search(500, x, num_matches=0);
//y = [ for (v = x) if (v == 500) v ];
//f = function(v) v == 500;
//y = [ for (v = x) if (f(v)) v ];

function f2(x, i=0) =
    i >= len(x)
    ? []
    : x[i] == 500
        ? concat(f2(x, i+1), x[i])
        : f2(x, i+1);
y = f2(x);

and here's the results:

Version
Net time
(not including
constructing x)
search
vs no-function
list comp
vs function
list comp
vs
recursive
search
0.3
-
0.07
0.01x
0.006x
no-function list comprehension
4.3
14x
-
0.1x
0.09x
function list comprehension
43.3
144x
10x
-
0.9x
recursive (scaled to 10M)
~50
167x
12x
1.2x
-

The recursive version blew up on the 10M entry table, so I ran it for 1M
entries and scaled up.

Note that the time for search() is so small that it's probably dominated
by noise.  The primary thing to learn from its results is that search()
is really, really fast.

I don't understand what you mean.  Are you saying that you would
expect a function as "needle" to be as slow as tail recursion
because each one is evaluating the same number of function calls?
Nobody is proposing recursion as playing any part in this process.  I
think Jordan just mentioned it for completeness.

The way I see it, the advantage of search() is speed, resulting from
either early termination if you don't ask for all the hits, or
resulting from search() just being a really fast internal function if
you do want all the hits.

If a find() method were to be added as an alternative/replacement then
it needs to be fast.  The formulation using needle() as a function is
elegant because it allows for any case of interest to be run,
including searching on columns or approximate searching.  But it's
only a good thing if it's still fast.  If it's faster for me to
write a hard coded list comprehension then this alternative isn't very
satisfying.

I don't think the takeaway from Jordan's experiments is that search()
is really fast.  The takeaway is that running within OpenSCAD, using
functions is really slow (100x slower than doing the same thing
without function calls).  That's troubling, and may mean that this
idea won't really be practical.

On Fri, Feb 25, 2022 at 1:30 PM Ronaldo Persiano rcmpersiano@gmail.com wrote:

On 2/25/2022 2:31 PM, Adrian Mariano wrote:

Right:  today, if you want to do an arbitrary search that stops at the
first hit, you have to use recursion.  (An arbitrary search that
doesn't stop at the first hit is naturally a list comprehension, which
makes me wonder whether that's the answer for "find all".)

So the question was "how would find(function, ...) compare to recursion?".

Even with its warts, I'd say that for the simple cases that it handles,
search() is also a lot easier to read and write than the recursive solution.

Hmm.  There's also the question of what's easier to read and write. 
List comprehensions are a lot easier than recursion, but they aren't as
easy as the basic "find" would be.  Whether they are easier than find
with a function as the needle is less clear.  But a list comprehension
also naturally wants to return all hits, requiring a [0] if you only
want one.

I'm sure that there are plenty of search/find applications that process
gazillions of entries, but I expect that there are also some that
process a dozen entries, and for those simplicity would be paramount.

Now, on the other hand, let me scan my work and count the number of
times that I've used search() in an actual project... um, zero. 
Experiments, three.  (Two of which have small tables, and one of which
can have a large (hundreds of thousands) table.)

On 2/25/2022 9:26 AM, Jordan Brown wrote:

For the "find all" case, a list comprehension may be an appropriate
alternative.

A list comprehension with an inline condition is ~10x faster, estimated,
than find with a needle function would be.

OTOH, a find with a constant needle might be as much as 10x faster than
a list comprehension.

The BOSL2 code has 55 invocations of search().  It's sometimes hard to
judge how big the search space is from the grep output, but it's true
that a lot of them are small.  A major use case for search which may
not be small is to compute the index of max() or min(), that is,
search([max(foo)], foo, 1)[0].  Many of the uses are small string
searches, or are lookup table search, e.g. for selecting which
polyhedron to produce in the regular_polyhedron module.  Clearly run
time is irrelevant for cases like this.  The code for determining if a
polygon is clockwise uses search, which could be on a few hundred
points.  If you do that a lot in a loop it could add up.  I suppose
another question is what applications would a generic first-hit search
have if it took a function.  How much benefit is there from having a
search function vs having to write a recursive function?  And how
important is run time there.  I was thinking about search problems
like: given a list of points defining a path, find the segment that is
distance L along the path from one end.  Of course, doing this search
requires state, which is a lot more complicated.

On Fri, Feb 25, 2022 at 6:01 PM Jordan Brown
openscad@jordan.maileater.net wrote: