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: