Fix the recursive optimized power calculation

[TD_LISP.git] / exercices / lists.lsp

diff --git a/exercices/lists.lsp b/exercices/lists.lsp
index 1930b1ca3a6e1b18cdf0300b80c11b6bec5a0299..35590dada335ff070e4a9546859cdafbe8777b1c 100755 (executable)
--- a/exercices/lists.lsp
+++ b/exercices/lists.lsp
@@ -7,6 +7,7 @@
   (if (null? L) nil
     (if (= (first L) E) true
       (mem E (rest L)))))
+(println "mem rt bool")
 (println (mem 9 L))
 
 (define (boolmemrec E L)
@@ -14,12 +15,14 @@
     ((null? L) nil)
     ((= (first L) E) true)
     ((mem E (rest L)))))
+(println "mem rec rt bool")
 (println (boolmemrec 10 L))
 
 (define (mem E L) ;la function mem a 2 arguments
   (if (null? L) nil
     (if (= (first L) E) L
       (mem E (rest L)))))
+(println "mem rt list")
 (println (mem 3 L))
 
 (define (mem E L)
@@ -27,6 +30,7 @@
     ((null? L) nil)
     ((= (first L) E) L)
     ((mem E (rest L)))))
+(println "mem rec rt list")
 (println (mem 9 L))
 (println (member 9 L))
 (println (mem 8 L))
@@ -35,18 +39,20 @@
 (define (concatene L1 L2)
   (if (null? L1) L2
     (cons (first L1) (concatene (rest L1) L2))))
+(println "concatene/append")
 (setq C (concatene L M))
 (println C)
 (println (append L M))
 
 ;(trace true)
 
-(define (rang x L)
-  (if (boolmemrec x L)
+(define (rang E L)
+  (if (boolmemrec E L)
     (cond 
-      ((= x (first L)) 0)
-      ((+ 1 (rang x (rest L)))))
+      ((= E (first L)) 0)
+      ((+ 1 (rang E (rest L)))))
     nil))
+(println "rang/find")
 (println (rang 4 L))
 (println (find 4 L))
 (println (rang 0 L))
@@ -54,21 +60,23 @@
 
 ;(trace nil)
 
-(define (tete n L) 
+(define (tete N L)
   (cond 
     ((null? L) '())
-    ((= n 0) '())
-    ((cons (first L) (tete (- n 1) (rest L))))))
+    ((= N 0) '())
+    ((cons (first L) (tete (- N 1) (rest L))))))
+(println "tete/slice")
 (println (tete 3 L))
 (println (slice L 0 3))
 (println (0 3 L))
 
-(define (inter L1 L2) 
+(define (intersectL L1 L2) 
   (cond
     ((null? L1) '())
-    ((member (first L1) L2) (cons (first L1) (inter (rest L1) L2)))
-    ((inter (rest L1) L2))))
-(println (inter L M))
+    ((member (first L1) L2) (cons (first L1) (intersectL (rest L1) L2)))
+    ((intersectL (rest L1) L2))))
+(println "intersectL/intersect")
+(println (intersectL L M))
 (println (intersect L M))
 
 (setq N '(1 9 3))
@@ -78,6 +86,7 @@
     ((null? L2) nil)
     ((= (first L1) (first L2)) (inclu (rest L1) (rest L2))) 
     ((inclu L1 (rest L2)))))
+(println "inclu")
 (println (inclu N L))
 (println (inclu L M))
 ;did not found a newlisp builtin equivalent function
@@ -87,8 +96,10 @@
     ((null? L1) L2)
     ((member (first L1) L2) (unionE (rest L1) L2))
     ((cons (first L1) (unionE (rest L1) L2)))))
+(println "unionE/union")
 (println (unionE L M))
 (println (unionE N L))
+(println (union N L))
 
 ;(trace true)
 
@@ -98,6 +109,7 @@
     ((null? L) 0) 
     ((atom? L) 0) 
     ((max (+ 1 (prof (first L))) (prof (rest L))))))
