Pomoc z kodem F Sharp

0

Witam,
potrzebuje pomocy w analizie kodu napisanego w F Sharp. Mam dwa krótkie programy do wyświetlania wszystkich permutacji i wszystkich kombinacji zbioru (w tym konkretnym przypadku tablicy). Jednak za bardzo nie znam składni tego języka. Czy mógł by ktoś wytłumaczyć po kolei co która funkcja robi, albo przepisać te programy w psedokodzie, tłumacząc jakie funkcje w f sharp za co odpowiadają i w jaki sposób działają?
Z góry dziękuje.

////////////////////////////////////////////////// PERMUTACJE
let permute xs =
  let insert e xs =
    List.fold (fun (a,l) x -> (e::x::l)::List.map (fun ys -> x::ys) a,x::l) ( [ [ e ] ] , [ ] ) xs |> fst
   
  let rec _p xs sofar =
    match xs with
    | [] -> sofar
    | h::t -> 
      _p t (List.fold (fun a x -> List.fold (fun s x -> x::s) a (insert h x)) sofar sofar)
  _p xs [[]] |> List.sort |> List.tail

////////////////////////////////////////////////// KOMBINACJE

let combine xs =
  let rec _p xs sofar =
    match xs with
    | [] -> sofar
    | h::t -> 
      _p t (List.fold (fun a x -> (h::x)::a) sofar sofar)
  _p xs [[]] |> List.rev |> List.tail 
0

Kolorowanie składni... - wrzucam twój kod z odpowiednimi kolorami:

////////////////////////////////////////////////// PERMUTACJE
let permute xs =
  let insert e xs =
    List.fold (fun (a,l) x -> (e::x::l)::List.map (fun ys -> x::ys) a,x::l) ( [ [ e ] ] , [ ] ) xs |> fst
 
  let rec _p xs sofar =
    match xs with
    | [] -> sofar
    | h::t -> 
      _p t (List.fold (fun a x -> List.fold (fun s x -> x::s) a (insert h x)) sofar sofar)
  _p xs [[]] |> List.sort |> List.tail
 
////////////////////////////////////////////////// KOMBINACJE
 
let combine xs =
  let rec _p xs sofar =
    match xs with
    | [] -> sofar
    | h::t -> 
      _p t (List.fold (fun a x -> (h::x)::a) sofar sofar)
  _p xs [[]] |> List.rev |> List.tail 

Do korzystania przy odpowiadaniu (łatwiej patrzeć na porządnie wyglądający kod).

0

Cóż wytłumaczenie tego może nie być proste. W sumie też w F# nie piszę, ale w innych językach funkcyjnych owszem.

Combine:

No więc definiowana jest lokalnie w tej funkcji funkcja pomocnicza _p (ale nazwa...). Następnie wszystko do robi funkcja combine można zapisać C-podobnie jako

combine(list)
{
    return tail( reverse( _p(list, [[]]) ) ); // notacja [] służy do tworzenia list, np. [1, 2, 3]. [[]] to lista list zawierająca jedną listę.
}

Teraz ta magiczna funkcja _p:

_p(list, soFar)
{
    if (list == []) { return soFar; }
    else
    {
        head = list[0];
        tail = list.tail();
        _p(tail, soFar.appendToEveryElement(head) + soFar); // tutaj by map było odpowiedniejsze, ale widać ktoś lubi foldy...
    }
}

Jako że jest północ, chwilowo nie mam siły przedzierać się przez składnię F# i analizować dziwnie napisaną funkcję permute.
Ale wrzucę wersję w Haskellu (ok, nieoptymalizowane) dla porównania (kombinacje można jeszcze krócej):

permutation [] = [[]]
permutation xs = [x:ys | x <- xs, ys <- permutation (delete x xs)]

1 użytkowników online, w tym zalogowanych: 0, gości: 1