Разделить список на два

Question

Я хотел бы реализовать функцию, которая принимает в качестве входных данных размер n и список. Эта функция вырезает список на два списка: один размер n и остальные в другом списке. Я новичок в этом языке и с трудом изучаю синтаксис.

Основная проблема, с которой я сталкиваюсь, это найти способ выражения размера списка без использования каких-либо циклов или изменяемых переменных.

Может ли кто-нибудь дать мне несколько указателей?

Answer 1

let split n list = 
    let rec not_a_loop xs = function 
    | (0, ys) | (_, ([] as ys)) -> (List.rev xs), ys 
    | (n, x::ys) -> not_a_loop (x::xs) (n-1, ys) 
    not_a_loop [] (n, list) 

Answer 2

Начнем с обозначения типа функции. Так как он получает n и список в качестве аргументов и возвращает пару списков, у вас есть функция split:

val split : int -> 'a list -> 'a list * 'a list 

Вот один подход к реализации этой функции:

let split n xs = 
    let rec splitUtil n xs acc = 
    match xs with 
    | [] -> List.rev acc, [] 
    | _ when n = 0 -> List.rev acc, xs 
    | x::xs' -> splitUtil (n-1) xs' (x::acc) 
    splitUtil n xs [] 

Идея с использованием аккумулятор acc, чтобы удерживать элементы, которые вы прошли и уменьшились n длинный путь. Поскольку элементы добавляются к acc, в конце вы должны отменить его, чтобы получить правильный порядок.

Функция имеет два базовых случая к прекращению:

• Там не осталось, чтобы пересечь элемент (xs = [] в этой точке).
• Вы прошли первые n элементов в списке (n уменьшено до 0 в это время).

Вот краткий пример того, как split вычисляет результат:

split 2 [1; 2; 3] // call the auxiliary function splitUtil 
~> splitUtil 2 [1; 2; 3] [] // match the 3rd case of x::xs' 
~> splitUtil 1 [2; 3] [1] // match the 3rd case of x::xs' 
~> splitUtil 0 [3] [2; 1] // match the 2nd case of n = 0 (base case) 
~> List.rev [2; 1], [3] // call List.rev on acc 
~> [1; 2], [3] 

Answer 3

Еще один способ, с помощью fold:

let biApply f (a, b) = (f a, f b) 

let splitAt n list = 
    let splitter ((xs, ys), n') c = 
    if n' < n then 
     ((c :: xs, ys), n' + 1) 
    else 
     ((xs, c :: ys), n' + 1) 
    List.fold splitter (([], []), 0) list 
    |> fst 
    |> biApply List.rev 

Here является большой серии на сгибах, чем вы можете следовать чтобы узнать больше на эту тему.

Answer 4

Новое решение - splitAt теперь встроено в список и массив. См. Фиксацию около 2014 года в github. Я заметил это сегодня, используя F # в VS.2015

Теперь вы можете просто сделать это ...

let splitList n list = 
    List.splitAt n list 

И как можно было бы ожидать, что подпись ...

n: int -> list: 'a list -> 'a list * 'a list 

Пример использование:

let (firstThree, remainder) = [1;2;3;4;5] |> (splitList 3) 
printfn "firstThree %A" firstThree 
printfn "remainder %A" remainder 

Выход:

firstThree [1; 2; 3] 
remainder [4; 5] 

Github для заинтересованных: https://github.com/dsyme/visualfsharp/commit/1fc647986f79d20f58978b3980e2da5a1e9b8a7d