CODEWITHSUNDEEP
functionfunctional-programmingocaml
Ilya
Ilya

Reputation: 59

How to make function that split lazy list into two?

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

Upvotes: 0

Views: 360

Answers (1)

Dan Robertson
Dan Robertson

Reputation: 4360

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)

Upvotes: 2

Related Questions