How to make function that split lazy list into two?

Question

I need to make function that split lazy list. For example, [5;6;3;2;1] -> [5;3;1] and [6;2]. Here is syntax of regular lists, but it have to be lazy. Function split by index, odd to first list, even to second. I write function like this, but I don`t know how to add to lazy list new element:

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
;;

Maybe start by thinking about the slightly simpler problem: how do you implement List.filter for lazy lists? I.e., write a function that takes a predicate (function returning bool) and a lazy list, and returns a new lazy list containing just the elements for which the predicate is true. The hint is that you don't need to add any elements to any lists to make this work. It's just a filtering operation. — Jeffrey Scofield

Dan Robertson Dan Robertson · Accepted Answer · 2018-11-25T22:36:12

I don’t know what your lazy list type is but I’m going to assume from your code it looks like:

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

Note that this is different from a more typical lazy list where (unit -> 'a t) would be 'a t lazy.

Chances are that the two lists won’t be consumed in the same way they are generated and we won’t want to scan through the input running all the functions once for the odds and again for the evens. So let’s write a function to pair up elements:

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)

This function has type 'a t -> ('a * 'a option) t and the key feature that once you have scanned it once, it is cheap to scan again as you do not recommits the elements of the output. The types are a little bit sad because really we are only allowed None for the second element in the last element of the result but let us live with that and carry on. First we need some trivial utilities:

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)

These have types ('a -> 'b) -> 'a t -> 'b t and ('a -> 'b option) -> 'a t -> 'b t and do the least stupid thing one would guess from reading the type signature. We can now implement the function that does what you want:

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

How to make function that split lazy list into two?

1 Answers