Я не знаю, какой у вас тип списка ленивых, но я собираюсь предположить, что из вашего кода он выглядит так:
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)