fusion de deux listes en F # récursive

Question

Je cherche à écrire une fonction récursive pour fusionner en entier listes F #

J'ai commencé avec cela, mais ne savez pas quoi faire.

let rec merge xs ys = 
    match xs with 
    | [] -> ys 
    | 

let li = [1;3;5;7;] 
let ll = [2;4;5;8;] 

Answer 1

Comme je l'ai dit dans mon commentaire, il est probablement plus facile si vous match de motif sur xs et ys simultanément:

let rec merge xs ys = 
    match xs,ys with 
    | [],l | l,[] -> l 
    | x::xs', y::ys' -> 
    if x < y then x :: (merge xs' ys) //' 
    else y :: (merge xs ys')   //' 

Answer 2

Vous avez déjà l'un des cas de base droite: Si xs est vide, juste retour ys.

De même, si ys est vide, renvoie xs.

Pour le cas où les deux xs et ys ne sont pas vides, vous devez regarder ce xs et les premiers éléments de YS (appelons-les x et y):

Si x est inférieur à y, qu'il doit être inséré avant y dans la liste finale. Donc, vous prenez y et ajoutez au résultat de la fusion de la queue de xs avec ys (y compris y).

Sinon, vous devez passer en premier. Donc préfixez y au résultat de la fusion de xs (y compris x) avec la queue de ys.

Answer 3

Ce n'est pas récursive, mais si les entrées ne sont pas classés:

let merge xs ys = (Seq.append xs ys) |> Seq.sort |> Seq.toList 

Answer 4

Je ne pense pas que ce soit un problème de récursivité

let a = [1;3;5] 
let b = [2;4;6] 

let c = Seq.append a b |> Seq.sort 

sortie de la session fsi: c:

val it : seq<int> = seq [1; 2; 3; 4; ...] 

Answer 5

J'ai trouvé un moyen qui pourrait convenir à ce que le demandeur voulait. Pour ma part, j'ai dû résoudre ce même problème et j'ai reçu à peine une semaine de leçons sur F # afin que toute la syntaxe ne soit pas discutée en classe et quand j'ai vu la réponse au-dessus de l'utilisation de plusieurs correspondants (match lst1, list2 with ...) instantanément, mais le professeur ne permettait pas son utilisation, donc j'ai dû trouver cette autre alternative. Même pensé que c'est fondamentalement le même algorithme, il utilise plus de code de base. Juste pensé que je devrais poster =)

let rec merge2 list1 list2 = 
    let head list = match list with | [] -> 0 | h::t -> h 
    let tail list = match list with | [] -> [] | h::t -> t 
    match list1 with 
    | [] -> [] 
    | h::t -> 
     //list2's head is 0 then list is empty then return whats in the first list 
     //(i.e no more values of second list to compare) 
     if head list2 = 0 then list1 
     elif h < head list2 then h :: merge2 t list2 
     else head list2 :: merge2 list1 (tail list2) 

Answer 6

J'utiliseraient List.fold pour ce faire:

let merge a b = 
    List.fold (fun acc x -> 
     if List.exists ((=)x) acc = false then 
      elem :: acc 
     else 
      acc 
    ) (List.sort a) b 

Cela peut ne pas être le meilleur moyen de le faire, cependant.