Объединить два списка

Question

Я ищу, чтобы объединить 2 списка в F # в чисто функциональном виде. Мне сложно понять синтаксис.

Пусть у меня есть кортеж ([5;3;8],[2;9;4])

Когда я вызываю функцию, она должна возвращать [5;2;3;9;8;4]

Вот почему я до сих пор, что это неправильно, я уверен. Если бы кто-то мог объяснить это простым способом, я был бы благодарен.

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

Answer 1

Ваша функция почти право. let f = function является сокращением для let f x = match x with, поэтому вам не нужны явные аргументы. Кроме того, ваш алгоритм нуждается в некоторой настройке.

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

Один важный момент в том, что функция не является правильным. Он не работает с входом ([1;2;3], []), так как вы пропустили случай (xs, []) в соответствии с шаблоном. Более того, аргументы лучше в карри, чтобы их было проще использовать с частичным приложением. Вот исправленная версия:

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

Вы можете видеть, что функция не хвостовой рекурсией, поскольку он применяется Cons (::) конструктор дважды после того, как вернулся рекурсивный вызов. Один интересный способ сделать его хвостовой рекурсией использует выражение последовательности:

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

Вы можете использовать эту возможность, чтобы определить более общую функцию высшего порядка - zipWith, а затем реализовать interleave его использования.

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 

Edit:

Как сказано ниже @pad, F # уже zipWith под названием List.map2. Таким образом, вы можете переписать interleave следующим образом:

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

Answer 4

С OP это не ясно, что должно произойти, если эти списки имеют разную длину, но вот общая, хвост рекурсивной реализации, которая полностью уничтожает оба списка:

// '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 

Примеры:

> 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]