const fc = require('fast-check');
function next(outputForIndexes, datasetLength) {
for (let cursor = outputForIndexes.length -1 ; cursor >= 0 ; --cursor) {
outputForIndexes[cursor]++;
if (outputForIndexes[cursor] < datasetLength) {
return true;
}
outputForIndexes[cursor] = 0;
}
return false;
}
function isAssociative(datasetLength, f) {
for (let a = 0 ; a !== datasetLength ; ++a) {
for (let b = 0 ; b !== datasetLength ; ++b) {
for (let c = 0 ; c !== datasetLength ; ++c) {
if (f(f(a,b),c) !== f(a,f(b,c))) {
return false;
}
}
}
}
return true;
}
function buildAssociativeFunction(datasetLength, randNat) {
const numFunOutputs = datasetLength * datasetLength;
const outputForIndexes = [...Array(numFunOutputs)].map(() => randNat() % datasetLength);
while (true) {
const f = (a, b) => outputForIndexes[a * datasetLength + b];
if (isAssociative(datasetLength, f)) {
return f;
}
next(outputForIndexes, datasetLength)
}
}
function binaryAssociativeFunction(arb) {
return fc.tuple(
// min=3 for tests purposes,
// max=3 because buildAssociativeFunction takes too long
fc.set(arb, {minLength: 3, maxLength: 3, compare: (a, b) => fc.stringify(a) === fc.stringify(b)}),
fc.infiniteStream(fc.nat()).noBias()
)
.map(([dataset, randomStream]) => {
const associativeF = buildAssociativeFunction(
dataset.length,
() => randomStream.next().value
);
const stringifiedDataset = dataset.map(d => fc.stringify(d));
return (a, b) => {
// compute index for a
const stringifiedA = fc.stringify(a);
let indexA = stringifiedDataset.indexOf(stringifiedA);
if (indexA === -1) indexA = fc.hash(stringifiedA) % dataset.length;
// compute index for b
const stringifiedB = fc.stringify(b);
let indexB = stringifiedDataset.indexOf(stringifiedB);
if (indexB === -1) indexB = fc.hash(stringifiedB) % dataset.length;
// compute answer
const indexResult = associativeF(indexA, indexB);
if (!(indexA in dataset)) throw new Error('unexpected: invalid indexA');
if (!(indexB in dataset)) throw new Error('unexpected: invalid indexB');
if (!(indexResult in dataset)) throw new Error('unexpected: invalid indexResult');
return dataset[indexResult];
};
})
}
// Just trying with one of the generated functions
const a = 'a';
const b = 'b';
const c = 'c';
const f1 = fc.sample(binaryAssociativeFunction(fc.string()), 1)[0];
console.log('a,b -> ' + f1(a, b));
console.log('(a,b),c -> ' + f1(f1(a, b), c));
console.log('b,c -> ' + f1(b, c));
console.log('a,(b,c) -> ' + f1(a, f1(b, c)));
// Property to confirm it works
fc.assert(fc.property(
binaryAssociativeFunction(fc.string()), fc.string(), fc.string(), fc.string(),
(f, a, b, c) => f(f(a,b),c) === f(a,f(b,c))))
no comments
sign in to comment