////////// Exercice 1 ////////// // Predicate testing if `l` is a list function isList(l) { return (l === nil) || ((typeof l === 'object') && hasKey(l, 'car') && hasKey(l, 'cdr') && isList(l.cdr)); } function testIsList(aValue, anExpected) { const result = isList(aValue); const res = result === anExpected ? greenString('OK') : redString('KO'); console.log(`Test isList(${anyToString(aValue)}) (${result}) : ${res}`); } [ [ 6, false ], [ {}, false ], [ { invalidKey: 6 }, false ], [ { car: 6 }, false ], [ { cdr: nil }, false ], [ nil, true ], [ cons(1, nil), true ], [ cons(1, cons(2, cons(3, nil))), true ], ].forEach((anArray) => testIsList(anArray[0], anArray[1])); // Predicate testing if `t` is a tree function isTree(t) { function isTreeList(l) { return (isEmpty(l)) || (isTree(head(l)) && isTreeList(tail(l))); } return (typeof t === 'object') && hasKey(t, 'val') && hasKey(t, 'children') && isList(t.children) && isTreeList(t.children); } function testIsTree(aValue, anExpected) { const result = isTree(aValue); const res = anExpected === result ? greenString("OK") : redString("KO"); console.log(`Test isTree(${anyToString(aValue)}) (${result}) : ${res}`); } [ [ 6, false ], [ {}, false ], [ { invalidKey: 6 }, false ], [ { car: 6 }, false ], [ { cdr: nil }, false ], [ nil, false ], [ node(1, nil), true ], [ node(1, cons(node(2, nil), cons(node(3, nil), nil))), true ], ].forEach((anArray) => testIsTree(anArray[0], anArray[1])); ////////// Exercice 2 ////////// import { listToString, listAppend } from '#src/utils/list.functional.api.js'; // Flattens a list of lists `l` recursively function listFlatten(l) { if (isEmpty(l)) return l; else if (!isList(head(l))) return cons(head(l), listFlatten(tail(l))); else return listAppend(listFlatten(head(l)), listFlatten(tail(l))); } function testFlatten(aList, anExpectedDisp) { const result = listToString()(listFlatten(aList)); const res = result === anExpectedDisp ? greenString('OK') : redString('KO'); console.log(`Test listFlatten(${anyToString(aList)}) == ${result} : ${res}`); } testFlatten(nil, "(| |)"); testFlatten(cons(1,nil), "(|1|)"); testFlatten(aList1, "(|1, 5, 6, 7, 8, 4|)"); testFlatten(aList2, "(|1, 2, 3, 4|)"); // Flattens a list of list `l` in a tail-recursive manner // This supposes that `listReverse` is also tail-recursive function listFlattenTr(l) { function listFlattenInt (l, acc) { console.logA([l, acc]); if (isEmpty(l)) return listReverse(acc); else if (!isList(head(l))) return listFlattenInt(tail(l), cons(head(l), acc)); else if (isEmpty(head(l))) return listFlattenInt(tail(l), acc); else // head(l) is a non-empty list return listFlattenInt( cons(head(head(l)), cons(tail(head(l)), tail(l))), acc); } return listFlattenInt(l, nil); } function testFlattenTr(aList, anExpectedDisp) { const result = listToString()(listFlattenTr(aList)); const res = result === anExpectedDisp ? greenString('OK') : redString('KO'); console.log(`Test listFlattenTr(${anyToString(aList)}) ${result} : ${res}`); } testFlattenTr(nil, "(| |)"); testFlattenTr(cons(nil, nil), "(| |)"); testFlattenTr(cons(1, nil), "(|1|)"); testFlattenTr(aList1, "(|1, 5, 6, 7, 8, 4|)"); testFlattenTr(aList2, "(|1, 2, 3, 4|)"); // Reverses the elements of a list of list `l` function listReverse(l) { if (isEmpty(l)) return l; else if (!isList(head(l))) return listAppend(listReverse(tail(l)), cons(head(l),nil)); else return listAppend(listReverse(tail(l)), cons(listReverse(head(l)), nil)); } function testReverse(aList, anExpectedDisp) { const result = anyToString(listReverse(aList)); const res = result === anExpectedDisp ? greenString('OK') : redString('KO'); console.log(`Test listReverse(${anyToString(aList)}) ${result} : ${res}`); } testReverse(aList1, "(|4, (|8, 7, 6, 5|), 1|)"); testReverse(aList2, "(|(|(|4|), 3, 2|), (|1|)|)"); // Counts the number of occurrences of `e` inside the list of lists // `l` function listCount(e, l) { if (isEmpty(l)) return 0; else { if (!isList(head(l))) { if ((head(l) === e)) return 1 + listCount(e, tail(l)); else return listCount(e, tail(l)); } else return listCount(e, head(l)) + listCount(e, tail(l)) ; } } function testCount(aValue, aList, anExpected) { const result = listCount(aValue, aList); const res = result === anExpected ? greenString('OK') : redString('KO'); console.log(`Test listCount(${aValue}, ${anyToString(aList)}) (${result}) : ${res}`); } testCount(9, aList1, 0); testCount(6, aList1, 1); testCount(3, aList2, 1); ////////// Exercice 3 ////////// // Binary tree functions function binaryNode(v, l, r) { return node(v, cons(l, cons(r, nil))); } function leftChild(v) { return head(children(v)); } function rightChild(v) { return head(tail(children(v))); } // Inserts the value `v` into the binary tree search `t` function binaryTreeInsert(t, v) { if (binaryTreeIsEmpty(t)) return binaryNode(v, tnil, tnil); else { const w = val(t); if (v <= w) { return binaryNode(w, binaryTreeInsert(leftChild(t), v), rightChild(t)); } else { // w < v return binaryNode(w, leftChild(t), binaryTreeInsert(rightChild(t), v)); } } } function testBinaryInsertSimple(aTree, aValue) { console.log(`* Test binaryTreeInsert(${anyToString(aTree)}, ${aValue});`); console.log(`returns\n${anyToString(binaryTreeInsert(aTree, aValue))}`); } testBinaryInsertSimple(tnil, 1); testBinaryInsertSimple(binaryNode(2, tnil, tnil), 1); testBinaryInsertSimple(binaryNode(2, tnil, tnil), 3); console.log("* Test multiple insertions in order"); console.log(binaryTreeDisp([3,1,2,4].reduce(binaryTreeInsert, tnil))); ////////// Exercice 4 ////////// // Compute the scalar product of `v1` and `v2` function scalarProduct(v1, v2) { return v1.map((x, i) => v1[i] * v2[i]). reduce((acc, el) => acc + el, 0); } console.log(`Test scalarProduct([], []) : ${scalarProduct([], [])} === 0`); console.log(`Test scalarProduct([1,2,3], [1,1,1]) : ${scalarProduct([1,2,3], [1,1,1])} === 6`); // Compute the list of the divisors of `n` between 1 and `n` function divisors(n) { return Array.from({length: n}, (_, index) => index + 1). filter((el) => n % el === 0); } console.log(`Test divisors(7) : [${divisors(7)}] === [1,7]`); console.log(`Test divisors(30) : [${divisors(30)}] === [1,2,3,5,6,10,15,30]`);