JPhrases/Intervals

From J Wiki
Jump to: navigation, search

4A. Intervals

It is a common need in programming to have to test whether a given number x lies between two other numbers a and b, with a less than b, called the lower boundary and upper boundary. The numbers that lie between the boundaries are called an interval. Each boundary may or may not be included in the interval. If the boundary is included in the interval, the interval is said to be closed on that side; if it is excluded it is said to be open on that side. If an interval is closed on both sides, it is said to be a closed interval. If it is open on both sides it is said to be an open interval. If it is open on the left side, it is said to be half open on the left. If it is open on the right it is said to be half open on the right. This is usually expressed in common mathematical notation in one of the following ways, which permit all possible ways in which the boundary numbers are or are not included in the interval:

{x | a < x < b} (a , b) open
{x | a < x * b} (a , b] half-open on the left
{x |a * x < b} [a , b) half-open on the right
{x |a * x * b} [a , b] closed

In the usual case, a and b are finite numbers, with a less than b. If we permit the boundaries to be infinite, and a to be equal to b, we get the cases tabulated below. See Andrew M. Gleason, Fundamentals of Abstract Analysis, Addison-Wesley, 1966, sect. 14-10.7

{x | a < x } (a , _) x greater than a
{x | x < b} (__, b) x less than b
R (__ , _) x all finite real numbers
{x | x * b} (__ , b] x less than or equal to b
{x | a * x} [a , _) x greater than or equal to a
{a} [a , a] x equal to a
{} (a , a) x is the empty set

In the verbs below the limits a and b form the two items of the right argument y. The verbs d0 through d3 below are reasonably efficient and allow testing for inclusion in an interval by using the relational symbols < and ≤ in pairs in all four possible ways. The verbs d5 through d8 use a common subverb d9 which when applied between arguments x and y yields a result between _ 2 and 2, depending on whether x is less than a, equal to a, strictly between a and b, equal to b, or greater than b, thus permitting a wide variety of tests. It subtracts y from x, yielding a two-atom result, and takes the sum of the signum of this. They are not particularly efficient, but are interesting pedagogically. The verbs d10 and d11 do not generalize readily, but may be useful in the special case of a need for a half-open left interval. All of these verbs may be used with Boolean, integer, or real arguments. When used with real arguments, you may wish to consider whether the relations should be fuzzed or made with zero tolerance.

d0=: OO=: ({.@] < [)*.([ < {:@]) x OinO y (Is x in open interval y)
d1=: OC=: ({.@] < [)*.([ <: {:@]) x OinC y
d2=: CO=: ({.@] <: [)*.([ < {:@]) x CinO y
d3=: CC=: ({.@] <: [)*.([ <: {:@]) x CinC y
d4=: +/"1@d2 Number of x OinC y
d5=: 0: e.~ class x OinO y
d6=: 0 1"_ e.~ class x OinC y
d7=: _1 0 "_ e.~ class x CinO y
d8=: _1 0 1"_ e.~ class x CinC y
d9=: class=: [: +/"1 [: * -/ Class _2 to 2: <A ="a" CINC="b">b
d10=: [: ~:/ >:/~ x OinC y
d11=: ] >/ .>~ [: ,.~ [ x OinC y
d12=: sgd=: *@(-~/~) Signum of difference
d13=: 0&=@(+/)@sgd OO
d14=: e.&0 1@(+/)@sgd OC
d15=: 0&>:@(%/)@sgd CO
d16=: >/@sgd CC
   x=:i.12 [ y=: 3 8
   x ([ , OO , OC ,CO ,: CC) y
0 1 2 3 4 5 6 7 8 9 10 11
0 0 0 0 1 1 1 1 0 0  0  0	( )
0 0 0 0 1 1 1 1 1 0  0  0	( ]
0 0 0 1 1 1 1 1 0 0  0  0	[ )
0 0 0 1 1 1 1 1 1 0  0  0	[ ]


   x(CC = OC +. CO) y	NB. Tautology
1 1 1 1 1 1 1 1 1 1 1 1

   x (d5 = OO) y
1 1 1 1 1 1 1 1 1 1 1 1

   x ,: x d9 y
 0  1  2  3 4 5 6 7 8 9 10 11
_2 _2 _2 _1 0 0 0 0 1 2  2  2

   x d12 y
_1 _1 _1  0  1  1  1  1 1 1 1 1
_1 _1 _1 _1 _1 _1 _1 _1 0 1 1 1