Fusionar dos listas

Question

Estoy buscando fusionar 2 listas en F # de una manera puramente funcional. Me está costando entender la sintaxis.

Let decir que tengo una tupla ([5;3;8],[2;9;4])

Cuando llamo a la función, se debe volver [5;2;3;9;8;4]

Aquí es por eso que tengo hasta ahora, lo que está mal, estoy seguro. Si alguien pudiera explicarlo de una manera simple, estaría agradecido.

let rec interleave (xs,ys) = function 
|([], ys) -> ys 
|(x::xs, y::ys) -> x :: y:: interleave (xs,ys) 

Answer 1

Su función es casi derecha. let f = function es la abreviatura de let f x = match x with por lo que no necesita argumentos explícitos. Además, su algoritmo necesita algunos ajustes.

let rec interleave = function //same as: let rec interleave (xs, ys) = match xs, ys with 
    |([], ys) -> ys 
    |(xs, []) -> xs 
    |(x::xs, y::ys) -> x :: y :: interleave (xs,ys) 

interleave ([5;3;8],[2;9;4]) //output: [5; 2; 3; 9; 8; 4] 

Answer 2

Un punto importante es que la función no es correcta. Falla con la entrada ([1;2;3], []) ya que se olvidó de la caja de (xs, []) en la coincidencia de patrones. Además, los argumentos son mejores en la forma al curry para que sea más fácil de usar con la aplicación parcial. Aquí está la versión corregida:

let rec interleave xs ys = 
    match xs, ys with 
    | [], ys -> ys 
    | xs, [] -> xs 
    | x::xs', y::ys' -> x::y::interleave xs' ys' 

Se puede ver que la función es no recursiva de cola ya que se aplica contras (::) constructor de dos veces después de la llamada recursiva regresó. Una forma interesante de hacer que recursiva de cola está utilizando la expresión secuencia:

let interleave xs ys = 
    let rec loop xs ys = 
     seq { 
      match xs, ys with 
      | [], ys -> yield! ys 
      | xs, [] -> yield! xs 
      | x::xs', y::ys' -> 
        yield x 
        yield y 
        yield! loop xs' ys' 
      } 
    loop xs ys |> List.ofSeq 

Answer 3

Se puede utilizar esta oportunidad para definir una función de orden superior más general - zipWith, y luego poner en práctica interleave usarlo.

let rec zipWith f xlist ylist = 
    match f, xlist, ylist with 
    | f, (x :: xs), (y :: ys) -> f x y :: zipWith f xs ys 
    | _, _, _ -> [] 

let interleave xs ys = zipWith (fun a b -> [a; b]) xs ys |> List.concat 

Editar:

Como @pad dijo a continuación, F # ya tiene zipWith bajo el nombre List.map2. Por lo que puede volver a escribir interleave de la siguiente manera:

let interleave xs ys = List.map2 (fun a b -> [a; b]) xs ys |> List.concat 

Answer 4

Desde el PO no está claro lo que debería suceder si las listas tienen longitudes diferentes, pero aquí hay una implementación genérica, recursiva de cola que consume totalmente ambas listas:

// 'a list -> 'a list -> 'a list 
let interleave xs ys = 
    let rec imp xs ys acc = 
     match xs, ys with 
     | [], [] -> acc 
     | x::xs, [] -> imp xs [] (x::acc) 
     | [], y::ys -> imp [] ys (y::acc) 
     | x::xs, y::ys -> imp xs ys (y::x::acc) 
    imp xs ys [] |> List.rev 

Ejemplos:

> interleave [5;3;8] [2;9;4];; 
val it : int list = [5; 2; 3; 9; 8; 4] 
> interleave [] [1..3];; 
val it : int list = [1; 2; 3] 
> interleave [1..3] [42];; 
val it : int list = [1; 42; 2; 3] 
> interleave [1..3] [42;1337];; 
val it : int list = [1; 42; 2; 1337; 3] 
> interleave [42; 1337] [1..3];; 
val it : int list = [42; 1; 1337; 2; 3]