LISP Function_Assignment 1 Solution

FUNDAMENTALS OF ARTIFICIAL INTELLIGENCE
1. Write a single LISP function, called SUB-LIST, that takes a list L and two nonnegative integers START and LEN, and returns the sub-list of L starting at position START and having length LEN. Assume that the first element of L has position 0.
For example,
(SUB-LIST ‘(a b c d) 0 3) returns (a b c); (SUB-LIST ‘(a b c d) 3 1) returns (d); (SUB-LIST ‘(a b c d) 2 0) returns NIL.
- if the first parameter is greater than or equal to the length of the list, return NIL. - if the second parameter is too large that it goes beyond the elements of the list, just return whatever elements it covers.
2. Write a single LISP function, called SPLIT-LIST, that takes a list L, and returns a list of two lists L1 and L2, in that order, such that
- L is the result of appending L1 and L2 - Length of L2 minus length of L1 is 0 or 1.
For example,
(SPLIT-LIST ‘(a b c d)) returns ((a b) (c d)); (SPLIT-LIST ‘(a b c d e)) returns ((a b) (c d e)); NOTE: ((a b c) (d e)) is incorrect; (SPLIT-LIST ‘(a b c d e f)) returns ((a b c) (d e f)).
You can call the function SUB-LIST from SPLIT-LIST.
3. A binary tree can be represented as follows:
- if the tree contains a single node N, it can be represented by atom N - if the tree has more than one node and is rooted at N, then it can be represented by a list (L R) where L represents the left subtree of N and R represents the right subtree of N
Write a single LISP function, called LIST2BTREE, that takes a non-empty list of atoms LEAVES, and returns a binary tree such that
- The tree leaves are the elements of LEAVES - For any internal (non-leaf) node in the tree, the number of leaves in its right branch minus the number of leaves in its left branch is 0 or 1.
For example,
(LIST2BTREE '(1)) returns 1; (LIST2BTREE '(1 2)) returns (1 2); (LIST2BTREE '(1 2 3)) returns (1 (2 3)) ; (LIST2BTREE '(1 2 3 4)) returns ((1 2) (3 4));
(LIST2BTREE '(1 2 3 4 5 6 7)) returns ((1 (2 3)) ((4 5) (6 7))); (LIST2BTREE '(1 2 3 4 5 6 7 8)) returns (((1 2) (3 4)) ((5 6) (7 8))).
You can call the function SPLIT-LIST from LIST2BTREE.
4. Write a single LISP function, called BTREE2LIST, that takes a binary tree TREE, and returns a list of atoms. (Assume TREE follows the constraints we defined in problem 3)
 As the input is a binary tree, each node has at most 2 children.  This function is the inverse of LIST2BTREE. That is, (BTREE2LIST (LIST2BTREE X)) = X for all lists of atoms X.
For example,
(BTREE2LIST 1) returns (1); (BTREE2LIST '(1 2)) returns (1 2); (BTREE2LIST '(1 (2 3))) returns (1 2 3) ; (BTREE2LIST '((1 2) (3 4))) returns (1 2 3 4); (BTREE2LIST '((1 (2 3)) ((4 5) (6 7)))) returns (1 2 3 4 5 6 7); (BTREE2LIST '(((1 2) (3 4)) ((5 6) (7 8)))) returns (1 2 3 4 5 6 7 8).