sample.ceylon

import ceylon.math.float {random}

{Integer*}? sample(Integer k, Range<Integer> range) {
    value lowerBound = smallest(range.first, range.last);
    return 0 <= k <= range.size then unfold([0, 0],
        ([Integer, Integer] seed) {
            value [chosen, visited] = seed;
            for (i in visited..(range.size)) {
                if (random() < (k - chosen).float / (range.size - i)) {
                    return [i + lowerBound, [chosen + 1, i + 1]];
                }
            }
            else {
                return null;
            }
        }
    );
}

unfold.ceylon

{Element*} unfold<Element, Seed>(Seed seed, [Element, Seed]?(Seed) f)
    => if (exists [element, next] = f(seed)) then {element, *unfold(next, f)} else [];