////////// Exercice 1 ////////// // Filters in `l` the values that are > to `val` function listFilterSup(l, val) { if (isEmpty(l)) return l; else if (head(l) > val) return cons(head(l), listFilterSup(tail(l), val)); else return listFilterSup(tail(l), val); } const aPrettyList = cons(5, cons(150, cons(10, cons(200, cons(-3, nil ))))); console.log(`Test listFilterSup(${anyToString(aPrettyList)}, 100) : ` + `${anyToString(listFilterSup(aPrettyList, 100))}`); // -> [150,200] // Filters in `l` the values that match the predicate `f` function listFilterGen(l, f) { if (isEmpty(l)) return l; else if (f(head(l))) return cons(head(l), listFilterGen(tail(l), f)); else return listFilterGen (tail(l), f); } const aPredicate = (x) => x < 100; console.log(`Test listFilterGen(${anyToString(aPrettyList)}, "smaller than 100") : ` + `${anyToString(listFilterGen(aPrettyList, aPredicate))}`); // -> [5,10,-3] // Filters in `l` the strings that start with an uppercase function listFilterAlpha(l) { function beginsWithMaj (s) { return s[0].toUpperCase() === s[0]; } return listFilterGen(l,beginsWithMaj); } const aStringList = cons('aaaa', cons('Aaaa', cons('bbbb', cons('bBBB', cons('BBBB', cons('ccc', nil)))))); console.log(`Test listFilterAlpha(${anyToString(aStringList)}) : ` + `${anyToString(listFilterAlpha(aStringList))}`); // -> [Aaaa,BBBB] ////////// Exercice 2 ////////// // A polynomial for the tests function myPolynomial(x) { return 3 * x * x + 4.7; } // A first version without currying function differentiate2(h, f) { return (x) => (f(x + h) - f(x - h)) / (2 * h); } function testDiffType(aValStr, aVal, aExpected) { const res = typeof aVal == aExpected ? greenString("OK") : redString("KO"); console.log(`Test type of ${aValStr} = '${aExpected}': ${res}`); } testDiffType("differentiate2(0.001, myPolynomial)", differentiate2(0.001, myPolynomial), "function"); testDiffType("differentiate2(0.001, myPolynomial)(1)", differentiate2(0.001, myPolynomial)(1), "number"); testDiffType("differentiate2(0.00001, Math.sin)", differentiate2(0.00001, Math.sin), "function"); testDiffType("differentiate2(0.00001, Math.sin)(1)", differentiate2(0.00001, Math.sin)(1), "number"); // Specialize differentiate2 on h=0.1 const specDiff2OnH = (f) => differentiate2(0.01, f); // Specialize differentiate2 on f=myPolynomial const specDiff2OnF = (h) => differentiate2(h, myPolynomial); function testDiffVal(aFunName, aFun, aValue, aExpected) { console.log(`Test ${aFunName}(${aValue}) = ${aFun(aValue)}, ` + `expected to be ~= ${aExpected}`); } testDiffVal("specDiff2OnH(myPolynomial)", specDiff2OnH(myPolynomial), 1, 6); testDiffVal("specDiff2OnF(0.01)", specDiff2OnF(0.01), 1, 6); // A second version without currying function differentiate3(h, f, x) { return (f(x + h) - f(x - h)) / (2 * h); } // Specialize differentiate3 on h=0.1 and f = myPolynomial const specDiff3OnHandF = (x) => differentiate3(0.01, myPolynomial, x); testDiffVal("specDiff3OnHandF", specDiff3OnHandF, 1, 6); // This solution uses anonymous functions to ease currying // It is perfectly possible to use functions instead. const differentiateCurry = (h) => (f) => (x) => (f(x+h) - f(x-h)) / (2*h); // The good thing with curryfication if that we can specialize to // directly get the derivative as a function of `x` const specCurryCos = differentiateCurry(0.1)(Math.cos); testDiffVal("specCurryCos", specCurryCos, 0., 0.); testDiffVal("specCurryCos", specCurryCos, Math.PI, 0.); const specCurrySin = differentiateCurry(0.1)(Math.sin); testDiffVal("specCurrySin", specCurrySin, 0., 1.); testDiffVal("specCurrySin", specCurrySin, Math.PI, -1.); // Specialization so that it takes a function and returns a function // approximated with `h=0.1` const specCurryDiff = (f) => differentiateCurry(0.1)(f); // Same as const diff = differentiateCurry(0.1) testDiffVal("specCurryDiff(Math.cos)", specCurryDiff(Math.cos), Math.PI/2, -1.); // Specialization so that it takes `h` and returns the derivative of // Math.cos approximated with `h` const specCurryOnH = (h) => differentiateCurry(h)(Math.cos); testDiffVal("specCurryOnH(0.05)", specCurryOnH(0.05), Math.PI/2, -1.); testDiffVal("specCurryOnH(0.005)", specCurryOnH(0.005), Math.PI/2, -1.); // N-th order differentiation function differentiateN(ordre, h, f) { if (ordre === 0) return f; else return differentiateN(ordre - 1 , h, differentiate2(h, f)); } testDiffType("differentiateN(1, 0.00001, myPolynomial)", differentiateN(1, 0.00001, myPolynomial), "function"); testDiffType("differentiateN(0, 0.00001, myPolynomial)(1)", differentiateN(0, 0.00001, myPolynomial)(1), "number"); testDiffType("differentiateN(1, 0.00001, myPolynomial)(1)", differentiateN(1, 0.00001, myPolynomial)(1), "number"); testDiffType("differentiateN(2, 0.00001, myPolynomial)(1)", differentiateN(2, 0.00001, myPolynomial)(1), "number"); ////////// Exercice 3 ////////// // Generic fixed point function function fixedPoint(x, start, epsilon, hasReached, getNext) { function fixedPointInt(current) { if (hasReached(current, x, epsilon)) return current; else return fixedPointInt(getNext(current, x)); } return fixedPointInt(start); } // Specialization on the computation of the square root function hasReachedSquare(current, x, epsilon) { return Math.abs(current*current - x) < epsilon; } function getNextSquare(current, x) { return (current + x / current) / 2; } // Compute the square root of `x` with precision `epsilon` function squareRoot(x, epsilon) { return fixedPoint(x, 1, epsilon, hasReachedSquare, getNextSquare); } function testSquareRoot(x, epsilon, anExpected) { console.log(`Test squareRoot(${x}, ${epsilon}) = ` + `${squareRoot(x, epsilon)} ~= ${anExpected}`); } testSquareRoot(4, 0.01, 2); testSquareRoot(9, 0.01, 3); // Specialization on the computation of the cubic root function hasReachedCubic(current, x, epsilon) { return Math.abs(current*current*current - x) < epsilon; } function getNextCubic(current, x) { return (2*current + x / (current*current) ) / 3; } // Compute the cubic root of `x` with precision `epsilon` function cubicRoot(x, epsilon) { return fixedPoint(x, 1, epsilon, hasReachedCubic, getNextCubic); } function testCubicRoot(x, epsilon, anExpected) { console.log(`Test cubicRoot(${x}, ${epsilon}) = ` + `${cubicRoot(x, epsilon)} ~= ${anExpected}`); } testCubicRoot(8, 0.01, 2); testCubicRoot(27, 0.01, 3);