Разделить список на две части - PullRequest
Новая
       17

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

0 голосов
/ 02 февраля 2012

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

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

Кто-нибудь может дать мне несколько советов?

Ответы [ 4 ]

10 голосов
/ 02 февраля 2012

Давайте начнем с сигнатуры типа функции.Поскольку он получает 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]
8 голосов
/ 02 февраля 2012 
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)
1 голос
/ 01 сентября 2015

Новое решение - теперь splitAt встроен в List и Array.Смотрите коммит около 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

0 голосов
/ 04 февраля 2012

Еще один способ, используя 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

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

...