TP4 LIFAP2

#lang racket

(define iverson
  (lambda (b)
    (if b 1 0)))

(define max
  (lambda (a b) ; NxN->N
    (if (>= a b) a b)))


(define ev
  (lambda (arbre)
    (iverson (even? (valeur arbre)))))

(define Caar
  (lambda (x)
    (if (null? x)
        0
        (if (null? (car x))
            0
            (caar x)))))

(define Cadar
  (lambda (x)
    (if (null? x)
        0
        (if (null? (car x))
            0
            (if (null? (cdar x))
                0
                (cadar x))))))


; RECURSIVITE PROFONDE

(define nbsup0
  (lambda (L) ; lists |-> N
    (if (null? L)
        0
        (cond ((list? (car L)) (+ (nbsup0 (car L)) (nbsup0 (cdr L))))
              ((number? (car L)) (+ (iverson (> (car L) 0)) (nbsup0 (cdr L))))
              (else (nbsup0 (cdr L)))))))

(define occ-prof
  (lambda (e L) ; symbols*lists |-> N
    (if (null? L)
        0
        (cond ((list? (car L)) (+ (occ-prof e (car L)) (occ-prof e (cdr L))))
              ((symbol? (car L)) (+ (iverson (equal? (car L) e)) (occ-prof e (cdr L))))
              (else (occ-prof e (cdr L)))))))

(define absliste
  (lambda (L) ; lists |-> lists
    (if (null? L)
        '()
        (cond ((list? (car L)) (append (absliste (car L)) (absliste (cdr L))))
              ((number? (car L)) (cons (abs (car L)) (absliste (cdr L))))
              (else (cons (car L) (absliste (cdr L))))))))

(define profondeur
  (lambda (L) ; lists |-> N
    (if (null? L)
        1
        (cond ((list? (car L)) (max (+ 1 (profondeur (car L)))
                                    (profondeur (cdr L))))
              (else (profondeur (cdr L)))))))

; ARBRES

; PRIMITIVES SUR LES ARBRES

(define arbre-vide?
  (lambda (arbre) ; trees |-> bool
    (null? arbre)))

(define valeur
  (lambda (arbre) ; trees |-> ?
    (car arbre)))

(define fils-g
  (lambda (arbre) ; trees |-> ?
    (cadr arbre)))

(define fils-d
  (lambda (arbre) ; trees |-> mixed
    (caddr arbre)))

(define cons-binaire
  (lambda (a1 a2 a3) ; mixed^3 |-> trees
    (list a1 a2 a3)))

(define arbre-vide
  (lambda ()
    '()))

(define arbre=?
  (lambda (a1 a2)
    (equal? a1 a2)))

(define arbre?
  (lambda (m) ; mixed? |-> bool
    (cond ((null? m) #f)
          ((not (list? (cdr m))) #f)
          ((null? (cdr m)) #f)
          ((not (list? (cddr m))) #f)
          ((null? (cddr m)) #f)
          ((not (list? (cdddr m))) #f)
          (else (null? (cdddr m))))))

(define feuille?
  (lambda (m) ; mixed? |-> bool
    (if (arbre? m)
        (and (null? (cadr m)) (null? (caddr m)))
        #f)))

; FONCTIONS SUR LES ARBRES

(define nb-noeuds
  (lambda (tree)
    (cond ((arbre-vide? tree) 0)
          ((feuille? tree) 1)
          (else (+ 1
                   (nb-noeuds (fils-g tree))
                   (nb-noeuds (fils-d tree)))))))

(define nb-feuilles
  (lambda (tree)
    (cond ((arbre-vide? tree) 0)
          ((feuille? tree) 1)
          (else (+ (nb-feuilles (fils-g tree))
                   (nb-feuilles (fils-d tree)))))))

(define fois2
  (lambda (tree)
    (if (null? tree)
        (arbre-vide)
        (cons-binaire (* 2 (valeur tree))
                      (fois2 (fils-g tree))
                      (fois2 (fils-d tree))))))

(define feuilles
  (lambda (tree)
    (cond ((arbre-vide? tree) '())
          ((feuille? tree) (cons (valeur tree) '()))
          (else (append (feuilles (fils-g tree))
                        (feuilles (fils-d tree)))))))

(define miroir
  (lambda (tree)
    (if (arbre-vide? tree)
        (arbre-vide)
        (cons-binaire (valeur tree)
                      (miroir (fils-d tree))
                      (miroir (fils-g tree))))))

(define pair-impair
  (lambda (arbre)
    (if (arbre-vide? arbre)
        (arbre-vide)
        (if (feuille? arbre)
            (cons-binaire (list (ev arbre)
                                (- 1 (ev arbre)))
                          '()
                          '())
            (cons-binaire (list (+ (ev arbre)
                                   (Caar (pair-impair (fils-g arbre)))
                                   (Caar (pair-impair (fils-d arbre))))
                                (+ (- 1 (ev arbre))
                                   (Cadar (pair-impair (fils-g arbre)))
                                   (Cadar (pair-impair (fils-d arbre)))))
                          (pair-impair (fils-g arbre))
                          (pair-impair (fils-d arbre)))))))

(define a1 '(3 (2 (1 () ()) ()) (7 (5 (4 () ()) (6 () ())) (9 () ()))))
(define a2 '(3 (2 () (1 () ()) ) (7 (5 (4 () ()) (6 () ())) (9 () ()))))
(define a3 '(3 (2 (1 () ()) (0 () ())) (7 (5 (4 () ()) (6 () ())) (9 () ()))))
(define a4 '())