Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

bool between(T, U1, U2)(T v, U1 lo, U2 hi)
{
     return v >= lo && v <= hi;
}

uint among(T, Us...)(T v, Us vals)
{
     foreach (i, U; Us)
     {
         if (v == vals[i]) return i + 1;
     }
     return 0;
}

Add?


Andrei

"bearophile" <bearophileHUGS lycos.com> writes:

Andrei Alexandrescu:

 bool between(T, U1, U2)(T v, U1 lo, U2 hi)
 {
     return v >= lo && v <= hi;
 }

I vote a +1 for between(). One use case:

http://rosettacode.org/wiki/Luhn_test_of_credit_card_numbers#Stronger_Statically_Typed_Version

It also helps in the D translation of Python expressions like:

if foo() and 3 < bar(x) < 5 and ...:

That in D need to be split in more lines unless bar() is pure and 
light.

-----------------

Regarding Phobos, currently one of the features I miss mostly is 
an optional template function for the min and max functions:

https://d.puremagic.com/issues/show_bug.cgi?id=4705#c16

Bye,
bearophile

"Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:

On Monday, 16 December 2013 at 21:13:58 UTC, bearophile wrote:

 It also helps in the D translation of Python expressions like:

 if foo() and 3 < bar(x) < 5 and ...:

Not really, it uses "<=" which illustrates why it is better to 
use lambdas where a named function hides what goes on and there 
are several interpretations.

Besides, in many algos you want "low <= x < hi"  or the opposite 
to avoid double-hits on edge-cases.

Walter Bright <newshound2 digitalmars.com> writes:

On 12/16/2013 12:38 PM, Andrei Alexandrescu wrote:
 bool between(T, U1, U2)(T v, U1 lo, U2 hi)
 {
      return v >= lo && v <= hi;
 }

You'd need 4 such functions, < <, < <=, <= <, <= <=, and it just seems like
trivia.

 uint among(T, Us...)(T v, Us vals)
 {
      foreach (i, U; Us)
      {
          if (v == vals[i]) return i + 1;
      }
      return 0;
 }

This has O(n) behavior, which might be unexpected for the user.

Timon Gehr <timon.gehr gmx.ch> writes:

On 12/16/2013 10:45 PM, Walter Bright wrote:
 On 12/16/2013 12:38 PM, Andrei Alexandrescu wrote:
 bool between(T, U1, U2)(T v, U1 lo, U2 hi)
 {
      return v >= lo && v <= hi;
 }

 You'd need 4 such functions, < <, < <=, <= <, <= <=, and it just seems
 like trivia.

 uint among(T, Us...)(T v, Us vals)
 {
      foreach (i, U; Us)
      {
          if (v == vals[i]) return i + 1;
      }
      return 0;
 }

 This has O(n) behavior, which might be unexpected for the user.

Do you mean O(vals.length)? O(vals.length)=O(1).

Walter Bright <newshound2 digitalmars.com> writes:

On 12/16/2013 1:51 PM, Timon Gehr wrote:
 Do you mean O(vals.length)? O(vals.length)=O(1).

I can't argue with both you and Andrei :-)

I withdraw my complaint.

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 12/16/13 1:45 PM, Walter Bright wrote:
 On 12/16/2013 12:38 PM, Andrei Alexandrescu wrote:
 bool between(T, U1, U2)(T v, U1 lo, U2 hi)
 {
      return v >= lo && v <= hi;
 }

 You'd need 4 such functions, < <, < <=, <= <, <= <=, and it just seems
 like trivia.

The behavior is taken from SQL where it's closed both ends.

 uint among(T, Us...)(T v, Us vals)
 {
      foreach (i, U; Us)
      {
          if (v == vals[i]) return i + 1;
      }
      return 0;
 }

 This has O(n) behavior, which might be unexpected for the user.

It's O(1) because the data size is in the source text. There's no 
variable n.

There's quite a bit of evidence in support of among (not as much for 
between) in the source code of Facebook's cpplint, soon to be open 
sourced. Here are some relevant quotes:

bool atBuiltinType(R)(R it) {
   return it.front.type_.among(tk!"double", tk!"float", tk!"int", 
tk!"short",
       tk!"unsigned", tk!"long", tk!"signed", tk!"void", tk!"bool", 
tk!"wchar_t",
       tk!"char") != 0;
}
...
string[] readQualifiedIdentifier(R)(ref R it) {
   string[] result;
   for (; it.front.type_.among(tk!"identifier", tk!"::"); it.popFront) {
     if (it.front.type_ == tk!"identifier") {
       result ~= it.front.value_;
     }
   }
   return result;
}
...
     if (it.front.type_.among(tk!"class", tk!"struct", tk!"union")) {
       result += callback(it, v);
     }
...
     if (it.front.type_.among(tk!"namespace", tk!"class", tk!"struct",
             tk!"union", tk!"{")) {
       auto term = it.find!(x => x.type_ == tk!"{");
       if (term.empty) {
         break;
       }
       it = skipBlock(term);
       continue;
     }
...


             && v[i + 1].value_.among("ifndef", "ifdef"))) {
       ++openIf;

         && v[i + 1].value_ == "endif") {
       ++i; // hop over the else
       --openIf;
     }
...
       auto term = it.find!((t) => t.type_.among(tk!":", tk!"{"));
...
static bool endsClass(CppLexer.TokenType2 tkt) {
   return tkt.among(tk!"\0", tk!"{", tk!";") != 0;
}
...
static bool isAccessSpecifier(CppLexer.TokenType2 tkt) {
   return tkt.among(tk!"private", tk!"public", tk!"protected") != 0;
}
...
       while (i.front.type_.among(tk!"*", tk!"const", tk!"volatile")) {
         i.popFront;
       }

I invite you all to contemplate redoing all these and more from first 
principles.


Andrei

Andrej Mitrovic <andrej.mitrovich gmail.com> writes:

On 12/16/13, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:
 There's quite a bit of evidence in support of among (not as much for
 between) in the source code of Facebook's cpplint, soon to be open
 sourced. Here are some relevant quotes:

From first glance it seems you're always using among when needing a

boolean result, so why does among have to return an index instead of a
boolean true/false?

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 12/16/13 2:38 PM, Andrej Mitrovic wrote:
 On 12/16/13, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:
 There's quite a bit of evidence in support of among (not as much for
 between) in the source code of Facebook's cpplint, soon to be open
 sourced. Here are some relevant quotes:

From first glance it seems you're always using among when needing a

 boolean result, so why does among have to return an index instead of a
 boolean true/false?

More info is better than less info, especially if it comes for free. We 
already use this idiom in a couple of places in Phobos.

Andrei

Marco Leise <Marco.Leise gmx.de> writes:

Am Mon, 16 Dec 2013 14:59:43 -0800
schrieb Andrei Alexandrescu <SeeWebsiteForEmail erdani.org>:

 On 12/16/13 2:38 PM, Andrej Mitrovic wrote:
 On 12/16/13, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:
 There's quite a bit of evidence in support of among (not as much for
 between) in the source code of Facebook's cpplint, soon to be open
 sourced. Here are some relevant quotes:

From first glance it seems you're always using among when needing a

 boolean result, so why does among have to return an index instead of a
 boolean true/false?

 
 More info is better than less info, especially if it comes for free. We 
 already use this idiom in a couple of places in Phobos.
 
 Andrei

I've always preferred findCharInString() to return the "end"
of the string in case the char isn't found instead of e.g. -1,
for two reasons:

a) With an index to the end (equal to the length) you can do
   more useful stuff like:

   auto idx = findCharInString(' ', str);
   str = str[idx .. $];

   -1 requires an explicit if()-branch in any case.

   auto idx = findCharInString(' ', str);
   if (idx == -1) {
     str = ""
   } else {
     str = str[idx .. $];
   }

b) The index becomes size_t again, which is the correct type.

Now similarly I would prefer if among() could do anything else
but shift indexes by +1. Indexes in D are 0 based. Since we
are talking about a verbatim set of options here instead of a
linear string, I could live with -1 as "not in list" and a
zero based index, but then among would have to be renamed to
something that doesn't imply a result that converts to boolean.
"optionIndex" or something.

-- 
Marco

=?UTF-8?B?U2ltZW4gS2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:

On 17.12.2013 15:36, Marco Leise wrote:
 Now similarly I would prefer if among() could do anything else
 but shift indexes by +1. Indexes in D are 0 based. Since we
 are talking about a verbatim set of options here instead of a
 linear string, I could live with -1 as "not in list" and a
 zero based index, but then among would have to be renamed to
 something that doesn't imply a result that converts to boolean.
 "optionIndex" or something.

findAmong? I find 'among' ambiguous - both a boolean result and an index result 
would fit the name, IMO.

-- 
   Simen

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 12/17/13 7:52 AM, Simen Kjærås wrote:
 On 17.12.2013 15:36, Marco Leise wrote:
 Now similarly I would prefer if among() could do anything else
 but shift indexes by +1. Indexes in D are 0 based. Since we
 are talking about a verbatim set of options here instead of a
 linear string, I could live with -1 as "not in list" and a
 zero based index, but then among would have to be renamed to
 something that doesn't imply a result that converts to boolean.
 "optionIndex" or something.

 findAmong? I find 'among' ambiguous - both a boolean result and an index
 result would fit the name, IMO.

I prefer "among". It's a convenience function. The longer the less 
convenient.

Andrei

"Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:

On Tuesday, 17 December 2013 at 14:36:38 UTC, Marco Leise wrote:
 boolean result, so why does among have to return an index 
 instead of a
 boolean true/false?

 
 More info is better than less info, especially if it comes for 
 free. We already use this idiom in a couple of places in 
 Phobos.


But it might not be free if the backend is incapable of reducing 
it because it lacks information. Sometimes just using gotos can 
lead to faster code (if they disappear in the IR of the backend 
after loop-unrolling). So testing and tweaking on different 
backends is kind of important (removing structures that inhibit 
optimization).

Some CPUs also will generate 1 as true for you when doing tests, 
which you in turn can use for indexing to avoid branching, so 
what is free depends on the hardware…

 I've always preferred findCharInString() to return the "end"
 of the string in case the char isn't found instead of e.g. -1,
 for two reasons:

 a) With an index to the end (equal to the length) you can do
    more useful stuff like:

    auto idx = findCharInString(' ', str);
    str = str[idx .. $];

Yep, that is neat, but then you really should name the function 
indexOfCharOrEnd() so you can forget about it when you look at 
the code again. I personally prefer to have boolean alternatives, 
I find the code becomes more readable. And it is sometimes easier 
to optimize a decision-problem than a search-problem.

Still, what is useful depends on what is the common case. When 
writing string validators I just want exceptions and don't even 
care about the result, because the code becomes very easy to 
maintain that way. The result is implied by being able to proceed 
to the next line:

validate_number(record.age);
validate_email(record.email);
database.store(record);

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 12/17/13 6:36 AM, Marco Leise wrote:
 Now similarly I would prefer if among() could do anything else
 but shift indexes by +1.

The function as defined can be used with if (often), or can be used as 
an integral (sometimes). I like that idiom very much.

Andrei

"H. S. Teoh" <hsteoh quickfur.ath.cx> writes:

On Mon, Dec 16, 2013 at 01:45:38PM -0800, Walter Bright wrote:
 On 12/16/2013 12:38 PM, Andrei Alexandrescu wrote:
bool between(T, U1, U2)(T v, U1 lo, U2 hi)
{
     return v >= lo && v <= hi;
}

 
 You'd need 4 such functions, < <, < <=, <= <, <= <=, and it just seems like
trivia.

