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

Я ищу, чтобы объединить 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)
Источник

4 ответа

Решение

Ваша функция почти правильная. 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]
Источник

Одним из важных моментов является то, что функция не является правильной. Сбой при вводе ([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'

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

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
Источник

Начиная с F# 4.5 (я думаю), предполагая, что вы хотите продолжать получать элементы из более длинной последовательности, когда короткая исчерпана, вы можете просто сделать:

let interleave = Seq.transpose >> Seq.concat >> Seq.toList

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

> interleave [ [1;2;3]; [4;5]; [6;7;8;9] ];; // also works for any number of lists
val it : int list = [1; 4; 6; 2; 5; 7; 3; 8; 9]

(Заметка List.transpose броски, если последовательности имеют разную длину, но Seq.transpose нет, поэтому вам нужно использовать последний.)

Источник

Вы можете использовать эту возможность, чтобы определить более общую функцию более высокого порядка - 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

Редактировать:

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

let interleave xs ys = List.map2 (fun a b -> [a; b]) xs ys |> List.concat
Источник

Из 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]
Источник

Добавлю еще одну вариацию в смесь. Это обрабатывает списки разной длины, просто добавляя остаток от более длинного списка в конце.

let rec interleave lst1 lst2 = [
    match lst1 with
    | lst1H :: lst1T ->
        yield lst1H
        yield! interleave lst2 lst1T
    | [] -> yield! lst2
]

Как это работает:

Предполагая, что у нас есть let a = [1;2;3]; let b = [4;5;6] и позвони interleave a b.

  • Мы сопоставляем первую ветку, потому что левый список не пустой.
  • Отдаем голову первого списка (1).
  • Затем мы рекурсивно переходим к функции со вторым списком и хвостом первого списка. Обратите внимание, что порядок параметров был изменен.

На этом промежуточном этапе у нас есть два списка: остаток от первого. [2;3] и второй [4;5;6]. Поскольку мы поменяли порядок аргументов, теперь мы сосредотачиваемся на втором списке.

  • Список не пустой, поэтому мы сопоставляем его по первой ветви.
  • Отдаем голову списка (4).
  • Затем мы снова выполняем рекурсию, еще раз переключая параметры.

Списки на данный момент [2;3] а также [5;6] в то время как вывод содержит [1;4].

Этот процесс повторяется до тех пор, пока управляемый список не станет пустым, что соответствует второй ветви, давая остаток от другого списка.

Источник
Другие вопросы по тегам