Drzewa binarne w OCAMLu

Nie wiem czy ktos tu zajmuje sie tak wymyslnym jezykiem jak OCAML (albo
w ogole czyms funkcyjnym), ale zaryzykuje.

Polimorficzne drzewa binarne są zdefiniowane następująco:
type 'a binTree = Node of 'a binTree * 'a * 'a binTree | Empty;;

Napisz funkcję getSubTrees: 'a binTree -int -('a binTree) list ,
która dla zadanego drzewa binarnego zwróci listę wszystkich poddrzew o
wysokości x.

Moim problemem nie jest nieumiejetnosc wklepania tego czy wymyslenia
algorytmu, lecz po prostu nie rozumiem tresci zadania, nie wiem co mam
otrzymac?!
Jesli ktos umie wyklepac ta funkcyjke to bylbym wdzieczny, a jesli nie
to chociaz jakies propozycje co powinienem otrzymac gdy dla takiego drzewa:

let tt = Node (Node (Empty, 1, Empty), 2, Node (Empty, 3, Node (Empty,
4, Empty)));;

Wywolam funkcje na takie 2 sposoby:
getSubTrees tt 1;;   i   getSubTrees tt 2;;

Dzieki. I przy okazji wesolych Swiat Wielkanocnych, duzo zdrowia przede
wszystkim, bo ja wlasnie sie rozchorowalem :/

Witam.

Polimorficzne drzewa binarne są zdefiniowane następująco:
type 'a binTree = Node of 'a binTree * 'a * 'a binTree | Empty;;

Napisz funkcję getSubTrees: 'a binTree -int -('a binTree) list ,
która dla zadanego drzewa binarnego zwróci listę wszystkich poddrzew o
wysokości x.

Moim problemem nie jest nieumiejetnosc wklepania tego czy wymyslenia
algorytmu, lecz po prostu nie rozumiem tresci zadania, nie wiem co mam
otrzymac?!
Jesli ktos umie wyklepac ta funkcyjke to bylbym wdzieczny, a jesli nie
to chociaz jakies propozycje co powinienem otrzymac gdy dla takiego

Masz dostać funkcję postaci:

getSubTrees: 'a binTree -int -'a binTree list

Elementami ostatecznej listy mają być drzewa. Każde z tych drzew ma być
poddrzewem drzewa wyjściowego. Każde z tych drzew ma mieć wysokość
równą drugiemu argumentowi. Zauważ, że mówiąc drzewo mamy na myśli
w tym przypadku albo Liść (Empty) albo trójkę postaci
(lewe poddrzewo, wartość, prawe poddrzewo).

Funkcja, która zwróci listę wszystkich poddrzew może wyglądać na przykład
tak (nie sprawdzałem czy działa).

let wszystkie drzewo =
    let rec pom drzewo lista = match drzewo with
    | Empty -Empty::lista
    | Node of (lewe,_,prawe) as korzen -
        korzen::(wszystkie lewe)::(wszystkie prawe)::lista
in pom drzewo [] ;;

pozdrawiam
Maciek

let wszystkie drzewo =
    let rec pom drzewo lista = match drzewo with
    | Empty -Empty::lista
    | Node of (lewe,_,prawe) as korzen -
        korzen::(wszystkie lewe)::(wszystkie prawe)::lista
in pom drzewo [] ;;

    | Node of (lewe,_,prawe) as korzen -
     korzen::(wszystkie lewe lista)::(wszystkie prawe lista)::lista

pozdrawiam, WŚ!
Maciek

| let wszystkie drzewo =
|    let rec pom drzewo lista = match drzewo with
|    | Empty -Empty::lista
|    | Node of (lewe,_,prawe) as korzen -
|        korzen::(wszystkie lewe)::(wszystkie prawe)::lista
| in pom drzewo [] ;;

Powinno byc

    | Node of (lewe,_,prawe) as korzen -
     korzen::(wszystkie lewe lista)::(wszystkie prawe lista)::lista

Doszedlem do takiego kodu:

let wszystkie t =
     let rec pom = function
     | (Empty, lista) -Empty :: lista
     | (Node(l, w, p), lista) -
          Node(l, w, p) :: pom (l, lista) :: pom (p, lista) :: lista
   in pom (t, []);;

Wydawac by sie moglo, ze wszystko jest w porzadku, a ocaml rzuca takim
bledem:

Characters 133-147:
       | (Node(l, w, p), lista) -Node(l, w, p) :: pom (l, lista) ::
pom (p, lista) :: lista
                                                    ^^^^^^^^^^^^^^
This expression has type 'a binTree list but is here used with type
   'a binTree

Nie bardzo rozumiem dlaczego, poniewaz podkreslone "pom (l, lista)"
zwraca faktycznie liste, a operator "::" jednak sie czepia :(

Co jak co, z ocamlem zawsze mialem problemy, ale tym razem juz po prostu
rece mi opadaja :/

          Node(l, w, p) :: pom (l, lista) :: pom (p, lista) :: lista
   in pom (t, []);;

Sklejanie dwóch list ma kosz O(długość_lewej). Żeby całość była
efektywniejsza, można by przekazywać "akumulator", do którego zostanie

można pominąć...

Operator :: dokłada jeden element na początek listy, jego typ to
   'a -'a list -'a list

Sklejanie dwóch list ma kosz O(długość_lewej). Żeby całość była
efektywniejsza, można by przekazywać "akumulator", do którego zostanie

można pominąć...

raczej, ze nie potrafie poradzic sobie w tym konkretnym przypadku.
Nie wiem dlaczego :/

| Sklejanie dwóch list ma kosz O(długość_lewej). Żeby całość była
| efektywniejsza, można by przekazywać "akumulator", do którego zostanie

| można pominąć...

O rekursji ogonowej tez wiem :)

Sztuczka polega na tym, że funkcja - zamiast zwracać listę - dokleja
ją na początek dodatkowego parametru. Dzięku temu jeśli rekurencyjne
wywołanie chce dokleić coś z prawej strony wyniku, to zamiast

listę do doklejenia jako dodatkowy parametr.

Node(l, w, p) jest jednym węzłem, pom zwraca listę węzłów, więc zamiast
   Node(l, w, p) :: pom (l, lista) :: pom (p, lista) :: lista
powinno być

Zadanie ostatecznie udalo mi sie rozwiazac i w celach edukacyjnych
wklejam tutaj tresc (moze sie komus przyda). Nie jest to zapewne
najoptymalniesze rozwiazanie, ale dziala poprawnie.

let rec wys (t, acc) =
   match t with
   | Empty -acc-1
   | Node(l, v, r) -
     let wl = wys(l, acc+1) and wr = wys(r, acc+1) in
     if wl wr then wl else wr;;

let getSubTrees t n =
     let rec get (t, n, acc) =
     match t with
     | Empty -acc
     | Node(l, v, r) -
       if wys(t, 0) = n then Node(l, v, r) :: acc

   in get(t, n, []);;