Как сделать функцию, которая разбивает ленивый список на две части? - PullRequest
0 голосов
/ 25 ноября 2018

Мне нужно сделать функцию, которая разделяет ленивый список.Например, [5; 6; 3; 2; 1] -> [5; 3; 1] и [6; 2].Вот синтаксис обычных списков, но он должен быть ленивым.Функция разбита по индексу, нечетная по первому списку, четная по второму.Я пишу такую ​​функцию, но не знаю, как добавить в ленивый список новый элемент:

let rec merge list = 
let rec mergeHelp list acc = function
    | LNil -> failwith "Empty list"
    | LCons(x, xf) ->
        if (acc mod 2 == 0)
        then LCons(x, function() -> mergeHelp (acc+1) (xf())), LCons(LNil, function() -> LNil)
        else LCons(LNil, function() -> LNil), LCons(x, function() -> mergeHelp (acc+1) (xf()))
in mergeHelp list 0
;;

1 Ответ

0 голосов
/ 26 ноября 2018

Я не знаю, какой у вас тип списка ленивых, но я собираюсь предположить, что из вашего кода он выглядит так:

type 'a t = LNil | LCons of 'a * (unit -> 'a t)

Обратите внимание, что это отличается от более типичного списка ленивых, где (unit -> 'a t) будет 'a t lazy.

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

let rec pair = function 
  | LNil -> LNil
  | LCons (fst, rest) ->
    match rest () with
    | LNil -> LCons ((fst, None), const LNil)
    | LCons (snd, rest) ->
      let later_pairs = lazy (pair rest()) in
      LCons ((fst, Some snd), fun () -> Lazy.force later_pairs)

Эта функция имеет тип 'a t -> ('a * 'a option) t и ключевую особенность: после того, как вы отсканировали ее один раз, сканирование будет дешевым, поскольку вы не рекомендуетеэлементы вывода.Типы немного печальны, потому что на самом деле нам разрешено только None для второго элемента в последнем элементе результата, но давайте жить этим и продолжать.Для начала нам понадобятся тривиальные утилиты:

let rec map f = function
  | LNil -> LNil
  | LCons (a, r) -> LCons (f a, fun () -> map f (r ()))

let rec filter_map f = function
  | LNil -> LNil
  | LCons (x, r) ->
    let r () = filter_map f (r ()) in
    match f x with
    | None -> r ()
    | Some a -> LCons (a, r)

Они имеют типы ('a -> 'b) -> 'a t -> 'b t и ('a -> 'b option) -> 'a t -> 'b t и делают наименьшую глупость, которую можно было бы догадаться при чтении сигнатуры типа.Теперь мы можем реализовать функцию, которая делает то, что вы хотите:

let unmerge xs =
  let pairs = pair xs in
  (map (fun (a,_) -> a) pairs, filter_map (fun (_,b) -> b) pairs)
...