3

How can express this imperative function in a functional, array-based language like K (or Q)?

In sloppy C++:

vector<int> x(10), y(10); // Assume these are initialized with some values.

// BTW, 4 is just a const -- it's part of the algorithm and is arbitrarily chosen.

vector<int> result1(x.size() - 4 + 1); // A place to hold a resulting array.
vector<int> result2(x.size() - 4 + 1); // A place to hold another resulting array.

// Here's the code I want to express functionally.
for (int i = 0; i <= x.size() - 4; i++) {
    int best = x[i + 0] - y[i + 0];
    int bad = best;
    int worst = best;
    for(int j = 0; j < 4; j++) {
        int tmp = x[i + j] - y[i + 0];
        bad = min(bad, tmp);
        if(tmp > best) {
            best = tmp;
            worst = bad;
        }
    }
    result1[i] = best
    result2[i] = worst
}

I would most like to see this in kdb and Q but other functional languages are welcome.

2
  • 2
    What is this code trying to do? Jul 18, 2011 at 16:16
  • It is trying to calculate two things: First, at each point in x, we want the maximum over the next 4 elements (let's call this Nx = max(x), at location Px, where Px = 0..3. Second, at each point in x, we want the minimum over the next Px points. Jul 19, 2011 at 19:59

3 Answers 3

5

porting @silentbicycle's k directly to q yields

q)a:1+til 8
q)b:8#0
q){(max x;min x)}flip{4#y _ x}[a+b;]each til count a
4 5 6 7 8 8 8 8
1 2 3 4 5 6 7 8

another approach, slightly more vectorized (imao):

q){(max;min)@\:flip 4#'(til count x)_\:x+y}[a;b]
4 5 6 7 8 8 8 8
1 2 3 4 5 6 7 8
4

In Kona (an open-source K dialect):

First, set some example values (using same as the Clojure solution):

a:1+!8;b:8#0        / a is 1..8, b is eight 0s

Then:

{(|/x;&/x)}@+{4#y _ x}[a+b;]'!#a

Where a and b are your x and y variables above. (K makes a special case for the variables x, y, and z.)

To break that up a bit more:

maxmin:{(|/x;&/x)}  / (max;min) pairs of x
get4:{4#y _ x}      / next 4 from x, starting at y
                    / with <4 remaining, will repeat; doesn't matter for min or max
/ maxmin applied to flipped results of get4(a-b) at each index 0..(length a)-1
maxmin@+get4[a-b;]'!#a

/ result
(4 5 6 7 8 8 8 8
 1 2 3 4 5 6 7 8)
1

In Clojure (a dialect of Lisp):

(defn minmax [x y](map #(vector (- (apply max %1) %2) (- (apply min %1) %2)))(partition-all 4 1 x) y)

(minmax [1 2 3 4 5 6 7 8] [0 0 0 0 0 0 0 0])

will give

[([4 1] [5 2] [6 3] [7 4] [8 5] [8 6] [8 7] [8 8])`(result 1, result 2) as output..

Then

(map #(first %1) result) is result1
(map #(last %1) result) is result2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.