Fix the recursive optimized power calculation

[TD_LISP.git] / exercices / lists.lsp

#!/usr/bin/env newlisp

(setq L '(1 9 3 7 0 5))
(setq M '(2 6 5 4 0 1 3))

(define (mem E L) ;la function mem a 2 arguments
  (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)
  (cond
    ((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)
  (cond
    ((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))
(println (member 8 L))

(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 E L)
  (if (boolmemrec E L)
    (cond 
      ((= 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))
(println (find 0 L))

;(trace nil)

(define (tete N L)
  (cond 
    ((null? 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 (intersectL L1 L2) 
  (cond
    ((null? L1) '())
    ((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))
(define (inclu L1 L2) 
  (cond
    ((null? L1) true)
    ((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

(define (unionE L1 L2)
  (cond
    ((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)

(setq T '(((4)((2 5))((((((6 7)))))))))
(define (prof L) 
  (cond 
    ((null? L) 0) 
    ((atom? L) 0) 
    ((max (+ 1 (prof (first L))) (prof (rest L))))))
(println "prof")
(println (prof L))
(println (prof T))

;(trace nil)
;(trace true)

(define (aplatir L) 
  (cond
    ((null? L) '())
    ((atom? L) (list L))
    ((append (aplatir (first L)) (aplatir (rest L))))))
(println "aplatir/flat")
(println (aplatir T))
(println (flat T))

;(trace nil)

(define (elim L) 
  (cond
    ((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))

(define (reverseL L)
  (cond
    ((null? L) '())
    ((append (reverseL (rest L)) (list (first L))))))
(println "reverseL/reverse")
(println (reverseL L))
(println (reverse L))

(define (list< N L)
  (cond
    ((null? 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)
  (cond
    ((null? 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)