[...]

	bool between(string op1=">=", string op2="<=", T, U1, U2)
		    (T v, U1, lo, U2 hi)
	{
		return mixin("v" ~ op1 ~ "lo") &&
			mixin("v" ~ op2 ~ "hi");
	}

	x.between(y, z);	// y <= x <= z
	x.between!(">", "<")(y, z);	// y < x < z
	// etc.


T

-- 
"I'm not childish; I'm just in touch with the child within!" - RL

Marco Leise <Marco.Leise gmx.de> writes:

Am Mon, 16 Dec 2013 14:31:16 -0800
schrieb "H. S. Teoh" <hsteoh quickfur.ath.cx>:

 On Mon, Dec 16, 2013 at 01:45:38PM -0800, Walter Bright wrote:
 On 12/16/2013 12:38 PM, Andrei Alexandrescu wrote:
bool between(T, U1, U2)(T v, U1 lo, U2 hi)
{
     return v >= lo && v <= hi;
}

 
 You'd need 4 such functions, < <, < <=, <= <, <= <=, and it just seems like
trivia.

 [...]
 
 	bool between(string op1=">=", string op2="<=", T, U1, U2)
 		    (T v, U1, lo, U2 hi)
 	{
 		return mixin("v" ~ op1 ~ "lo") &&
 			mixin("v" ~ op2 ~ "hi");
 	}
 
 	x.between(y, z);	// y <= x <= z
 	x.between!(">", "<")(y, z);	// y < x < z
 	// etc.
 
 
 T

Compare:

a) import std.something; x.between!(">", "<")(y, z);
b) y < x && x < z

now which would you use? :-)

-- 
Marco

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 12/17/13 6:38 AM, Marco Leise wrote:
 Compare:

 a) import std.something; x.between!(">", "<")(y, z);
 b) y < x && x < z

 now which would you use? :-)

x.between!("><")(y, z);

would have the advantage of the South Park emoticon.

Andrei

Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:

On 17/12/13 19:08, Andrei Alexandrescu wrote:
 x.between!("><")(y, z);

 would have the advantage of the South Park emoticon.

To be defined in the std.unclefucker module? :-)

"Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:

On Monday, 16 December 2013 at 21:45:40 UTC, Walter Bright wrote:
 uint among(T, Us...)(T v, Us vals)
 {
     foreach (i, U; Us)
     {
         if (v == vals[i]) return i + 1;
     }
     return 0;
 }

 This has O(n) behavior, which might be unexpected for the user.

I would expect one table-lookup for this if vals contains 
strings, not N ifs. If you look at the example, most of them 
could be done with perfect hashing on a single character.

Is it possible for the compiler/template system to turn this into 
a switch/dictionary? Or is there something in the 
language/compiler that makes that impossible?

(I am not trying to be clever, I am curious)

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 12/16/13 2:55 PM, "Ola Fosheim Grøstad" 
<ola.fosheim.grostad+dlang gmail.com>" wrote:
 On Monday, 16 December 2013 at 21:45:40 UTC, Walter Bright wrote:
 uint among(T, Us...)(T v, Us vals)
 {
     foreach (i, U; Us)
     {
         if (v == vals[i]) return i + 1;
     }
     return 0;
 }

 This has O(n) behavior, which might be unexpected for the user.

 I would expect one table-lookup for this if vals contains strings, not N
 ifs. If you look at the example, most of them could be done with perfect
 hashing on a single character.

 Is it possible for the compiler/template system to turn this into a
 switch/dictionary? Or is there something in the language/compiler that
 makes that impossible?

It's a good idea, but unfortunately we don't have partial evaluation. 
We'd need to move whatever compile-time work is to be done in the 
template arguments area, i.e.

value.among!("foo", "bar", "baz")

as opposed to

value.among("foo", "bar", "baz")

Now that I think of it we can easily support both forms.



Andrei

"Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:

On Monday, 16 December 2013 at 23:04:09 UTC, Andrei Alexandrescu 
wrote:
 It's a good idea, but unfortunately we don't have partial 
 evaluation. We'd need to move whatever compile-time work is to 
 be done in the template arguments area, i.e.

When I think of it, it might be better to let the compiler detect 
it and do this as a general optimization. Because you might be 
able to collapse two consecutive among() into a single lookup if 
the code-structure allows for it. So an early library 
optimization could reduce the ability to optimize at a later 
stage… *shrug*

Walter Bright <newshound2 digitalmars.com> writes:

On 12/16/2013 4:01 PM, "Ola Fosheim Grøstad" 
<ola.fosheim.grostad+dlang gmail.com>" wrote:
 When I think of it, it might be better to let the compiler detect it and do
this
 as a general optimization. Because you might be able to collapse two
consecutive
 among() into a single lookup if the code-structure allows for it. So an early
 library optimization could reduce the ability to optimize at a later stage…
*shrug*

It definitely is a good idea for the compiler to recognize:

    if (s == "foo" || s == "bar" || s == "baz")

and generate special code for it.

"Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:

On Tuesday, 17 December 2013 at 00:53:07 UTC, Walter Bright wrote:
 It definitely is a good idea for the compiler to recognize:

    if (s == "foo" || s == "bar" || s == "baz")

 and generate special code for it.

I guess that would work in this case if among() is inlined since
the integer is then used as a boolean and can be reduced to the
same value (true). If it isn't inlined you would deal with 
(pseudo):

r=0;
if(s=="foo"){ r=1; goto e;}
if(s=="bar"){ r=2; goto e;}
if(s=="baz"){ r=3; goto e;}
e:
return r

So it would be more general to optimize conditionals that test
the same (unchanged) variable into a switch() and then if
possible reduce that to a table lookup if each basic block in the
switch sets the same variables to a constant value…

I guess a fast bool variation could be something like (pseudo):

// skip the length test if s[2] on an empty string doesn't 
core-dump.
if(s.length<3) return false;
return lut[ (s[2]-'o') & MASK] == s;


(the NNTP server or the web-interface seemed to be dead for 12 
hours?)

Marco Leise <Marco.Leise gmx.de> writes:

Am Mon, 16 Dec 2013 15:04:09 -0800
schrieb Andrei Alexandrescu <SeeWebsiteForEmail erdani.org>:

 On 12/16/13 2:55 PM, "Ola Fosheim Gr=C3=B8stad"=20
 <ola.fosheim.grostad+dlang gmail.com>" wrote:
 On Monday, 16 December 2013 at 21:45:40 UTC, Walter Bright wrote:
 uint among(T, Us...)(T v, Us vals)
 {
     foreach (i, U; Us)
     {
         if (v =3D=3D vals[i]) return i + 1;
     }
     return 0;
 }

 This has O(n) behavior, which might be unexpected for the user.

 I would expect one table-lookup for this if vals contains strings, not N
 ifs. If you look at the example, most of them could be done with perfect
 hashing on a single character.

 Is it possible for the compiler/template system to turn this into a
 switch/dictionary? Or is there something in the language/compiler that
 makes that impossible?

=20
 It's a good idea, but unfortunately we don't have partial evaluation.=20
 We'd need to move whatever compile-time work is to be done in the=20
 template arguments area, i.e.
=20
 value.among!("foo", "bar", "baz")
=20
 as opposed to
=20
 value.among("foo", "bar", "baz")
=20
 Now that I think of it we can easily support both forms.
=20
=20
=20
 Andrei

This works well in general. I did the same for writing bits
to a stream:

writeBits()(uint bits, uint value)
writeBits(uint bits)(uint value)

(Now with 2.064 the empty template parenthesis can be omitted.)
Knowing that the bit count is 9 or less, you can optimize for a
case that only writes to two bytes. The one bit case doesn't
even need branching at all.

--=20
Marco

"Brad Anderson" <eco gnuk.net> writes:

On Monday, 16 December 2013 at 20:38:52 UTC, Andrei Alexandrescu 
wrote:
 bool between(T, U1, U2)(T v, U1 lo, U2 hi)
 {
     return v >= lo && v <= hi;
 }

I must say that:

     if (val.between(3, 10))

sure is a lot easier to understand at a glance than:

     if (val >= 3 && val <= 10)

Although there is a problem with the word "between" not being 
clear about whether it is inclusive or not.

I do kind of enjoy the Ruby-style DSL-lite they use to make code 
more readable so I'm for it.

"Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:

On Monday, 16 December 2013 at 21:47:35 UTC, Brad Anderson wrote:
     if (val >= 3 && val <= 10)

if (3 <= val && val <= 10)

Pretty clear.

Timon Gehr <timon.gehr gmx.ch> writes:

On 12/16/2013 10:47 PM, Brad Anderson wrote:
 On Monday, 16 December 2013 at 20:38:52 UTC, Andrei Alexandrescu wrote:
 bool between(T, U1, U2)(T v, U1 lo, U2 hi)
 {
     return v >= lo && v <= hi;
 }

 I must say that:

      if (val.between(3, 10))

 sure is a lot easier to understand at a glance than:

      if (val >= 3 && val <= 10)
 ...

if (3 <= val && val <= 10)

is similarly easy to understand at a glance as the former. (Its drawback 
compared to that is that often a temporary variable will be required to 
be introduced in order to avoid recomputation.)

Walter Bright <newshound2 digitalmars.com> writes:

On 12/16/2013 1:47 PM, Brad Anderson wrote:
 On Monday, 16 December 2013 at 20:38:52 UTC, Andrei Alexandrescu wrote:
 bool between(T, U1, U2)(T v, U1 lo, U2 hi)
 {
     return v >= lo && v <= hi;
 }

 I must say that:

      if (val.between(3, 10))

 sure is a lot easier to understand at a glance than:

      if (val >= 3 && val <= 10)

 Although there is a problem with the word "between" not being clear about
 whether it is inclusive or not.

Exactly, meaning I'd have to go look at the source code for it, whereas with
the 
latter I can see right away what it is. The function is a net programmer time
loss.

"Jakob Ovrum" <jakobovrum gmail.com> writes:

On Monday, 16 December 2013 at 22:10:28 UTC, Walter Bright wrote:
 Exactly, meaning I'd have to go look at the source code for it, 
 whereas with the latter I can see right away what it is. The 
 function is a net programmer time loss.

Surely you would turn to the documentation, not the source code. 
We could make it require the bounds template parameter, so it 
would always be required to use it like:

if(val.between!"[)"(0, 10))
    ...

However, with a good, solid default that is easy to remember, I 
wouldn't mind having a default argument for the bounds.

At any rate, the implementation of `among` should probably be 
something closer to:

---
uint among(T, Values...)(auto ref T value, auto ref Values values)
     if(!is(CommonType!(T, Values) == void))
{
     foreach(uint i, ref v; values)
     {
         if(value == v) return i + 1;
     }

     return 0;
}
---

It would of course be even better if we had a nice and clear way 
to express that all types in Values must be equatable (?) with T, 
something like `allSatisfy!(isComparable!("==", T), Values)`, 
where `isComparable` is the missing link.

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 12/16/13 2:24 PM, Jakob Ovrum wrote:
 On Monday, 16 December 2013 at 22:10:28 UTC, Walter Bright wrote:
 Exactly, meaning I'd have to go look at the source code for it,
 whereas with the latter I can see right away what it is. The function
 is a net programmer time loss.

 Surely you would turn to the documentation, not the source code. We
 could make it require the bounds template parameter, so it would always
 be required to use it like:

 if(val.between!"[)"(0, 10))
     ...

 However, with a good, solid default that is easy to remember, I wouldn't
 mind having a default argument for the bounds.

