?

Log in

No account? Create an account

Pure kth-largest in D2 - leonardo
View:Recent Entries.
View:Archive.
View:Friends.
View:Profile.
View:Website (My Website).

Tags:, ,
Security:
Subject:Pure kth-largest in D2
Time:03:23 pm
From a recent post ("Determining if a function is effectively pure") on the Lambda the Ultimate Blog:
http://lambda-the-ultimate.org/node/4238

The problem:
Example: A function kth-largest takes a list L of integers and an integer K. It returns the K-th largest value in L. We choose to implement it as follows: create a mutable vector V, copy the integers in L into V, sort V in decreasing order using mutation, and return V[K]. V is then out of scope. There is lots of mutation occurring in the implementation, but the caller can never tell (ignore the possibility of exhausting available memory).

Have people implemented systems that could determine that kth-largest is effectively pure? For which programming languages?

D V2 language is getting good at this, a not much tested solution:
import std.stdio: writeln;

pure void selectionSort(T)(T[] data) {
    foreach (i; 0 .. data.length) {
        size_t minIndex = i;
        foreach (j; i + 1 .. data.length)
            if (data[j] < data[minIndex])
                minIndex = j;
        T temp = data[i];
        data[i] = data[minIndex];
        data[minIndex] = temp;
    }
}

pure T klargest(T)(const T[] data, const int k)
    in {
        assert(k >= 0 && k < data.length);
    } body {
        const int n = data.length;
        T[] dataCopy = data.dup;
        selectionSort(dataCopy);
        return dataCopy[k];
    }

void main() {
    auto d = [8, 2, 0, 0, 5, 10, 10, 11, 4, 4, 5, 12];
    writeln(klargest(d, 5));
}


Here selectionSort() is "weakly pure" (it modifies the array items) and klargest() is "strongly pure", as requested. I have not used the Phobos sort or swap functions because they aren't pure yet.

You are even allowed to cheat a little (normally alloca is not meant to be pure):
import std.stdio: writeln;
import core.exception: OutOfMemoryError;

extern (C) pure void* alloca(const size_t size);

pure void selectionSort(T)(T[] data) {
    foreach (i; 0 .. data.length) {
        size_t minIndex = i;
        foreach (j; i + 1 .. data.length)
            if (data[j] < data[minIndex])
                minIndex = j;
        T temp = data[i];
        data[i] = data[minIndex];
        data[minIndex] = temp;
    }
}

pure T klargest(T)(const T[] data, const int k)
    in {
        assert(k >= 0 && k < data.length);
    } body {
        const int n = data.length;

        T* ptr = cast(T*)alloca(n * T.sizeof);
        if (ptr == null)
            throw new OutOfMemoryError();
        T[] dataCopy = ptr[0 .. n];
        dataCopy[] = data[];

        selectionSort(dataCopy);
        return dataCopy[k];
    }

void main() {
    auto d = [8, 2, 0, 0, 5, 10, 10, 11, 4, 4, 5, 12];
    writeln(klargest(d, 5));
}
comments: Leave a comment Previous Entry Share Next Entry

(Deleted comment)

leonardo_m
Link:(Link)
Time:2011-03-27 04:48 pm (UTC)
> Is there a reason you're basing this on sorting when linear-time algorithms for the problem (e.g. quickselect) exist?

You have probably missed the quotation at the top, from the LtU blog:

We choose to implement it as follows: ...


I have just followed his implementation, the purpose of my code was just to demonstrate how much powerful/good is the current implementation of the purity in D V.2 language (its implementation is not perfect still, some parts needs to be improved). Implementing a Quickselect (something similar is already present in D standard library too) is trivial compared to having a good implementation of purity in a C++-class language :-)
(Reply) (Parent) (Thread)

viheorff
Link:(Link)
Time:2011-04-12 08:41 am (UTC)
I think that is right bout that. Nice info and thanks. Need to get in google feed.

(Reply) (Thread)

Pure kth-largest in D2 - leonardo
View:Recent Entries.
View:Archive.
View:Friends.
View:Profile.
View:Website (My Website).