// Functions on pointed pairs function cons(_car, _cdr) { return { car: _car, cdr: _cdr }; } const nil = {}; function car(cons) { return cons['car']; } function cdr(cons) { return cons['cdr']; } // Functions on lists function head(l) { return car(l); } function tail(l) { return cdr(l); } function isEmpty(l) { return l === nil; } // 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)}]`; } //////////////////////////////////////////////////////////////// // Functions on trees function node(_val, _children) { return { val: _val, children: _children }; } function val(tree) { return tree['val']; } function children(tree) { return tree['children']; } ////////// Exercice 1 ////////// // Predicate testing if an object `obj` has a field `key` function hasKey(obj, key) { return Object.keys(obj).includes(key); } console.log(hasKey({ name: "Alf" }, "name")); // -> true console.log(hasKey({ name: "Alf" }, "cat")); // -> false ////////// Exercice 2 ////////// // Returns a string displaying the contents of a list of lists `l` function listDispDeep(l) { function listDispDeepInt(l) { if (isEmpty(l)) return ''; else if (isEmpty(tail(l))) { if (!isList(head(l))) return `${head(l)}`; else return `[${listDispDeepInt(head(l))}]`; } else if (!isList(head(l))) return `${head(l)},${listDispDeepInt(tail(l))}`; else return `[${listDispDeepInt(head(l))}],${listDispDeepInt(tail(l))}`; } return `[${listDispDeepInt(l)}]`; } let aList1 = cons(1, cons(listIota(5,9), cons(4, nil))); // -> [[1],[5,6,7,8],4] let aList2 = cons(cons(1, nil), cons(cons(2, cons(3, nil)), cons(4, nil))); // -> [[1],[2,3],4] console.log(`Disp aList1 : ${listDispDeep(aList1)}`); console.log(`Disp aList2 : ${listDispDeep(aList2)}`); let aList = cons(cons(1, nil), cons(cons(2, cons(3, nil)), cons(4, nil))); // -> [ [1], [2, 3], 4 ] listFlatten(aList); // -> [1, 2, 3, 4] let aList = cons('a', cons('b', cons(cons('c', cons('d', nil)), cons('e', cons('f', nil))))); // -> [a, b, [c, d], e, f] listReverse(aList); // -> [f, e, [d, c], b, a] let aList = cons('a', cons(cons('b', cons('a', cons(cons('c', cons('a', nil)), nil))), cons('d', cons('a', nil)))); // -> [a [b a [c a] d a] countList('a', aList); // -> 4 ////////// Exercice 3 ////////// // Functions on binary trees const tnil = {}; function binaryTreeIsEmpty(t) { return t === tnil; } // Returns a string displaying the contents of the binary tree `t` function binaryTreeDisp(t) { function btDisp(t, depth) { const prefix = (depth >= 1) ? (" ".repeat(depth-1) + "⌞") : "" if (binaryTreeIsEmpty(t)) { return `${prefix}{}\n`; } else { return `${prefix}${val(t)}\n${btListDisp(children(t), depth+1)}`; } } function btListDisp(tl, depth) { if (isEmpty(tl)) return ""; else if (isEmpty(tail(tl))) return `${btDisp(head(tl), depth)}`; else return `${btDisp(head(tl), depth)}${btListDisp(tail(tl), depth)}`; } return btDisp(t, 0); } let aTree = binaryNode(6, binaryLeaf(3), binaryNode(11, binaryLeaf(7), tnil)); console.log(`Disp : \n${binaryTreeDisp(aTree)}`); ////////// Exercice 4 //////////