////////// Exercice 1 ////////// // Computes the list of integers between `a` and `b` function listIota(a, b) { if (a >= b) return nil; else return cons(a, listIota(a+1, b)); } // Computes a string displaying the contents of the list `l` function listDisp(l) { function listDispRec(l) { if (isEmpty(l)) return ""; else if (isEmpty(tail(l))) return `${head(l)}`; else return `${head(l)},${listDispRec(tail(l))}`; } return `(|${listDispRec(l)}|)`; } function testListIota(a, b) { console.log(`Test listIota(${a}, ${b}) : ${listDisp(listIota(a, b))}`); } testListIota(1, 4); // -> { car: 1, cdr: { car: 2, cdr: { car: 3, cdr: {} } } } testListIota(4, 1); // -> nil ////////// Exercice 2 ////////// // Computes the number of elements of the list `l` function listLength(l) { if (isEmpty(l)) return 0; else return 1 + listLength(tail(l)); } function testLength(aList, anExpected) { const result = listLength(aList); const res = result === anExpected ? "OK" : "KO"; console.log(`Test listLength(${listDisp(aList)}) (${result}) : ${res}`); } testLength(nil, 0); // -> 0 testLength(cons(11, cons(-22, nil)), 2); // -> 2 testLength(cons(-3, cons(-2, cons(-1, nil))), 3); // -> 3 testLength(listIota(1,6), 5); // -> 5 ////////// Exercice 3 ////////// // Computes the list of the absolute values of `l` function listAbsRec(l) { if (isEmpty(l)) return nil; else return cons(Math.abs(head(l)), listAbsRec(tail(l))); } function testAbsRec(aList) { console.log(`Test listAbsRec(${listDisp(aList)}) : ` + `${listDisp(listAbsRec(aList))}`); } testAbsRec(cons(11, cons(-22, nil))); // -> (|11,22|) testAbsRec(cons(-3, cons(-2, cons(-1, nil)))); // -> (|3,2,1|) ////////// Exercice 4 ////////// // Concatenates `l1` and `l2` assuming that // they are both immutable function listAppend(l1, l2) { if (isEmpty(l1)) return l2; else return cons(head(l1), listAppend(tail(l1), l2)) ; } function testListAppend(aList1, aList2) { const res = listAppend(aList1, aList2); console.log(`Test listAppend(${listDisp(aList1)}, ${listDisp(aList2)})` + `: ${listDisp(res)}`); } testListAppend(nil, listIota(1, 4)); testListAppend(listIota(1, 3), nil); testListAppend(listIota(1, 3), listIota(1, 4)); // Concatenates `l1` and `l2` assuming that // they are both immutable, in a tail-recursive manner function listAppendTr(l1, l2) { function listAppendInt(to_append, to_mirror, lasts) { if (isEmpty(to_append)) { if (isEmpty(to_mirror)) return lasts; else return listAppendInt(to_append, tail(to_mirror), cons(head(to_mirror), lasts)); } else return listAppendInt(tail(to_append), cons(head(to_append), to_mirror), lasts); } return listAppendInt(l1, nil, l2); } function testListAppendTr(aList1, aList2) { const res = listAppendTr(aList1, aList2); console.log(`Test listAppendTr(${listDisp(aList1)}, ${listDisp(aList2)})` + `: ${listDisp(res)}`); } testListAppend(nil, listIota(1, 4)); testListAppend(listIota(1, 3), nil); testListAppend(listIota(1, 3), listIota(1, 4)); ////////// Exercice 5 ////////// // Rotates the list `l` to the left function listRotateLeft (l) { if (isEmpty(l)) return l; else return listAppend(tail(l), cons(head(l), nil)); } function testRotateLeft(aList) { console.log(`Test listRotateLeft(${listDisp(aList)}) : ` + `${listDisp(listRotateLeft(aList))}`); } testRotateLeft(nil); // -> nil testRotateLeft(listIota(1,5)); // -> (|2,3,4,1|) // Returns the last element of the list `l`, nil if empty function listGetLast(l) { if (isEmpty(l)) return nil; else if (isEmpty(tail(l))) return head(l); else return listGetLast(tail(l)); } function testGetLast(aList) { console.log(`Test listGetLast(${listDisp(aList)}) : ${listGetLast(aList)}`); } testGetLast(listIota(1,2)); // -> 1 testGetLast(listIota(1,5)); // -> 4 // Removes the last element of the list `l` function listRemoveLast(l) { if (listLength(l) <= 1) return nil; else return cons(head(l), listRemoveLast(tail(l))); } function testRemoveLast(aList) { console.log(`Test listRemoveLast(${listDisp(aList)}) : ` + `${listDisp(listRemoveLast(aList))}`); } testRemoveLast(nil), // -> nil testRemoveLast(listIota(1,5)); // -> (|1,2,3|) // Rotates the list `l` to the right function listRotateRight (l) { if (isEmpty(l)) return l; else return cons(listGetLast(l), listRemoveLast(l)); } function testRotateRight(aList) { console.log(`Test listRotateRight(${listDisp(aList)}) : ` + `${listDisp(listRotateRight(aList))}`); } testRotateRight(nil); // -> (|4,1,2,3|) testRotateRight(listIota(1,5)); // -> (|4,1,2,3|) ////////// Exercice 6 ////////// // Inserts `aValue` into the sorted list `aList` function listInsert(aValue, aList) { if (isEmpty(aList) || head(aList) > aValue) return cons(aValue, aList); else return cons(head(aList), listInsert(aValue, tail(aList))); } function testListInsert(aValue, aList) { console.log(`Test listInsert(${aValue}, ${listDisp(aList)}) : ` + `${listDisp(listInsert(aValue, aList))}`); } const l1 = cons (1, cons (4, cons (6, cons (10, nil)))); testListInsert(0, l1); // -> (|0,1,4,6,10|) testListInsert(5, l1); // -> (|1,4,5,6,10|) // Sorts the list `l` using insertion sort function listSortInsertNumbers(l) { if (isEmpty(l)) return l; else return listInsert(head(l), listSortInsertNumbers(tail(l))); } function testListInsertSort(aList) { console.log(`Test listSortInsertNumbers(${listDisp(aList)}) : ` + `${listDisp(listSortInsertNumbers(aList))}`); } const l2 = cons (15, cons (4, cons (84, cons (-2, nil)))); testListInsertSort(l2); // -> (|-2,4,15,84|) // Sorts the list `l` according to the comparator `op` using // an insertion sort. `op` is a 2-parameter function returning // a boolean, telling if the 1st parameter is less-than the 2nd function listSortInsertGen(l, op) { function insertGen(e, l) { if (isEmpty(l) || op(e, head(l))) return cons(e, l); else return cons(head(l), insertGen(e, tail(l))); } if (isEmpty(l)) return l; else return insertGen(head(l), listSortInsertGen(tail(l), op)); } function testListInsertSortGen(aList, aCmp, aCmpDisp) { console.log(`Test listSortInsertGen(${listDisp(aList)}, ${aCmpDisp}) : ` + `${listDisp(listSortInsertGen(aList, aCmp))}`); } const l3 = cons(15, cons(4, cons(84, cons(-2, nil)))); testListInsertSortGen(l3, (x,y) => x(|-2,4,15,84|) testListInsertSortGen(l3, (x,y) => x>y, "decreasing order"); // ->(|84,15,4,-2|) // Comparator between strings that ignores case function compareStrings(s1, s2) { return s1.toLocaleLowerCase() < s2.toLocaleLowerCase(); } const phrase = cons('Abba', cons('est', cons('un', cons('Groupe', cons('Suedois', nil))))); testListInsertSortGen(phrase, compareStrings, "string order"); // -> (|Abba,est,Groupe,Suedois,un|) ////////// Exercice 7 ////////// // Merges the sorted lists `a` and `b` into a sorted list function listMerge (a, b) { if (isEmpty(a)) return b; else if (isEmpty(b)) return a; else if (head(a) < head(b)) return (cons(head(a), listMerge( tail(a), b))); else return (cons(head(b), listMerge(a, tail(b)))); } const left = cons(1, cons(6, cons(8, cons(47, cons(87, nil))))); const right = cons(3, cons(8, cons(9, cons(21, cons(50, nil))))); console.log(`Test listMerge(${listDisp(left)}, ${listDisp(right)}) : ` + `${listDisp(listMerge(left, right))}`); // Splits the list `l` into two parts of near-equal length //////////////////////////////////////////////////////////////// function listSplit(l) { if (isEmpty(l)) return [nil, nil]; else if (isEmpty(tail(l))) return [l, nil]; else { let [x1, x2] = [head(l), head(tail(l))]; let l2 = tail(tail(l)); let [u1,u2] = listSplit(l2); return [cons(x1, u1), cons(x2, u2)]; } } let l4 = listIota(-3,3); let [aSplit1, aSplit2] = listSplit(l4); console.log(`Test listSplit(${listDisp(l4)}) : ` + `${listDisp(aSplit1)}, ${listDisp(aSplit2)}`); // Sorts the list `l` using a merge-sort function listMergeSort(l) { if (isEmpty(l) || isEmpty(tail(l))) return l; else { let [l1, l2] = listSplit(l); return listMerge( listMergeSort(l1), listMergeSort(l2)); } } const l5 = cons(31, cons(17, cons(83, cons(12, cons(51, nil))))); console.log(`Test listMergeSort(${listDisp(l5)}) : ${listDisp(listMergeSort(l5))}`); ////////// Exercice 8 ////////// // Tests if the list `l` is a palindrome or not // (yes it takes an 'e' at the end in english) function listIsPalindrome(aList) { if (isEmpty(aList) || isEmpty(cdr(aList))) return true; else return ((car(aList) === listGetLast(aList)) && listIsPalindrome(cdr(listRemoveLast(aList)))); } function testPalindrome(aList, anExpected) { const res = listIsPalindrome(aList) === anExpected ? 'OK' : 'KO'; console.log(`Test if ${listDisp(aList)} is a palindrome (${anExpected}) : ${res}`); } testPalindrome(cons('', nil), true); testPalindrome(cons('a', nil), true); testPalindrome(cons('a', cons('b', nil)), false); testPalindrome(cons('a', cons('b', cons('b', cons('a', nil)))), true); testPalindrome(cons('b', cons('b', cons('b', cons('a', nil)))), false);