I guess if we need several versions of between, we could give up on it.

 At any rate, the implementation of `among` should probably be something
 closer to:

 ---
 uint among(T, Values...)(auto ref T value, auto ref Values values)
      if(!is(CommonType!(T, Values) == void))
 {
      foreach(uint i, ref v; values)
      {
          if(value == v) return i + 1;
      }

      return 0;
 }
 ---

 It would of course be even better if we had a nice and clear way to
 express that all types in Values must be equatable (?) with T, something
 like `allSatisfy!(isComparable!("==", T), Values)`, where `isComparable`
 is the missing link.

A custom predicate defaulted to '==' would be the ticket.


Andrei

Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:

On 16/12/13 23:30, Andrei Alexandrescu wrote:
 I guess if we need several versions of between, we could give up on it.

What's wrong with having it implemented analogous to std.random.uniform -- 
taking a bounds parameter which allows for open and/or closed at either end, 
with the default being "[)" ... ?

By the way, I'd also like to see that open/closed-at-either-end specialization 
extended to std.range.iota().

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 12/16/13 2:39 PM, Joseph Rushton Wakeling wrote:
 On 16/12/13 23:30, Andrei Alexandrescu wrote:
 I guess if we need several versions of between, we could give up on it.

 What's wrong with having it implemented analogous to std.random.uniform
 -- taking a bounds parameter which allows for open and/or closed at
 either end, with the default being "[)" ... ?

Too much sophistication for too trivial work. One between would be fine. 
Four would be probably overdoing it. So I'm retracting my proposal for 
between.

Andrei

"bearophile" <bearophileHUGS lycos.com> writes:

Andrei Alexandrescu:

 Too much sophistication for too trivial work. One between would 
 be fine. Four would be probably overdoing it. So I'm retracting 
 my proposal for between.

Regarding "between", in Bugzilla I suggested to add "in" operator 
overloading to iota:

5 in iota(5, 12)

And elsewhere in Bugzilla I suggested to give the "[]" to iota:

5 in iota!"[]"(5, 12)

https://d.puremagic.com/issues/show_bug.cgi?id=11252
https://d.puremagic.com/issues/show_bug.cgi?id=10466

Bye,
bearophile

"H. S. Teoh" <hsteoh quickfur.ath.cx> writes:

On Mon, Dec 16, 2013 at 11:39:56PM +0100, Joseph Rushton Wakeling wrote:
 On 16/12/13 23:30, Andrei Alexandrescu wrote:
I guess if we need several versions of between, we could give up on it.

 
 What's wrong with having it implemented analogous to
 std.random.uniform -- taking a bounds parameter which allows for
 open and/or closed at either end, with the default being "[)" ... ?
 
 By the way, I'd also like to see that open/closed-at-either-end
 specialization extended to std.range.iota().

Oooh, do I hear a volunteer for cleaning up iota? ;-)

While you're at it, you might as well implement:

	https://d.puremagic.com/issues/show_bug.cgi?id=10762

:-P


T

-- 
The peace of mind---from knowing that viruses which exploit Microsoft system
vulnerabilities cannot touch Linux---is priceless. -- Frustrated system
administrator.

Walter Bright <newshound2 digitalmars.com> writes:

On 12/16/2013 2:51 PM, H. S. Teoh wrote:
 Oooh, do I hear a volunteer for cleaning up iota? ;-)

I'm not giving in one iota!

"Francesco Cattoglio" <francesco.cattoglio gmail.com> writes:

On Monday, 16 December 2013 at 22:53:24 UTC, H. S. Teoh wrote:
 What's wrong with having it implemented analogous to
 std.random.uniform -- taking a bounds parameter which allows 
 for
 open and/or closed at either end, with the default being "[)" 
 ... ?
 
 By the way, I'd also like to see that open/closed-at-either-end
 specialization extended to std.range.iota().

 Oooh, do I hear a volunteer for cleaning up iota? ;-)

 While you're at it, you might as well implement:

 	https://d.puremagic.com/issues/show_bug.cgi?id=10762

 :-P


 T

Well, I might actually volunteer :)
Any pointer about implementing that enhancement? Can one just 
forgot about the different versions (one for integrals, one for 
floating points) and just implement the One True Iota?

=?UTF-8?B?U2ltZW4gS2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:

On 17.12.2013 16:22, Francesco Cattoglio wrote:
 On Monday, 16 December 2013 at 22:53:24 UTC, H. S. Teoh wrote:
 What's wrong with having it implemented analogous to
 std.random.uniform -- taking a bounds parameter which allows for
 open and/or closed at either end, with the default being "[)" ... ?

 By the way, I'd also like to see that open/closed-at-either-end
 specialization extended to std.range.iota().

 Oooh, do I hear a volunteer for cleaning up iota? ;-)

 While you're at it, you might as well implement:

     https://d.puremagic.com/issues/show_bug.cgi?id=10762

 :-P


 T

 Well, I might actually volunteer :)
 Any pointer about implementing that enhancement? Can one just forgot about the
 different versions (one for integrals, one for floating points) and just
 implement the One True Iota?

One problem of OTI (One True Iota) is floating-point inaccuracies. What does 
this function return? (hint: it's not 16777217)

float foo() {
     return 16777216f + 1.0f;
}

So if you want iota(16777217f, 16777245f, 1.0f) to not go into an infinite
loop, 
you will probably need to special-case floating-point. If you assume that you 
can duplicate whatever is passed to iota, you could do something like this:


T _front;
size_t _index;
U _step;

void popFront() {
    ++_index;
    if (_front + _index * _step != _front) {
        _front += _index * _step;
        _index = 0;
    }
}

I don't think even this covers all bases (consider the case where the
inaccuracy 
of real is > size_t.max).

I'm playing with writing a new iota now too. Could be fun to see what different 
solutions people come up with.

-- 
   Simen

"H. S. Teoh" <hsteoh quickfur.ath.cx> writes:

On Tue, Dec 17, 2013 at 04:58:10PM +0100, Simen Kj�r�s wrote:
 On 17.12.2013 16:22, Francesco Cattoglio wrote:
On Monday, 16 December 2013 at 22:53:24 UTC, H. S. Teoh wrote:
What's wrong with having it implemented analogous to
std.random.uniform -- taking a bounds parameter which allows for
open and/or closed at either end, with the default being "[)" ... ?

By the way, I'd also like to see that open/closed-at-either-end
specialization extended to std.range.iota().

Oooh, do I hear a volunteer for cleaning up iota? ;-)

While you're at it, you might as well implement:

    https://d.puremagic.com/issues/show_bug.cgi?id=10762

:-P


T

Well, I might actually volunteer :)
Any pointer about implementing that enhancement? Can one just forgot
about the different versions (one for integrals, one for floating
points) and just implement the One True Iota?

 
 One problem of OTI (One True Iota) is floating-point inaccuracies.
 What does this function return? (hint: it's not 16777217)
 
 float foo() {
     return 16777216f + 1.0f;
 }
 
 So if you want iota(16777217f, 16777245f, 1.0f) to not go into an
 infinite loop, you will probably need to special-case
 floating-point. If you assume that you can duplicate whatever is
 passed to iota, you could do something like this:
 
 
 T _front;
 size_t _index;
 U _step;
 
 void popFront() {
    ++_index;
    if (_front + _index * _step != _front) {
        _front += _index * _step;
        _index = 0;
    }
 }
 
 I don't think even this covers all bases (consider the case where
 the inaccuracy of real is > size_t.max).
 
 I'm playing with writing a new iota now too. Could be fun to see
 what different solutions people come up with.

[...]

Maybe this should be a community effort. Let each of us come up with a
new iota, and we can compare and incorporate each other's ideas to
produce the best implementation. How's that?


T

-- 
Life is unfair. Ask too much from it, and it may decide you don't deserve what
you have now either.

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 12/17/13 8:26 AM, H. S. Teoh wrote:
 Maybe this should be a community effort. Let each of us come up with a
 new iota, and we can compare and incorporate each other's ideas to
 produce the best implementation. How's that?

I think the deal with "a in iota(b, c)" gets odd quite fast if e.g. 
those are floating-point numbers and the questions shows up whether a 
must be exactly a value obtained by iterating from b to c.

Andrei

"H. S. Teoh" <hsteoh quickfur.ath.cx> writes:

On Tue, Dec 17, 2013 at 10:13:43AM -0800, Andrei Alexandrescu wrote:
 On 12/17/13 8:26 AM, H. S. Teoh wrote:
Maybe this should be a community effort. Let each of us come up with
a new iota, and we can compare and incorporate each other's ideas to
produce the best implementation. How's that?

 
 I think the deal with "a in iota(b, c)" gets odd quite fast if e.g.
 those are floating-point numbers and the questions shows up whether a
 must be exactly a value obtained by iterating from b to c.

[...]

