Wydobywanie liści ścieżki n-ary drzewa w F #

Question

Zainspirowany this question, chciałem spróbować swoich sił w najnowszej ponder this challenge za pomocą F #

Moje podejście jest chyba całkowicie z kursu, ale w trakcie rozwiązywania tego problemu , Próbuję uzyskać listę wszystkich permutacji cyfr 0-9.

Czekam na rozwiązanie go za pomocą drzewa n-ary tak:

type Node = 
    | Branch of (int * Node list) 
    | Leaf of int 

jestem bardzo z siebie zadowolony, bo udało mi się wypracować jak wygenerować drzewo że chcieć.

Mój problem polega na tym, że nie mogę zrozumieć, jak przejść przez to drzewo i wyodrębnić "ścieżkę" do każdego liścia jako int. Rzeczą, która mnie myli, jest to, że muszę dopasowywać poszczególne węzły, ale moja "zewnętrzna" funkcja musi przyjąć listę węzłów.

Moja obecna próba prawie robi słusznie, z wyjątkiem tego, że zwraca mi sumę wszystkich ścieżkach ...

let test = Branch(3, [Branch(2, [Leaf(1)]);Branch(1, [Leaf(2)])]) 

let rec visitor lst acc = 
    let inner n = 
     match n with 
     | Leaf(h) -> acc * 10 + h 
     | Branch(h, t) -> visitor t (acc * 10 + h) 
    List.map inner lst |> List.sum 

visitor [test] 0 //-> gives 633 (which is 321 + 312) 

I nie jestem nawet pewien, że jest to ogon rekurencyjnej.

(Jesteś bardzo mile widziane, aby zaproponować inne rozwiązanie dla znalezienia permutacji, ale ja nadal jestem zainteresowany rozwiązanie tego konkretnego problemu)

EDIT: Mam napisali algorytmu permutacji rodzajowe w F # here.

Answer 1

dotyczące twojego pytania o przechodzenie do listy - możesz zacząć od napisania funkcji, która zwraca listy reprezentujące ścieżkę - to myślę, że jest łatwiej i później łatwo będzie przekształcić ją w funkcję zwracającą liczbę.

Ten pobiera listę jako pierwszy argument (dotychczasowa ścieżka) i drzewo i zwraca listę> typ - to wszystkie możliwe ścieżki z bieżącej gałęzi.

let rec visitor lst tree = 
    match tree with 
    | Branch(n, sub) -> List.collect (visitor (n::lst)) sub 
    | Leaf(n) -> [List.rev (n::lst)] 

// For example... 
> let tr = Branch(1, [Leaf(3); Branch(2, [Leaf(4); Leaf(5)])]);; 
> visitor [] tr;; 
val it : int list list = [[1; 3]; [1; 2; 4]; [1; 2; 5]] 

W przypadku „listków”, po prostu dodać aktualny numer na liście i zwraca wynik w postaci listy zawierającej jedną listę (musimy odwrócić ją pierwszy, bo byliśmy dodawanie numerów do początku) . W przypadku "Oddziału" dodajemy "n" do listy i wywołuje rekursywnie gościa, aby przetworzyć wszystkie podnagody w bieżącym oddziale. Zwraca to kilka list i używamy "map_concat", aby przekształcić je w pojedynczą listę zawierającą wszystkie posble ścieżki z bieżącej gałęzi.

Teraz można przepisać to, aby powrócić do listy liczb całkowitych:

let rec visitor2 lst tree = 
    match tree with 
    | Branch(n, sub) -> List.collect (visitor2 (lst * 10 + n)) sub 
    | Leaf(n) -> [lst * 10 + n] 

// For example... 
> visitor2 0 tr;; 
val it : int list = [13; 124; 125] 

Zamiast łączenie list, możemy teraz obliczyć liczbę.

Answer 2

Odnośnie lenistwa - Możesz zrobić to leniwym przy użyciu typu F # "seq" zamiast "listy". Oto przykład:

let rec visitor2 lst tree = 
    match tree with 
    | Branch(n, sub) -> Seq.map_concat (visitor2 (lst * 10 + n)) sub 
    | Leaf(n) -> 
     seq { do printfn "--yielding: %d" (lst * 10 + n) 
      yield lst * 10 + n };; 

Rzecz "seq" to wyrażenie sekwencji, które reprezentuje leniwy strumień wartości.I dodał: „printfn” do kodu, dzięki czemu możemy śledzić, jak rzeczy realizują:

> visitor2 0 tr |> Seq.take 2;; 
--yielding: 13 
--yielding: 124 
val it : seq<int> = seq [13; 124] 

Prawdopodobnie można użyć czegoś podobnego Seq.first znaleźć pierwszą wartość, która reprezentuje wynik.