let ( @@ ) f g x = f (g x);;
type lettre = {l:char; f:int;};;
type huff = Feuille of lettre | Branche of huff * huff;;
type huffL = huff list;;
type binarySeg = bool list;;
let rec count = function
| Feuille l -> l.f
| Branche (h1, h2) -> count h1 + count h2;;
let rec getFC = function
| Feuille l -> l.l
| Branche (h1, h2) -> getFC h1;;
let cmp f h1 h2 =((f h1) < (f h2));;
let insert cmp huff huffL=
let rec insert acc = function
| [] -> List.rev (huff::acc)
| hd::lt -> if cmp huff hd
    then List.rev_append acc (huff::hd::lt)
    else insert (hd::acc) lt
in insert [] huffL;;
let string2huffL cmp str =
    let strget=String.get str
    in let rec f acc = function n -> if n = -1 then acc
    else f (insert cmp (Feuille({l=strget n;f=1})) acc) (n-1)
    in f [] ((String.length str)-1);;
let grouper fa fb = match (fa, fb) with
    | (Feuille la, Feuille lb) ->
        (if la.l = lb.l then Feuille ({l=la.l;f=la.f + lb.f})
        else Branche (fa, fb))
    | _ -> Branche (fa, fb);;
let grouperL cmp grouper2 liste=
let rec f acc = function
| [] -> acc
| hd1::hd2::lt ->
    if (getFC hd1) = (getFC hd2)
    then f acc ((grouper2 hd1 hd2)::lt)
    else f (insert cmp hd1 acc) (hd2::lt)
| hd1::[] -> insert cmp hd1 acc
in f [] liste;;
let rec grouperA cmp = function
| hd::[] -> hd
| hd1::hd2::lt -> grouperA cmp ( insert cmp (grouper hd1 hd2) lt)
| _ -> failwith "?? grouperA ??";;
let getArbreForString chaine =
    grouperA (cmp count) (grouperL (cmp count) grouper
    (string2huffL (cmp (int_of_char @@ getFC)) chaine)) ;;
let getBinarySeq arbre c =
    let rec f = function
    | Branche (ba, bb) ->
        let (boola, seq)= f ba in
        if boola
            then (boola, true::seq)
            else
                let (boolb, seq)= f bb
                in (boolb, false::seq)
    | Feuille (fa) -> (fa.l=c, [])
    in f arbre;;