www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - between and among: worth Phobosization?

reply 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
Dec 16 2013
next sibling parent reply "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
Dec 16 2013
parent "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.
Dec 16 2013
prev sibling next sibling parent reply 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.
Dec 16 2013
next sibling parent reply 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).
Dec 16 2013
parent 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.
Dec 16 2013
prev sibling next sibling parent reply 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; } ... if (v[i .. $].atSequence(tk!"#", tk!"if") || (v[i .. $].atSequence(tk!"#", tk!"identifier") && v[i + 1].value_.among("ifndef", "ifdef"))) { ++openIf; } else if (v[i .. $].atSequence(tk!"#", tk!"identifier") && 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
Dec 16 2013
parent reply 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?
Dec 16 2013
parent reply 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
Dec 16 2013
parent reply 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
Dec 17 2013
next sibling parent reply =?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
Dec 17 2013
parent 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
Dec 17 2013
prev sibling next sibling parent "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);
Dec 17 2013
prev sibling parent 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
Dec 17 2013
prev sibling next sibling parent reply "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
Dec 16 2013
parent reply 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
Dec 17 2013
parent reply 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
Dec 17 2013
parent 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? :-)
Dec 17 2013
prev sibling parent reply "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)
Dec 16 2013
parent reply 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
Dec 16 2013
next sibling parent reply "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*
Dec 16 2013
parent reply 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.
Dec 16 2013
parent "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?)
Dec 17 2013
prev sibling parent 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
Dec 17 2013
prev sibling next sibling parent reply "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.
Dec 16 2013
next sibling parent "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.
Dec 16 2013
prev sibling next sibling parent 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.)
Dec 16 2013
prev sibling next sibling parent reply 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.
Dec 16 2013
parent reply "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.
Dec 16 2013
next sibling parent reply 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
Dec 16 2013
next sibling parent reply 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().
Dec 16 2013
parent reply 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
Dec 16 2013
parent "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
Dec 16 2013
prev sibling parent reply "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.
Dec 16 2013
next sibling parent 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!
Dec 16 2013
prev sibling parent reply "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?
Dec 17 2013
next sibling parent =?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
Dec 17 2013
prev sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Dec 17, 2013 at 04:58:10PM +0100, Simen Kjrs 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.
Dec 17 2013
parent reply 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
Dec 17 2013
parent "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!
Dec 17 2013
prev sibling parent reply 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.
Dec 16 2013
parent reply "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.
Dec 16 2013
next sibling parent "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…
Dec 16 2013
prev sibling parent reply "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
Dec 16 2013
parent "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).
Dec 16 2013
prev sibling parent 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
Dec 16 2013
prev sibling next sibling parent reply 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.
Dec 16 2013
parent 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).
Dec 16 2013
prev sibling next sibling parent 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
Dec 16 2013
prev sibling next sibling parent reply "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.
Dec 16 2013
parent reply 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
Dec 17 2013
parent reply "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).
Dec 17 2013
next sibling parent reply 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
Dec 17 2013
next sibling parent reply "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.
Dec 17 2013
parent "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.
Dec 17 2013
prev sibling parent reply "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…
Dec 17 2013
parent reply 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
Dec 17 2013
parent reply "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.
Dec 18 2013
next sibling parent "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)
Dec 18 2013
prev sibling parent reply 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
Dec 18 2013
next sibling parent reply "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.
Dec 18 2013
parent reply 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
Dec 18 2013
parent reply "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?
Dec 18 2013
parent reply 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.
Dec 18 2013
parent "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…
Dec 18 2013
prev sibling parent "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
Dec 18 2013
prev sibling parent reply "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.
Dec 17 2013
parent reply "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).
Dec 17 2013
parent "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.
Dec 17 2013
prev sibling next sibling parent "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;
Dec 17 2013
prev sibling next sibling parent reply 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
Dec 17 2013
next sibling parent reply 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
Dec 17 2013
parent 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
Dec 17 2013
prev sibling parent 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
Dec 17 2013
prev sibling next sibling parent reply "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.
Dec 17 2013
next sibling parent reply 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
Dec 17 2013
next sibling parent "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
Dec 17 2013
prev sibling parent reply 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
Dec 17 2013
next sibling parent 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
Dec 17 2013
prev sibling parent "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":-)])
Dec 17 2013
prev sibling parent reply 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
Dec 17 2013
parent "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
Dec 17 2013
prev sibling next sibling parent reply 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.
Dec 19 2013
parent 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.
Dec 19 2013
prev sibling next sibling parent "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
Dec 19 2013
prev sibling parent reply 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
Mar 14 2015
next sibling parent reply "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)); }
Mar 26 2015
parent "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
Mar 26 2015
prev sibling parent reply "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.
Mar 26 2015
next sibling parent 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
Mar 26 2015
prev sibling parent reply 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
Mar 26 2015
parent reply "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.
Mar 26 2015
parent reply "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
Mar 26 2015
parent reply 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
Mar 26 2015
next sibling parent reply "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.
Mar 26 2015
next sibling parent "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) { ... } ?
Mar 26 2015
prev sibling parent reply 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
Mar 26 2015
parent reply "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.
Mar 26 2015
parent 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
Mar 26 2015
prev sibling parent reply "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?
Mar 26 2015
parent reply "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 -- Не дорог подарок, дорога любовь.
Mar 26 2015
parent "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...
Mar 27 2015