Sorry, I was talking about improving iota support for non-builtin types
that support ++ or +/*.

I don't agree that "a in iota(b,c)" is a good idea; it looks cute but
hides a potential performance hit if not properly implemented. Iota is
for iteration, not for general representation of numerical ranges. And
yes, when floating-point values are involved, it quickly becomes quite
nasty.  So I vote against it in favor of between(). Specifically, this
variant among those proposed:

	bool between(string bounds="[]", T, U, V)(T val, U lower, V upper);

	unittest
	{
		assert(1.between(0u, 2.0f));	// should work with mixed types
		assert(3.14.between(3u, BigInt(4)); // and library types
	}


T

-- 
Stop staring at me like that! It's offens... no, you'll hurt your eyes!

Walter Bright <newshound2 digitalmars.com> writes:

On 12/16/2013 2:24 PM, Jakob Ovrum wrote:
 On Monday, 16 December 2013 at 22:10:28 UTC, Walter Bright wrote:
 Exactly, meaning I'd have to go look at the source code for it, whereas with
 the latter I can see right away what it is. The function is a net programmer
 time loss.

 Surely you would turn to the documentation, not the source code.

I hate to say it, but often when I read the Phobos library documentation I wind 
up having to check the source code. Yes, I should follow my own advice and do
PRs.

"Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:

On Monday, 16 December 2013 at 23:01:36 UTC, Walter Bright wrote:
 I hate to say it, but often when I read the Phobos library 
 documentation I wind up having to check the source code. Yes, I 
 should follow my own advice and do PRs.

You should consider having direct links to html-formatted source 
code from the documentation. Like this:

http://webapp-improved.appspot.com/api/webapp2_extras/json.html

I find that simple "[source]"-link to be a very helpful solution. 
It is very difficult to make good enough documentation to cover 
things like assumptions that you need to know about when doing 
inheritance related stuff. So easy access to code is very nice, 
and that also means that the real documentation can be less 
detailed and verbose and easier to comprehend.

"Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:

On Monday, 16 December 2013 at 23:50:26 UTC, Ola Fosheim Grøstad 
wrote:
 You should consider having direct links to html-formatted

Just to clarify: I meant "direct links to each function" not the 
entire source…

"H. S. Teoh" <hsteoh quickfur.ath.cx> writes:

On Tue, Dec 17, 2013 at 12:50:21AM +0100, digitalmars-d-bounces puremagic.com
wrote:
 On Monday, 16 December 2013 at 23:01:36 UTC, Walter Bright wrote:
I hate to say it, but often when I read the Phobos library
documentation I wind up having to check the source code. Yes, I
should follow my own advice and do PRs.

 
 You should consider having direct links to html-formatted source
 code from the documentation. Like this:
 
 http://webapp-improved.appspot.com/api/webapp2_extras/json.html
 
 I find that simple "[source]"-link to be a very helpful solution. It
 is very difficult to make good enough documentation to cover things
 like assumptions that you need to know about when doing inheritance
 related stuff. So easy access to code is very nice, and that also
 means that the real documentation can be less detailed and verbose
 and easier to comprehend.

I agree it's a nifty trick, but I think it's solving the wrong problem.
Documentation should document the *API*, and user code shouldn't depend
on quirks in the current implementation, because it may change later
(bugfixes, optimizations, etc.).


T

-- 
You have to expect the unexpected. -- RL

"Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:

On Tuesday, 17 December 2013 at 00:29:29 UTC, H. S. Teoh wrote:
 Documentation should document the *API*, and user code 
 shouldn't depend
 on quirks in the current implementation, because it may change 
 later
 (bugfixes, optimizations, etc.).

Yes… but when there are quirks that cause your code to not work 
it is much easier to locate the problem if you can easily jump 
around in the library code. I don't use it much for initial 
coding, unless the documentation is missing or if the 
documentation lacks proper examples that show how the different 
part interact or if the documentation is too verbose. I use it 
when I need more insight (like when doing debugging or if I have 
to hook into handlers etc).

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 12/16/13 1:47 PM, Brad Anderson wrote:
 On Monday, 16 December 2013 at 20:38:52 UTC, Andrei Alexandrescu wrote:
 bool between(T, U1, U2)(T v, U1 lo, U2 hi)
 {
     return v >= lo && v <= hi;
 }

 I must say that:

      if (val.between(3, 10))

 sure is a lot easier to understand at a glance than:

      if (val >= 3 && val <= 10)

 Although there is a problem with the word "between" not being clear
 about whether it is inclusive or not.

Prior art: SQL.


Andrei

Timon Gehr <timon.gehr gmx.ch> writes:

On 12/16/2013 09:38 PM, Andrei Alexandrescu wrote:
 bool between(T, U1, U2)(T v, U1 lo, U2 hi)
 {
      return v >= lo && v <= hi;
 }
 ...

There's the issue of different possibilities for inclusive/exclusive end 
points. Maybe we want to add a template parameter taking values from 
["[)","()","(]","[]"]. Even then it is not too clear what the default 
should be. (Probably "[)".)

 uint among(T, Us...)(T v, Us vals)
 {
      foreach (i, U; Us)
      {
          if (v == vals[i]) return i + 1;
      }
      return 0;
 }
 ...

I have my own version of this. I vote add.

Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:

On 16/12/13 22:49, Timon Gehr wrote:
 There's the issue of different possibilities for inclusive/exclusive end
points.
 Maybe we want to add a template parameter taking values from
 ["[)","()","(]","[]"]. Even then it is not too clear what the default should
be.
 (Probably "[)".)

That would be in line with the way that it's handled in other Phobos cases
where 
bounds can be open or closed at either end (e.g. std.random.uniform).

Max Klyga <email domain.com> writes:

On 2013-12-16 20:38:51 +0000, Andrei Alexandrescu said:

 bool between(T, U1, U2)(T v, U1 lo, U2 hi)
 {
      return v >= lo && v <= hi;
 }
 
 uint among(T, Us...)(T v, Us vals)
 {
      foreach (i, U; Us)
      {
          if (v == vals[i]) return i + 1;
      }
      return 0;
 }
 
 Add?
 
 
 Andrei

as Walter mentioned, between should have different versions. Aslo might 
be useful to have a generalized
Range type (not to be confused with iteration ranges). Having used 
Guava range [1] type, I can say it was very useful (especially 
implementing a predicate interface, enabling filtering with a range)

1. https://code.google.com/p/guava-libraries/wiki/RangesExplained

"Chris Cain" <clcain uncg.edu> writes:

On Monday, 16 December 2013 at 20:38:52 UTC, Andrei Alexandrescu 
wrote:
 bool between(T, U1, U2)(T v, U1 lo, U2 hi)
 {
     return v >= lo && v <= hi;
 }

I realize this is, at this point, being retracted. But it would 
open up some interesting ideas. It seems a lot like iota, but it 
could look pretty cool for some purposes. Consider an alternative 
API where you could do things like this:

---
if(x in between(2, 7)) {
    //...
}
---

and

---
// for random number generation...
auto a = uniform(between(30, 100));
---

A slight bit more verbose but more readable, maybe. It also 
shifts the code that checks that it's a valid range (not in the D 
InputRange sense) to between instead.

So code like
https://github.com/D-Programming-Language/phobos/blob/master/std/random.d#L1318
could be taken out and isolated in the "between" code. This could 
have some slight positive performance implications for cases 
where you generate a lot of random numbers in the same range, but 
its main value would probably come improved readability and 
reduced code duplication (but, admittedly, I've not looked around 
enough to know if there are more opportunities to use such a 
between object in phobos...).

Also, kinda going along with what bearophile said, something like 
this might be possible to add to iota. But I'd like to see a 
different name for it since `uniform(iota(30,100))` isn't exactly 
as nice to read.

And I think a default for the range of numbers between represents 
probably should be "[)" but obviously being customizable is 
important too.

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 12/16/13 5:02 PM, Chris Cain wrote:
 On Monday, 16 December 2013 at 20:38:52 UTC, Andrei Alexandrescu wrote:
 bool between(T, U1, U2)(T v, U1 lo, U2 hi)
 {
     return v >= lo && v <= hi;
 }

 I realize this is, at this point, being retracted. But it would open up
 some interesting ideas. It seems a lot like iota, but it could look
 pretty cool for some purposes. Consider an alternative API where you
 could do things like this:

 ---
 if(x in between(2, 7)) {
     //...
 }
 ---

That's problematic. "Between" is a preposition. Naming a function as a 
preposition is fine as long as a verb is implied (e.g. "a in b" really 
means "a _is_ in b", or "a.between(b, c)" really means "a _is_ between b 
and c" etc).

Reifying "between" to the status of object is weird. One constructs a 
"between" object and then what are its primitives? How can one even talk 
about it? "Yeah I have a between here and I copy it to another between"...

"x in between(2, 7)" is cute but just that - it's a lucky strike that 
relies on word ordering in a particular phrase and is unlikely to work 
in many other places.


Andrei

"Chris Cain" <clcain uncg.edu> writes:

On Tuesday, 17 December 2013 at 18:06:27 UTC, Andrei Alexandrescu 
wrote:
 That's problematic. "Between" is a preposition. Naming a 
 function as a preposition is fine as long as a verb is implied 
 (e.g. "a in b" really means "a _is_ in b", or "a.between(b, c)" 
 really means "a _is_ between b and c" etc).

I see... interesting. But this doesn't suggest that the concept 
is bad, just the name.

 "x in between(2, 7)" is cute but just that - it's a lucky 
 strike that relies on word ordering in a particular phrase and 
 is unlikely to work in many other places.

I agree it's cute and just lucky. I'm not attached to the name, 
but I'd like some sort of name that evokes the purpose like that 
does (as an example of something I wouldn't like reading, `x in 
iota(2, 7)` ...)

 Reifying "between" to the status of object is weird. One 
 constructs a "between" object and then what are its primitives? 
 How can one even talk about it? "Yeah I have a between here and 
 I copy it to another between"...

To be honest, I'm just the kind of person to come up with very 
weird ideas, so it's not surprising people might find my idea 
weird. It doesn't necessarily have to be called "between" but 
some sort of object (being able to contain the state is 
important) could contain the concept of a range of values 
("inclusive lowerbound", "exclusive upperbound", support things 
like "opIn" or an opCall to test a value for membership). It'd 
also be needed for it to have a simple way to get the smallest 
acceptable type for the range of values the "between" object 
could represent. So a for a Between!(uint, int) that would be a 
uint, and a Between!(int, uint) that would be a long, and so on. 
Obviously some things _don't_ have acceptable types, such as a 
Between!(long, ulong) (no integral type currently can actually 
hold all of those values).

Something like this, like I showed, could be used to pass to 
other functions like std.random.uniform which request a range to 
generate. Or you should be able to pass it to something like 
std.algorithm.find, std.algorithm.count, etc (predicates that 
take one parameter).

On Tuesday, 17 December 2013 at 01:02:28 UTC, Chris Cain wrote:
 but its main value would probably come improved readability and 
 reduced code duplication

Actually, I thought about this a bit more and its value might be
greater than previously thought... what about the issues people
have with unsigned vs signed comparisons? (consider, someone in 
this very topic corrected your proposed code because of this very 
issue):

---
int a = -1;
uint b = 0;
assert(a < b); // oops, fails.
---

This isn't a new revelation or anything, and the solution, of
course, is to do more complex tests like `assert(a < 0 || a <
b);` but the compiler doing those sorts of things automatically
is questionable. Instead, covering the use-cases with
functions/objects like `between` where template magic can insert
these extra tests automatically might be a viable strategy.

And as another example of something falling prey to this 
"unexpected" behavior, look no further than the example I've 
already given: std.random.uniform ...

---
writeln(uniform(-1, 1u));
// std.random.uniform(): invalid bounding interval [-1, 1)
// Wat?
foreach(_; 0..5) {
     writeln(uniform(-2, uint.max));
     // Oops! Always prints out 4294967294
     // as if the bounding interval was [-2u, -1u)
}
---

https://d.puremagic.com/issues/show_bug.cgi?id=11758


These types of things are apparently very common issues. Having 
an object encapsulating the behavior needed to check this stuff 
and using it is preferable to reimplementing the checks each time 
(and potentially failing each time in subtle ways).

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 12/17/13 1:29 PM, Chris Cain wrote:
 It
 doesn't necessarily have to be called "between" but some sort of object
 (being able to contain the state is important) could contain the concept
 of a range of values ("inclusive lowerbound", "exclusive upperbound",
 support things like "opIn" or an opCall to test a value for membership).

Interval arithmetic (http://en.wikipedia.org/wiki/Interval_arithmetic) 
comes to mind. Like bounds-checked numbers, units, and probabilities, 
it's one of those bread-and-butter types that nobody got around to 
implement for Phobos yet.

In an interval arithmetic approach numbers would compare actually equal, 
i.e. 10 == IntervalInt(5, 100) would be true.


Andrei

"H. S. Teoh" <hsteoh quickfur.ath.cx> writes:

On Tue, Dec 17, 2013 at 01:57:53PM -0800, Andrei Alexandrescu wrote:
 On 12/17/13 1:29 PM, Chris Cain wrote:
It doesn't necessarily have to be called "between" but some sort of
object (being able to contain the state is important) could contain
the concept of a range of values ("inclusive lowerbound", "exclusive
upperbound", support things like "opIn" or an opCall to test a value
for membership).

 
 Interval arithmetic
 (http://en.wikipedia.org/wiki/Interval_arithmetic) comes to mind.
 Like bounds-checked numbers, units, and probabilities, it's one of
 those bread-and-butter types that nobody got around to implement for
 Phobos yet.
 
 In an interval arithmetic approach numbers would compare actually
 equal, i.e. 10 == IntervalInt(5, 100) would be true.

[...]

Ah! "Interval" is the word I was looking for. :)

Ideally, Intervals should implement opApply, 'in', .find, .count, etc.,
and perhaps even interval intersection (but not union since that's not
closed).

I don't like the idea of "IntervalInt"; the base type should be a
template parameter:

	struct Interval(T) { ... }

In my previous post I considered allowing non-homogenous upper/lower
bound types, but in interest of keeping things less messy, it may be
better to just allow only a single type (then you wouldn't need kooky
static-if's around things like opApply, etc.).

Intervals with discrete base types can probably implement the range APIs
for maximum usability with std.algorithm, etc..


T

-- 
Let's eat some disquits while we format the biskettes.

"Chris Cain" <clcain uncg.edu> writes:

On Tuesday, 17 December 2013 at 22:23:47 UTC, H. S. Teoh wrote:
 In my previous post I considered allowing non-homogenous 
 upper/lower
 bound types, but in interest of keeping things less messy, it 
 may be
 better to just allow only a single type (then you wouldn't need 
 kooky
 static-if's around things like opApply, etc.).

I disagree. The fact that it is so messy is precisely why it 
needs to handle it. Doing the messy/hard things in the standard 
library means that users don't have to do it. It's even more 
important since it's so error prone and the "obvious" way to do 
it is strictly wrong.

"Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:

On Tuesday, 17 December 2013 at 21:57:54 UTC, Andrei Alexandrescu 
wrote:
 In an interval arithmetic approach numbers would compare 
 actually equal, i.e. 10 == IntervalInt(5, 100) would be true.


Why is that? I would think that 10 == Interval(10,10), but 
interval(5,100).contains(10) ? True interval arithmetic is 
difficult to implement though, since !(a<b) does not imply (a>=b) 
if I got it right… So you you might have to introduce a 
tri-boolean type to represent uncertainty, or prevent those 
operations, or accept inconsistencies…  Also f(a) should be the 
min/max values of f over the interval a… Tricky to compute, you 
can try numerically…

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 12/17/13 5:58 PM, "Ola Fosheim Grøstad" 
<ola.fosheim.grostad+dlang gmail.com>" wrote:
 On Tuesday, 17 December 2013 at 21:57:54 UTC, Andrei Alexandrescu wrote:
 In an interval arithmetic approach numbers would compare actually
 equal, i.e. 10 == IntervalInt(5, 100) would be true.


 Why is that? I would think that 10 == Interval(10,10), but
 interval(5,100).contains(10) ?

Yah, defining == my way would make it non-transitive.

 True interval arithmetic is difficult to
 implement though, since !(a<b) does not imply (a>=b) if I got it right…

I didn't peruse the wikipedia page in detail but it seems a lot of 
interval arithmetic is well-defined.

 So you you might have to introduce a tri-boolean type

That would be good too for distinct reasons.


Andrei

"Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:

On Wednesday, 18 December 2013 at 02:17:06 UTC, Andrei 
Alexandrescu wrote:
 On 12/17/13 5:58 PM, "Ola Fosheim Grøstad" 
 <ola.fosheim.grostad+dlang gmail.com>" wrote:
 Why is that? I would think that 10 == Interval(10,10), but
 interval(5,100).contains(10) ?

 Yah, defining == my way would make it non-transitive.

 True interval arithmetic is difficult to
 implement though, since !(a<b) does not imply (a>=b) if I got 
 it right…

 I didn't peruse the wikipedia page in detail but it seems a lot 
 of interval arithmetic is well-defined.

But it is counter-intuitive since an interval represent 
uncertainty?

[5,5] == [5,5] => true
[1,5] != [1,5]  => false? // counter-intuitive
[0,5] < [6,10] => true
[0,5] < [2,10] => uncertain

 So you you might have to introduce a tri-boolean type

 That would be good too for distinct reasons.

I wrote libraries for both tribool and fuzzybool for D 7 years 
ago to see how D worked for ADTs. I guess I could rewrite those 
to be more modern and make it available as a starting point. I 
believe I also started on (or planned) to do fuzzy numbers. Fuzzy 
numbers are related to intervals, but have a triangular 
membership function. You use it for representing hazy values like 
"pretty" or "intelligent" (the same person can be both smart and 
stupid at the same time). There are more than one definition, 
each with trade-offs.

e.g.:
fast = FuzzyNumber(40,60,70)
slow = FuzzyNumber(1,10,40)

However, one deficiency in D is (or was) that you cannot make 
comparison operators return non-bool values?

Anyway, I think it might be a good idea to implement Intervals, 
Fuzzynumber, Tribool and Fuzzylogic in a manner that is 
consistent.

"Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:

On Wednesday, 18 December 2013 at 08:58:07 UTC, Ola Fosheim 
Grøstad wrote:
 [1,5] != [1,5]  => false? // counter-intuitive

(a bit unclear there, [1,5]!=[1,5] is uncertain/true, but not 
false which we might first assume)

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 12/18/13 12:58 AM, "Ola Fosheim Grøstad" 
<ola.fosheim.grostad+dlang gmail.com>" wrote:
 On Wednesday, 18 December 2013 at 02:17:06 UTC, Andrei Alexandrescu wrote:
 On 12/17/13 5:58 PM, "Ola Fosheim Grøstad"
 <ola.fosheim.grostad+dlang gmail.com>" wrote:
 Why is that? I would think that 10 == Interval(10,10), but
 interval(5,100).contains(10) ?

 Yah, defining == my way would make it non-transitive.

 True interval arithmetic is difficult to
 implement though, since !(a<b) does not imply (a>=b) if I got it right…

 I didn't peruse the wikipedia page in detail but it seems a lot of
 interval arithmetic is well-defined.

 But it is counter-intuitive since an interval represent uncertainty?

 [5,5] == [5,5] => true
 [1,5] != [1,5]  => false? // counter-intuitive

Within the tolerance allowed, they are equal.

 [0,5] < [6,10] => true
 [0,5] < [2,10] => uncertain

That would be false.

The whole trick is to define primitives such that they have the 
fundamental properties (transitivity, (anti-)symmetry etc).

 So you you might have to introduce a tri-boolean type

 That would be good too for distinct reasons.

 I wrote libraries for both tribool and fuzzybool

There's been a discussion on fast tristate logic recently in here.


Andrei

"Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:

On Wednesday, 18 December 2013 at 17:29:19 UTC, Andrei 
Alexandrescu wrote:
 Within the tolerance allowed, they are equal.

No, "a != a" is only false for singeltons ([3,3] etc)

 [0,5] < [6,10] => true
 [0,5] < [2,10] => uncertain

 That would be false.

Interval-arithmetic is used for approximate calculations with 
upper-lower bounds, so it should not be false because then you 
make the wrong approximation. If the approximation is uncertain 
you need to track that or throw an exception when intervals 
overlap.

 The whole trick is to define primitives such that they have the 
 fundamental properties (transitivity, (anti-)symmetry etc).

The trick is to make the algebra useful for the domain it is used 
in. Some properties we are used to from regular real numbers will 
almost always break, so you have to decide based on usefulness.

Ola.

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 12/18/13 10:02 AM, "Ola Fosheim Grøstad" > The trick is to make the 
algebra useful for the domain it is used in.
 Some properties we are used to from regular real numbers will almost
 always break, so you have to decide based on usefulness.

I don't think so. Algebraic properties have been derived from desirable 
and useful properties and have long shown good returns. Breaking 
algebraic properties based on ad-hoc arguments of usefulness will 
guarantee the type won't work with many standard algorithms (sort etc) 
and will never cease to surprise its users.

Andrei

"Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:

On Wednesday, 18 December 2013 at 19:47:05 UTC, Andrei 
Alexandrescu wrote:
 I don't think so. Algebraic properties have been derived from 
 desirable and useful properties and have long shown good 
 returns.

No, when you change the foundation/definitions some of the 
theorems will break. That always happens. I can't think of a 
single example where that does not happen.

Some theorems are more important to uphold than others, it is a 
good thing to avoid breaking DeMorgans for instance.

 Breaking algebraic properties based on ad-hoc arguments of 
 usefulness will guarantee the type won't work with many 
 standard algorithms (sort etc) and will never cease to surprise 
 its users.

Not sure what you mean by ad-hoc? It is so by definition? You are 
the one arguing for ad hoc… It does not make sense to turn to 
interval-algebra if you want 
range-like-ad-hoc-programmers-semantics? If you implement 
interval-algebra it should be… interval-algebra, and usable a 
such?

Timon Gehr <timon.gehr gmx.ch> writes:

On 12/18/2013 09:06 PM, "Ola Fosheim Grøstad" 
<ola.fosheim.grostad+dlang gmail.com>" wrote:
 On Wednesday, 18 December 2013 at 19:47:05 UTC, Andrei Alexandrescu wrote:
 I don't think so. Algebraic properties have been derived from
 desirable and useful properties and have long shown good returns.

 No, when you change the foundation/definitions some of the theorems will
 break. That always happens. I can't think of a single example where that
 does not happen.

 Some theorems are more important to uphold than others, it is a good
 thing to avoid breaking DeMorgans for instance.
 ...

Giving up Eg. ¬(A ∧ B) → ¬A ∨ ¬B is actually a sensible thing to do in 
constructive logic.

"Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:

On Wednesday, 18 December 2013 at 20:45:44 UTC, Timon Gehr wrote:

 Giving up Eg. ¬(A ∧ B) → ¬A ∨ ¬B is actually a sensible thing 
 to do in constructive logic.

It is common to give it up in fuzzy logic too, doesn't mean it is 
the first thing to throw out.

Anyway, the point in the discussion above is that of having a 
third value "uncertain"/"indeterminate" mapped to false and the 
consequences of that.

You don't want:
a<b == a>b, so ordering overlapping intervals is indeterminate

It is sensible to allow explicit:
bool(indeterminate)==false

If you then have:
[a,b]<[c,d] => indeterminate

And define == by < then it follows that:
[a,b]==[a,b] => indeterminate for a!=b

and:
bool([a,b]==[a,b]) => false

and therefore you would want:
bool([a,b]!=[a,b]) => true

Which is kind of tricky to achieve unless you have two types of 
indeterminate when I come to think of it, maybe you need 
indeterminate and not_indeterminate if you allow casts to bool… 
E.g. !indeterminate=> not_indeterminate and !not_indeterminate => 
indeterminate ?

Hm…

"Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:

On Wednesday, 18 December 2013 at 17:29:19 UTC, Andrei 
Alexandrescu wrote:
 There's been a discussion on fast tristate logic recently in 
 here.

Thanks for the tip. It uses one of the implementations I tested 
too, a LUT in a shift register. However, I think I found the 
regular lookup-table to be faster on x86 (takes one instruction):

e.g. AND:

static ubyte[16] lut = [0,0,0,0, 0,1,2,2, 0,2,2,2, 0,2,2,2];
value = lut[x*4+y]; //turn off boundary checks

"H. S. Teoh" <hsteoh quickfur.ath.cx> writes:

On Tue, Dec 17, 2013 at 10:29:22PM +0100, Chris Cain wrote:
 On Tuesday, 17 December 2013 at 18:06:27 UTC, Andrei Alexandrescu
 wrote:
That's problematic. "Between" is a preposition. Naming a function
as a preposition is fine as long as a verb is implied (e.g. "a in
b" really means "a _is_ in b", or "a.between(b, c)" really means
"a _is_ between b and c" etc).

 
 I see... interesting. But this doesn't suggest that the concept is
 bad, just the name.
 
"x in between(2, 7)" is cute but just that - it's a lucky strike
that relies on word ordering in a particular phrase and is
unlikely to work in many other places.

 
 I agree it's cute and just lucky. I'm not attached to the name, but
 I'd like some sort of name that evokes the purpose like that does
 (as an example of something I wouldn't like reading, `x in iota(2,
 7)` ...)
 
Reifying "between" to the status of object is weird. One
constructs a "between" object and then what are its primitives?
How can one even talk about it? "Yeah I have a between here and I
copy it to another between"...

 
 To be honest, I'm just the kind of person to come up with very weird
 ideas, so it's not surprising people might find my idea weird. It
 doesn't necessarily have to be called "between" but some sort of
 object (being able to contain the state is important) could contain
 the concept of a range of values ("inclusive lowerbound", "exclusive
 upperbound", support things like "opIn" or an opCall to test a value
 for membership).

Ah, I see what you're getting at now. I think this idea has a merit on
its own; I'm just not sure if it is useful as an actual intermediate
data *type*.

But, putting that aside, I think the concept does serve its purpose.
It's a pity that the word 'range' already has an assigned meaning in D,
because otherwise that would be the best name in this case (i.e., range
in the mathematical sense of being a contiguous subset of, say, the
number line). So, for the lack of a better name, let's tentatively call
it "Bounds" (as in, the set of elements bounded by upper and lower
bounds), which may be defined, at least conceptually, as:

	struct Bounds(string shape="[]", T,U)
		if (is(T.init < U.init))
	{
		T lower;
		U upper;

		this(T lowerBound, U upperBound)
		{
			lower = lowerBound;
			upper = upperBound;
		}

		bool opBinaryRight(string op)(V val)
			if (op == "in" &&
				is(T.init < V.init) &&
				is(V.init < U.init))
		{
			static if (shape[0] == '[')
				static if (shape[1] == ']')
					return lower <= val <= upper;
				else static if (shape[1] == ')')
					return lower <= val < upper;
				else static assert(0);
			else static if (shape[0] == '(')
				static if (shape[1] == ']')
					return lower < val <= upper;
				else static if (shape[1] == ')')
					return lower < val < upper;
				else static assert(0);
			else static assert(0);
		}
	}

	// And we might as well throw in a convenience function for
	// constructing these things:
	auto bounds(string shape="[]", T,U)(T lower, U upper)
	{
		return Bounds!(shape,T,U)(lower, upper);
	}

	// So here's how you'd use it:
	unittest
	{
		int x = 123;
		assert(x in bounds(122, 124));

		// Mixed types are possible
		ulong y = ulong.max;
		float z = -z.max;
		assert(100 in bounds(y, z));
	}

	// If we want maximum efficiency, and the bounds are statically
	// known, we could also introduce a compile-time variant of
	// Bounds:
	struct CtBounds(T lower, U upper, string shape="[]", T, U)
		if (is(t < u))
	{
		// This struct cannot be instantiated at runtime.
		 disabled this();

		bool opBinaryRight(string op, V)(V val) if (op == "in")
		{
			... // same as above, except that now .lower and
			    // .upper are known at compile-time.
		}
	}

	unittest
	{
		// Now we can check bounds at compile time.
		static assert(1 in CtBounds!(0.0f, 2u));
	}

Of course, we can add opApply to these structs, then you'd be able to
write:

	foreach (x; bounds(0, 100)) { ... }


 It'd also be needed for it to have a simple way to get the smallest
 acceptable type for the range of values the "between" object could
 represent. So a for a Between!(uint, int) that would be a uint, and a
 Between!(int, uint) that would be a long, and so on. Obviously some
 things _don't_ have acceptable types, such as a Between!(long, ulong)
 (no integral type currently can actually hold all of those values).

There's nothing wrong with Bounds!(long,ulong); it just won't have an
opApply method, that's all. :) It can be conveniently static-if'd out in
that case. It can still represent number ranges beyond the current range
of built-in types, like [long.min, ulong.max], and you can test for
membership with various types. This allows you to test variables of
different types, like ints and uints, so the ability to represent such a
range is still useful.


 Something like this, like I showed, could be used to pass to other
 functions like std.random.uniform which request a range to generate.
 Or you should be able to pass it to something like std.algorithm.find,
 std.algorithm.count, etc (predicates that take one parameter).

While you *could* implement the input range API for the Bounds struct
for this purpose, it's probably better to define special overloads for
find and count, since you really don't want to waste time iterating over
elements instead of just directly computing the narrowed Bounds struct
or subtracting the lower bound from the upper, respectively. For
example:

	auto find(T, U, V)(Bounds!(T,U) bounds, V val)
	{
		if (val in bounds)
			return Bounds!(T,U)(val, bounds.upper);
		else
			return Bounds!(T,U)(0, -1); // empty bounds
	}

	size_t count(T, U)(Bounds!(T,U) bounds)
	{
		return bounds.upper - bounds.lower;
	}

I.e., O(1) complexity instead of O(upper-lower).


T

-- 
Question authority. Don't ask why, just do it.

"Chris Cain" <clcain uncg.edu> writes:

On Tuesday, 17 December 2013 at 22:14:41 UTC, H. S. Teoh wrote:
 Ah, I see what you're getting at now. I think this idea has a 
 merit on
 its own; I'm just not sure if it is useful as an actual 
 intermediate
 data *type*.

The use over a function would be

1. Contain all of the complexity that working with intervals on 
(in this case) integers. It's been shown enough times that the 
straight-forward way of dealing with this is error-prone.
2. Maintain performance characteristics as much as possible. 
Without an object, a function doing this sort of thing would have 
to revalidate the bounds each time or, worse, NOT validate the 
bounds at all (with in contracts, we can validate each time 
because release code will take the contracts out, but it's still 
potentially an issue). With an object we can cache any type of 
validations and/or assertions needed and, potentially, improve 
performance in some cases.
3. Allow for existing functions to specialize when an interval is 
given, when appropriate.

 But, putting that aside, I think the concept does serve its 
 purpose.
 It's a pity that the word 'range' already has an assigned 
 meaning in D,
 because otherwise that would be the best name in this case 
 (i.e., range
 in the mathematical sense of being a contiguous subset of, say, 
 the
 number line). So, for the lack of a better name, let's 
 tentatively call
 it "Bounds" (as in, the set of elements bounded by upper and 
 lower
 bounds), which may be defined, at least conceptually, as:

Just to step up your idea to something a bit closer to complete 
(still have not thrown it into a compiler or anything yet):
http://www.dpaste.dzfl.pl/19c80ff9

(And I really like the idea of a CtInterval, but haven't done 
anything with it so I've excluded it in the above paste)

 It'd also be needed for it to have a simple way to get the 
 smallest
 acceptable type for the range of values the "between" object 
 could
 represent. So a for a Between!(uint, int) that would be a 
 uint, and a
 Between!(int, uint) that would be a long, and so on. Obviously 
 some
 things _don't_ have acceptable types, such as a Between!(long, 
 ulong)
 (no integral type currently can actually hold all of those 
 values).

 There's nothing wrong with Bounds!(long,ulong); it just won't 
 have an
 opApply method, that's all. :) It can be conveniently 
 static-if'd out in
 that case. It can still represent number ranges beyond the 
 current range
 of built-in types, like [long.min, ulong.max], and you can test 
 for
 membership with various types. This allows you to test 
 variables of
 different types, like ints and uints, so the ability to 
 represent such a
 range is still useful.

Well, I'm not suggesting that the interval not be allowed... but 
for things that use that interval, they may produce some sort of 
output. If they're using the interval to output, then they'll 
need to know what data type the output needs to be. It'd be 
convenient if some standard function existed to accomplish that 
task in a standard way.

The example I'm using for this is if std.random.uniform took in 
an interval, what would its output be? Obviously, it couldn't 
output something in [long.min, ulong.max], but it's possible it 
could spit out an answer in [byte.min, ubyte.max] since a short 
could contain all of those values.

 Something like this, like I showed, could be used to pass to 
 other
 functions like std.random.uniform which request a range to 
 generate.
 Or you should be able to pass it to something like 
 std.algorithm.find,
 std.algorithm.count, etc (predicates that take one parameter).

 While you *could* implement the input range API for the Bounds 
 struct
 for this purpose, it's probably better to define special 
 overloads for
 find and count, since you really don't want to waste time 
 iterating over
 elements instead of just directly computing the narrowed Bounds 
 struct
 or subtracting the lower bound from the upper, respectively. For
 example:

Sorry, confusion based on using the word "range" again. When I 
said range, I meant bounds/interval in this case. Functions that 
request some sort of interval or bounds should use interval 
instead of trying to do anything on its own (since the "do your 
own thing" is increasingly being found to be errorprone).

So, something like this should work:

     unittest
     {
         import std.algorithm;
         assert(
             find!"a in b"([5, 6, 2, 9], interval(1, 4))
                 == [2, 9]);
         // uses std.algorithm.find

         assert(
             count!"a in b"([5, 6, 1, 3, 9, 7, 2], interval(1,3))
                 == 3);
         // uses std.algorithm.count

         import std.random;
         foreach(_; 0..10000)
             assert(uniform(interval(1,5)) in interval(1,5));
         // Nice assertion, right?
     }

It might also be useful in some circumstances to be able to know 
how many values are in the interval (sort of like a "length" or 
"size") but if you have an interval of [long.min, ulong.max] ... 
well, you know the problem.

Considering what Andrei said, we might could expand this concept 
to support the interval arithmetic. We'd also need to be able to 
support intervals like (-oo, oo), (-oo, x], [x, oo) ... where the 
membership test returns true, <=x, and >=x respectively (while 
taking care of the issues that exist with signed/unsigned 
comparisons, obviously). That said, not all functions will want 
to handle those types of intervals (std.random.uniform, for 
instance).

"Chris Cain" <clcain uncg.edu> writes:

On Wednesday, 18 December 2013 at 01:27:37 UTC, Chris Cain wrote:
 Just to step up your idea to something a bit closer to complete 
 (still have not thrown it into a compiler or anything yet):
 http://www.dpaste.dzfl.pl/19c80ff9

Thinking about this a bit more, it might also be really cool if 
the way to make an Interval was using an IntervalBuilder or 
something of the like (as opposed to the current constructor that 
takes a "shape" template parameter). Then it'd be natural to have 
intervals without certain bounds being constructed (you'd just 
not specify the lowerbound while building it).

Of course, then it'd be almost completely unique in phobos since 
nothing else uses the builder pattern. That may or may not be an 
issue.

"Vladimir Panteleev" <vladimir thecybershadow.net> writes:

On Monday, 16 December 2013 at 20:38:52 UTC, Andrei Alexandrescu 
wrote:
 bool between(T, U1, U2)(T v, U1 lo, U2 hi)
 {
     return v >= lo && v <= hi;
 }

Careful:

assert(between(0u, -1, 1)); // fails

Assuming no overflows, a faster implementation would be:

return v-lo <= hi-lo;

Jerry <jlquinn optonline.net> writes:

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

 bool between(T, U1, U2)(T v, U1 lo, U2 hi)
 {
     return v >= lo && v <= hi;
 }

+1

 uint among(T, Us...)(T v, Us vals)
 {
     foreach (i, U; Us)
     {
         if (v == vals[i]) return i + 1;
     }
     return 0;
 }

This seems less useful to me.  What was the example where you found it
useful?

Jerry

Jerry <jlquinn optonline.net> writes:

Jerry <jlquinn optonline.net> writes:

 Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

 uint among(T, Us...)(T v, Us vals)
 {
     foreach (i, U; Us)
     {
         if (v == vals[i]) return i + 1;
     }
     return 0;
 }

 This seems less useful to me.  What was the example where you found it
 useful?

Being bad and following myself up...

I think this proposal is highlighting that Phobos more generally lacks
set operations.  It seems to me that among() is roughly equivalent to:

auto i = v in vals;

but this is only currently used for builtin hash tables.  Since this
syntax already exists, does it make sense to see if it can be done as
something like:

auto i = v in (val, val, val ...);

?

I've been playing with porting some code where we use hash tables and
sets quite a bit and end up creating a lot of bool[string] objects.  It
works, but I do wish there was a more explicit set.  This allows for
blah["entry"] = false, which isn't really what I'm trying to model :-)

Would it make sense to create a Set object in std.container?  

Jerry

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 12/17/13 9:06 AM, Jerry wrote:
 Would it make sense to create a Set object in std.container?

Yes.

Andrei

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 12/17/13 7:59 AM, Jerry wrote:
 Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

 bool between(T, U1, U2)(T v, U1 lo, U2 hi)
 {
      return v >= lo && v <= hi;
 }

 +1

 uint among(T, Us...)(T v, Us vals)
 {
      foreach (i, U; Us)
      {
          if (v == vals[i]) return i + 1;
      }
      return 0;
 }

 This seems less useful to me.  What was the example where you found it
 useful?

 Jerry

I gave a long litany of examples taken from real code in a subsequent 
post. In fact I couldn't find motivating examples for "between", or even 
significant evidence that it would be dramatically useful; I'd included 
it only for completion, and I have since retracted it.

Andrei

"Byron" <byron.heads gmail.com> writes:

On Monday, 16 December 2013 at 20:38:52 UTC, Andrei Alexandrescu 
wrote:
 bool between(T, U1, U2)(T v, U1 lo, U2 hi)
 {
     return v >= lo && v <= hi;
 }

 uint among(T, Us...)(T v, Us vals)
 {
     foreach (i, U; Us)
     {
         if (v == vals[i]) return i + 1;
     }
     return 0;
 }

 Add?


 Andrei


I don't know why we can do this instead:

if(foo in ["alpha", "beta", "delta"] ) {

}

basically have an opIn operator  x in y -> y.opIn(x)
U* opIn(T, U)(T key)
can define in runtime for arrays, and allow custom ones to be 
defines

and

if(1 < x <= 10) {

}

I remember this being shot down before...




Both of these are easier to read, and are more natural.  They 
also cover more cases.

Andrej Mitrovic <andrej.mitrovich gmail.com> writes:

On 12/17/13, Byron <byron.heads gmail.com> wrote:
 I don't know why we can't do this instead:

 if (foo in ["alpha", "beta", "delta"] ) {

You can come pretty close with:

if (foo in A["alpha", "beta", "delta"] )

Here's the code:

http://forum.dlang.org/thread/mailman.111.1325867961.16222.digitalmars-d puremagic.com#post-mailman.111.1325867961.16222.digitalmars-d:40puremagic.com

"Byron" <byron.heads gmail.com> writes:

On Tuesday, 17 December 2013 at 17:17:39 UTC, Andrej Mitrovic 
wrote:
 On 12/17/13, Byron <byron.heads gmail.com> wrote:
 I don't know why we can't do this instead:

 if (foo in ["alpha", "beta", "delta"] ) {

 You can come pretty close with:

 if (foo in A["alpha", "beta", "delta"] )

 Here's the code:

 http://forum.dlang.org/thread/mailman.111.1325867961.16222.digitalmars-d puremagic.com#post-mailman.111.1325867961.16222.digitalmars-d:40puremagic.com

Wow that is a lot of hoops to jump through to simulate a fairly 
simple operator.  Probably not something anyone new to D is going 
to do.
the in operator needs some real love.  I would think you could do 
even more with in

if("ello" in "Hello World") { // I would think that this could 
return a slice

}

LinkedList!int list = makeList();
enforce(45 in list, "oh no we must have 45 in the linked list or 
all is lost");

!in would be nice, not sure how it could work if in returns 
pointers/refs/slices

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 12/17/13 9:17 AM, Andrej Mitrovic wrote:
 On 12/17/13, Byron <byron.heads gmail.com> wrote:
 I don't know why we can't do this instead:

 if (foo in ["alpha", "beta", "delta"] ) {

 You can come pretty close with:

 if (foo in A["alpha", "beta", "delta"] )

Wouldn't

if (foo in LiteralSet("alpha", "beta", "delta"))

be a ton faster?


Andrei

Dmitry Olshansky <dmitry.olsh gmail.com> writes:

17-Dec-2013 22:16, Andrei Alexandrescu пишет:
 On 12/17/13 9:17 AM, Andrej Mitrovic wrote:
 On 12/17/13, Byron <byron.heads gmail.com> wrote:
 I don't know why we can't do this instead:

 if (foo in ["alpha", "beta", "delta"] ) {

 You can come pretty close with:

 if (foo in A["alpha", "beta", "delta"] )

 Wouldn't

 if (foo in LiteralSet("alpha", "beta", "delta"))

 be a ton faster?

Or even:
if (foo in LiteralSet!("alpha", "beta", "delta"))

 Andrei


-- 
Dmitry Olshansky

"Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:

On Tuesday, 17 December 2013 at 18:16:59 UTC, Andrei Alexandrescu 
wrote:

 if (foo in LiteralSet("alpha", "beta", "delta"))

if "_" referred to anything undefined then you could do:

if (foo in ["alpha":_,"beta":_,"delta":_])

Side-note: LLVM actually uses a value "undef" that it uses for 
reasoning, so that

(x & undef) == 0
(x | undef) == -1

Kind of cute.

Or even better:

if (foo in ["alpha":-),"beta":-),"delta":-)])

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 12/17/13 8:43 AM, Byron wrote:
 I don't know why we can do this instead:

 if(foo in ["alpha", "beta", "delta"] ) {

 }

It's a good idea.

 basically have an opIn operator  x in y -> y.opIn(x)
 U* opIn(T, U)(T key)
 can define in runtime for arrays, and allow custom ones to be defines

No, that should only work for literal arrays.

 and

 if(1 < x <= 10) {

 }

 I remember this being shot down before...

"Don't change semantics of C code".

 Both of these are easier to read, and are more natural.  They also cover
 more cases.

No - "among" could take a custom predicate.


Andrei

"Byron" <byron.heads gmail.com> writes:

On Tuesday, 17 December 2013 at 18:15:29 UTC, Andrei Alexandrescu 
wrote:
 On 12/17/13 8:43 AM, Byron wrote:
 I don't know why we can do this instead:

 if(foo in ["alpha", "beta", "delta"] ) {

 }

 It's a good idea.

 basically have an opIn operator  x in y -> y.opIn(x)
 U* opIn(T, U)(T key)
 can define in runtime for arrays, and allow custom ones to be 
 defines

 No, that should only work for literal arrays.

Any major reason why? Right now in reminds of + operator in java, 
only language devs can decide how its used.

 and

 if(1 < x <= 10) {

 }

 I remember this being shot down before...

 "Don't change semantics of C code".

How does this change semantics of C code anymore then in, is, ~ 
does? Its okay if this has been beaten to death and you don't 
want to comment more on it.

 Both of these are easier to read, and are more natural.  They 
 also cover
 more cases.

 No - "among" could take a custom predicate.

Is that not just a special case of reduce/filter/find then?

 Andrei

Lionello Lunesu <lionello lunesu.remove.com> writes:

On 12/17/13, 4:38, Andrei Alexandrescu wrote:
 bool between(T, U1, U2)(T v, U1 lo, U2 hi)
 {
      return v >= lo && v <= hi;
 }

The expression a<b<c is not ambiguous in D. We could make it do what 
people expect.


 uint among(T, Us...)(T v, Us vals)
 {
      foreach (i, U; Us)
      {
          if (v == vals[i]) return i + 1;
      }
      return 0;
 }

"in"?

assert("a" in ["a":1, "b":1]);

Again, with little compiler magic we could allow that to be written as

assert("a" in ["a", "b"]);

Note that I'm not advocating for O(n) "in" for regular arrays, but 
merely for the compiler to recognize the "in []" pattern and Do The 
Right Thing.

L.

Lionello Lunesu <lionello lunesu.remove.com> writes:

Finally able to update the posts from the newsserver and saw both got 
mentioned before.

I agree with the "Don't change semantics of C code", so that rules out 
a<b<c.

L.

"Jakob Ovrum" <jakobovrum gmail.com> writes:

On Monday, 16 December 2013 at 20:38:52 UTC, Andrei Alexandrescu 
wrote:
 Add?

I've posted a PR[1] for an implementation of `among` that 
attempts to incorporate all the suggestions from this thread.

[1] https://github.com/D-Programming-Language/phobos/pull/1787

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 12/16/13 12:38 PM, Andrei Alexandrescu wrote:
 bool between(T, U1, U2)(T v, U1 lo, U2 hi)
 {
      return v >= lo && v <= hi;
 }

 uint among(T, Us...)(T v, Us vals)
 {
      foreach (i, U; Us)
      {
          if (v == vals[i]) return i + 1;
      }
      return 0;
 }

 Add?

Looks like among() has proven its worth since we introduced it. Now I 
somehow forgot between() didn't make it, and reviewed some code at work 
assuming it exists! Here's the original and proposed in a couple of 
snippets:

return (path.asPath.logicalLength() <= asPathLengths_[1] &&
             path.asPath.logicalLength() >= asPathLengths_[0]);

=>

return path.asPath.logicalLength.between(asPathLengths_[0], 
asPathLengths_[1]);

====

if (prefix.prefixLen > prefixLenRange_[1] ||
         prefix.prefixLen < prefixLenRange_[0]) {

=>

if (!prefix.prefixLen.between(prefixLenRange_[0], prefixLenRange_[1])) {

====

Well?


Andrei

"Jesse Phillips" <Jesse.K.Phillips+D gmail.com> writes:

On Sunday, 15 March 2015 at 01:48:53 UTC, Andrei Alexandrescu 
wrote:
 On 12/16/13 12:38 PM, Andrei Alexandrescu wrote:
 bool between(T, U1, U2)(T v, U1 lo, U2 hi)
 {
     return v >= lo && v <= hi;
 }

 uint among(T, Us...)(T v, Us vals)
 {
     foreach (i, U; Us)
     {
         if (v == vals[i]) return i + 1;
     }
     return 0;
 }

 Add?

 Looks like among() has proven its worth since we introduced it. 
 Now I somehow forgot between() didn't make it, and reviewed 
 some code at work assuming it exists! Here's the original and 
 proposed in a couple of snippets:

 return (path.asPath.logicalLength() <= asPathLengths_[1] &&
             path.asPath.logicalLength() >= asPathLengths_[0]);

 =>

 return path.asPath.logicalLength.between(asPathLengths_[0], 
 asPathLengths_[1]);

 ====

 if (prefix.prefixLen > prefixLenRange_[1] ||
         prefix.prefixLen < prefixLenRange_[0]) {

 =>

 if (!prefix.prefixLen.between(prefixLenRange_[0], 
 prefixLenRange_[1])) {

 ====

 Well?


 Andrei

I think it would be a good addition. Would we want to allow 
specifying the inclusion like below:

     auto between(string inclusion = "[]")(int v, int a, int b) {
         static if(inclusion == "(]")
             return (v <= b && v > a);
         else static if(inclusion == "[)")
             return (v < b && v >= a);
         else static if(inclusion == "()")
             return (v < b && v > a);
         else static if(inclusion == "[]")
             return (v <= b && v >= a);
         else
             static assert(false, "unknown inclusion parameter");
     } unittest {
         static assert(4.between(3,5));
         static assert(4.between(4,5));
         static assert(4.between(3,4));

         static assert(!4.between!"(]"(4,5));
         static assert(!4.between!"[)"(3,4));
     }

"Tobias Pankrath" <tobias pankrath.net> writes:

 I think it would be a good addition. Would we want to allow 
 specifying the inclusion like below:

     auto between(string inclusion = "[]")(int v, int a, int b) {

+1

"Vladimir Panteleev" <vladimir thecybershadow.net> writes:

On Sunday, 15 March 2015 at 01:48:53 UTC, Andrei Alexandrescu 
wrote:
 On 12/16/13 12:38 PM, Andrei Alexandrescu wrote:
 bool between(T, U1, U2)(T v, U1 lo, U2 hi)
 {
     return v >= lo && v <= hi;
 }

 Add?

 Looks like among() has proven its worth since we introduced it. 
 Now I somehow forgot between() didn't make it, and reviewed 
 some code at work assuming it exists!

I don't know if it's been mentioned yet, but there exists an 
optimization for between with integer arguments:

bool between(T, U1, U2)(T v, U1 lo, U2 hi)
	if (is(T:long) && is(U1:long) && is(U2:long))
{
     return cast(Unsigned!T )v  - cast(Unsigned!U1)lo
         <= cast(Unsigned!U2)hi - cast(Unsigned!U1)lo;
}

For this reason, I think this makes "between" non-trivial, so it 
is worth adding.

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 3/26/15 11:41 AM, Vladimir Panteleev wrote:
 On Sunday, 15 March 2015 at 01:48:53 UTC, Andrei Alexandrescu wrote:
 On 12/16/13 12:38 PM, Andrei Alexandrescu wrote:
 bool between(T, U1, U2)(T v, U1 lo, U2 hi)
 {
     return v >= lo && v <= hi;
 }

 Add?

 Looks like among() has proven its worth since we introduced it. Now I
 somehow forgot between() didn't make it, and reviewed some code at
 work assuming it exists!

 I don't know if it's been mentioned yet, but there exists an
 optimization for between with integer arguments:

 bool between(T, U1, U2)(T v, U1 lo, U2 hi)
      if (is(T:long) && is(U1:long) && is(U2:long))
 {
      return cast(Unsigned!T )v  - cast(Unsigned!U1)lo
          <= cast(Unsigned!U2)hi - cast(Unsigned!U1)lo;
 }

 For this reason, I think this makes "between" non-trivial, so it is
 worth adding.

Hmmm... so we have two subtractions and one comparisons vs. two 
comparisons and a jump in between. I think you're right! -- Andrei

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 3/26/15 11:41 AM, Vladimir Panteleev wrote:
 On Sunday, 15 March 2015 at 01:48:53 UTC, Andrei Alexandrescu wrote:
 On 12/16/13 12:38 PM, Andrei Alexandrescu wrote:
 bool between(T, U1, U2)(T v, U1 lo, U2 hi)
 {
     return v >= lo && v <= hi;
 }

 Add?

 Looks like among() has proven its worth since we introduced it. Now I
 somehow forgot between() didn't make it, and reviewed some code at
 work assuming it exists!

 I don't know if it's been mentioned yet, but there exists an
 optimization for between with integer arguments:

 bool between(T, U1, U2)(T v, U1 lo, U2 hi)
      if (is(T:long) && is(U1:long) && is(U2:long))
 {
      return cast(Unsigned!T )v  - cast(Unsigned!U1)lo
          <= cast(Unsigned!U2)hi - cast(Unsigned!U1)lo;
 }

 For this reason, I think this makes "between" non-trivial, so it is
 worth adding.

Wait, that doesn't work. 5.between(4, 3) returns true, should return 
false. -- Andrei

"Vladimir Panteleev" <vladimir thecybershadow.net> writes:

On Thursday, 26 March 2015 at 21:09:16 UTC, Andrei Alexandrescu 
wrote:
 On 3/26/15 11:41 AM, Vladimir Panteleev wrote:
 I don't know if it's been mentioned yet, but there exists an
 optimization for between with integer arguments:

 bool between(T, U1, U2)(T v, U1 lo, U2 hi)
     if (is(T:long) && is(U1:long) && is(U2:long))
 {
     return cast(Unsigned!T )v  - cast(Unsigned!U1)lo
         <= cast(Unsigned!U2)hi - cast(Unsigned!U1)lo;
 }

 For this reason, I think this makes "between" non-trivial, so 
 it is
 worth adding.

 Wait, that doesn't work. 5.between(4, 3) returns true, should 
 return false. -- Andrei

Oh yeah, this assumes hi <= lo. I thought this was part of the 
function contract.

"Vladimir Panteleev" <vladimir thecybershadow.net> writes:

On Thursday, 26 March 2015 at 21:51:54 UTC, Vladimir Panteleev
wrote:
 Oh yeah, this assumes hi <= lo. I thought this was part of the 
 function contract.

I meant lo <= hi

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 3/26/15 2:52 PM, Vladimir Panteleev wrote:
 On Thursday, 26 March 2015 at 21:51:54 UTC, Vladimir Panteleev
 wrote:
 Oh yeah, this assumes hi <= lo. I thought this was part of the
 function contract.

 I meant lo <= hi

New idea:

bool ordered(pred = "a < b")(T...)(T values)
{
     foreach (i, _; T[1 .. $])
     {
         if (binaryFun!pred(values[i], values[i - 1]) return false;
     }
     return true;
}

Instead of x.between(a, b) one would write ordered(a, x, b).

Cons: can't use the UFCS nicely. Doesn't generalize to all combinations 
of < and <=.

Pros: Consistent with isSorted so easy to grasp. Does generalize to 
testing multiple values.

Destroy!


Andrei

"H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:

On Thu, Mar 26, 2015 at 03:23:12PM -0700, Andrei Alexandrescu via Digitalmars-d
wrote:
 On 3/26/15 2:52 PM, Vladimir Panteleev wrote:
On Thursday, 26 March 2015 at 21:51:54 UTC, Vladimir Panteleev
wrote:
Oh yeah, this assumes hi <= lo. I thought this was part of the
function contract.

I meant lo <= hi

 
 New idea:
 
 bool ordered(pred = "a < b")(T...)(T values)
 {
     foreach (i, _; T[1 .. $])
     {
         if (binaryFun!pred(values[i], values[i - 1]) return false;
     }
     return true;
 }
 
 Instead of x.between(a, b) one would write ordered(a, x, b).
 
 Cons: can't use the UFCS nicely. Doesn't generalize to all
 combinations of < and <=.
 
 Pros: Consistent with isSorted so easy to grasp. Does generalize to
 testing multiple values.
 
 Destroy!

[...]

Neat idea! This would let us translate mathematical statements of the
form "1 < x < 2 < y < 3" to ordered(1, x, 2, y, 3), and various other
combinations.

Don't like the name, though. Prefer 'isOrdered', otherwise it sounds
like some kind of sorting algorithm (as in, returns an ordered sequence
of its arguments).

As for combinations of < and <=, what about taking multiple template
arguments? E.g.:

	if (isOrdered!("<", "<=")(0, x, 10)) { ... }


T

-- 
If it tastes good, it's probably bad for you.

"Jakob Ovrum" <jakobovrum gmail.com> writes:

On Thursday, 26 March 2015 at 22:30:54 UTC, H. S. Teoh wrote:
 As for combinations of < and <=, what about taking multiple 
 template
 arguments? E.g.:

 	if (isOrdered!("<", "<=")(0, x, 10)) { ... }

In that case, wouldn't it be more readable to just do:

     if (0 < x <= 10) { ... }

?

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 3/26/15 3:28 PM, H. S. Teoh via Digitalmars-d wrote:
 Don't like the name, though. Prefer 'isOrdered', otherwise it sounds
 like some kind of sorting algorithm (as in, returns an ordered sequence
 of its arguments).

Must be single-word name or nothing per Andrei's Hierarchy Of Naming 
Abstractions (AHONA). From low-level to high-level abstractions:

* If a realization is too simple and frequent, no abstraction should 
replace it.

* If a realization has high frequency but low complexity, it can only be 
replaced by an abstraction that is one simple word with no change of 
case. E.g. "among" is okay, "isAmong" is not.

* If a realization has high frequency and high complexity, it may be 
replaced by an abstraction with a multi-word name, little or no nesting, 
and few or no type parameters.

* If a realization has low frequency and high complexity, it may be 
replaced by an abstraction with a multi-word name, nesting, and type 
parameters.


Andrei

"H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:

On Thu, Mar 26, 2015 at 03:48:26PM -0700, Andrei Alexandrescu via Digitalmars-d
wrote:
 On 3/26/15 3:28 PM, H. S. Teoh via Digitalmars-d wrote:
Don't like the name, though. Prefer 'isOrdered', otherwise it sounds
like some kind of sorting algorithm (as in, returns an ordered
sequence of its arguments).

 
 Must be single-word name or nothing per Andrei's Hierarchy Of Naming
 Abstractions (AHONA). From low-level to high-level abstractions:
 
 * If a realization is too simple and frequent, no abstraction should
 replace it.
 
 * If a realization has high frequency but low complexity, it can only
 be replaced by an abstraction that is one simple word with no change
 of case.  E.g. "among" is okay, "isAmong" is not.
 
 * If a realization has high frequency and high complexity, it may be
 replaced by an abstraction with a multi-word name, little or no
 nesting, and few or no type parameters.
 
 * If a realization has low frequency and high complexity, it may be
 replaced by an abstraction with a multi-word name, nesting, and type
 parameters.

[...]

If the bar is this high, then I vote against adding this function.

Writing `if (0 <= x && x < 10)` is far easier and has a clear meaning,
whereas hiding it behind a poorly-named one-word abstraction actually
hurts readability and therefore maintainability. IMO this falls under
the first rule you listed above.


T

-- 
There are 10 kinds of people in the world: those who can count in binary, and
those who can't.

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 3/26/15 4:03 PM, H. S. Teoh via Digitalmars-d wrote:
 On Thu, Mar 26, 2015 at 03:48:26PM -0700, Andrei Alexandrescu via
Digitalmars-d wrote:
 On 3/26/15 3:28 PM, H. S. Teoh via Digitalmars-d wrote:
 Don't like the name, though. Prefer 'isOrdered', otherwise it sounds
 like some kind of sorting algorithm (as in, returns an ordered
 sequence of its arguments).

 Must be single-word name or nothing per Andrei's Hierarchy Of Naming
 Abstractions (AHONA). From low-level to high-level abstractions:

 * If a realization is too simple and frequent, no abstraction should
 replace it.

 * If a realization has high frequency but low complexity, it can only
 be replaced by an abstraction that is one simple word with no change
 of case.  E.g. "among" is okay, "isAmong" is not.

 * If a realization has high frequency and high complexity, it may be
 replaced by an abstraction with a multi-word name, little or no
 nesting, and few or no type parameters.

 * If a realization has low frequency and high complexity, it may be
 replaced by an abstraction with a multi-word name, nesting, and type
 parameters.

 [...]

 If the bar is this high, then I vote against adding this function.

 Writing `if (0 <= x && x < 10)` is far easier and has a clear meaning,
 whereas hiding it behind a poorly-named one-word abstraction actually
 hurts readability and therefore maintainability. IMO this falls under
 the first rule you listed above.

https://github.com/D-Programming-Language/phobos/pull/3112 -- Andrei

"Vladimir Panteleev" <vladimir thecybershadow.net> writes:

On Thursday, 26 March 2015 at 22:23:12 UTC, Andrei Alexandrescu 
wrote:
 New idea:

 bool ordered(pred = "a < b")(T...)(T values)

So... isSorted for tuples?

"H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:

On Fri, Mar 27, 2015 at 01:37:45AM +0000, Vladimir Panteleev via Digitalmars-d
wrote:
 On Thursday, 26 March 2015 at 22:23:12 UTC, Andrei Alexandrescu wrote:
New idea:

bool ordered(pred = "a < b")(T...)(T values)

 
 So... isSorted for tuples?

That's pretty much what it is, and I'm wondering why use a completely
different name rather than overload isSorted.


T

-- 
Не дорог подарок, дорога любовь.

"John Colvin" <john.loughran.colvin gmail.com> writes:

On Friday, 27 March 2015 at 01:53:22 UTC, H. S. Teoh wrote:
 On Fri, Mar 27, 2015 at 01:37:45AM +0000, Vladimir Panteleev 
 via Digitalmars-d wrote:
 On Thursday, 26 March 2015 at 22:23:12 UTC, Andrei 
 Alexandrescu wrote:
New idea:

bool ordered(pred = "a < b")(T...)(T values)

 
 So... isSorted for tuples?

 That's pretty much what it is, and I'm wondering why use a 
 completely
 different name rather than overload isSorted.


 T

import std.typecons : ∑ = tuple;

∑(a, x, b).isSorted;

Or maybe not, haha! It's kinda tempting for personal projects, as 
∑ is just alt-w on my macbook...