TD2 prog fonctionnelle Polytech

OCaml
type 'a bintree =
  | Node of 'a bintree * 'a * 'a bintree
  | Empty
 
 
let rec nbFeuilles = function 
  | Empty                  -> 0
  | Node (Empty, x, Empty) -> 1
  | Node (left, _, right)  -> nbFeuilles left + nbFeuilles right
 
let rec nbNoeuds = function 
  | Empty               -> 0
  | Node (left,_,right) -> 1 + nbNoeuds left + nbNoeuds right
 
let exemple = Node (Node(Empty, 1, Empty), 2, Node(Node(Node(Empty,6,Empty),5,Empty),3,Node(Empty,4,Empty)))
 
  
let rec hauteur = function
  | Empty               -> 0
  | Node (left,_,right) -> 1 + max (hauteur left) (hauteur right)
 
 
     
let maxo (x: 'a option) (y : 'a option) : 'a option =
  match (x,y) with
  | (None, None)         -> None
  | (None, _)            -> y
  | (_, None)            -> x
  | ((Some a), (Some b)) -> Some (max a b)
 
let rec maxi = function
  | Empty                 -> None
  | Node (left, x, right) -> maxo (Some x) (maxo (maxi left) (maxi right))
 
let rec toListi = function
  | Empty                 -> []
  | Node (left, x, right) -> (toListi left) @ (x :: (toListi right)) 
 
let rec toListp = function
  | Empty                 -> []
  | Node (left, x, right) -> x :: ( (toListp left) @ (toListp right) )
 
 
 
 
     
let rec fold f neutre = function
  | Empty                 -> neutre
  | Node (left, x, right) -> f (fold f neutre left) x (fold f neutre right)
 
 
let nbFeuilles2 = fold (fun g x d -> if (g = 0) && (d = 0) then 1 else g + d) 0
     
let nbNoeuds2 = fold (fun g x d -> 1 + g + d) 0
 
let hauteur2 = fold (fun g x d -> 1 + (max g d)) 0
 
let maxi2 = fold (fun g x d -> maxo (Some x) (maxo g d)) None
 
let toList2 = fold (fun g x d -> g @ (x :: d)) []
 
type 'a ntree =
  | ArbreVide
  | Noeud of 'a * ('a ntree list)
      
let ex = Noeud (1, [ArbreVide; Noeud (2, [ArbreVide; ArbreVide; ArbreVide]); ArbreVide])

Tags

courtesy of webmatter.de