+(println "prof")
 (println (prof L))
 (println (prof T))
 
@@ -106,10 +118,11 @@
 
 (define (aplatir L) 
   (cond
-    ((null? L) nil)
-    ((atom? L) (list L)) ;FIXME: the "casting" is not working properly
+    ((null? L) '())
+    ((atom? L) (list L))
     ((append (aplatir (first L)) (aplatir (rest L))))))
-;(println (aplatir T))
+(println "aplatir/flat")
+(println (aplatir T))
 (println (flat T))
 
 ;(trace nil)
@@ -119,6 +132,7 @@
     ((null? L) '())
     ((member (first L) (rest L)) (elim (rest L)))
     ((cons (first L) (elim (rest L))))))
+(println "elim/unique")
 (println (elim C))
 (println (unique C))
 
@@ -126,22 +140,86 @@
   (cond
     ((null? L) '())
     ((append (reverseL (rest L)) (list (first L))))))
+(println "reverseL/reverse")
 (println (reverseL L))
 (println (reverse L))
 
-(define (list< n L)
+(define (list< N L)
   (cond
     ((null? L) '())
-    ((>= (first L) n) (list< n (rest L)))
-    ((cons (first L) (list< n (rest L))))))
+    ((>= (first L) N) (list< N (rest L)))
+    ((cons (first L) (list< N (rest L))))))
+(println "list<")
 (println (list< 5 L))
 (println (list< 5 C))
 
-(define (list>= n L)
+(define (list>= N L)
   (cond
     ((null? L) '())
-    ((< (first L) n) (list>= n (rest L)))
-    ((cons (first L) (list>= n (rest L))))))
+    ((< (first L) N) (list>= N (rest L)))
+    ((cons (first L) (list>= N (rest L))))))
+(println "list>=")
 (println (list>= 5 C))
 
+;(trace true)
+
+(define (qsort L)
+  (cond
+    ((null? L) '())
+    ((append 
+       ;the pivot is the first element of the list
+       (qsort (list< (first L) (rest L))) 
+       (list (first L))
+       (qsort (list>= (first L) (rest L)))))))
+(println "qsort")
+(println (qsort C))
+
+;(trace nil)
+
+;we suppose both lists are flat
+(setq L1 '(A ? ? B C D ?))
+(setq L2 '(? A B ? C ? ? D))
+
+;(println "replace")
+;(println L1)
+;(println L2)
+;the replace function modify the passed argument
+;(println (replace 'B L1))
+;(println (replace '? L1))
+;(println (replace '? L2))
+;(println L1)
+;(println L2)
+
+(define (filtre L1 L2 C)
+  ;the replace function modify the passed argument
+  ;FIXME: use the function argument C
+  (replace '? L1)
+  (replace '? L2)
+  (cond 
+    ((and (null? L1) (null? L2)) true)
+    ((and (not (null? L1)) (null? L2)) nil)
+    ((and (null? L1) (not (null? L2))) nil)
+    ((and (inclu L1 L2) (inclu L2 L1) true))))
+(println "filtre")
+(println (filtre L1 L2 ?))
+(println (filtre L M ?))
+
+;algorithm written on the board
+(define (filtrerec L1 L2 C)
+  ;FIXME: use the function argument C
+  (cond
+    ((null? L1)
+      (cond
+        ((null? L2) true)
+        ((= '? (first L2)) (filtrerec L1 (rest L2)))
+        (nil)))
+    ((null? L2) (filtrerec L2 L1))
+    ((= '? (first L1)) (filtrerec (rest L1) L2))
+    ((= '? (first L2)) (filtrerec L1 (rest L2)))
+    ((= (first L1) (first L2)) (filtrerec (rest L1) (rest L2)) )
+    (nil)))
+(println "filtrerec")
+(println (filtrerec L1 L2 ?))
+(println (filtrerec L M ?))
+
 (exit)