Un-filter (or merge) lists

What is the standard functional construct which is the converse of filter?

Eg. if I want to add 0 between all elements of a list?

Or if I want to merge two sorted lists preserving sorting?

I am thinking of a "unfilter" construct which takes a list of lists, and a list of functions applied in turn

(*insert 0 between two elements of the list*)
unfilter [a] [fun x::xs -> (x, [xs]); fun as -> (0, [as])]

(*merge two sorted lists*)
unfilter [a;b] [fun as, bs -> match as, bs with
   | x::xs, y::ys => if y < x then (y, [as;ys]) else (x, [xs;bs])
   | [], y::ys => (y, [[];ys])
   | x::xs, [] => (x, [xs;[]])]

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Well of course...

... it must be a "retlif".

A filter is a kind of fold.

A filter is a kind of fold. So is your interleaving 0 function:

let rec fold f list = 
  match list with
  | [] -> f None
  | x :: xs -> f (Some(x, fold f xs))

let filter p list = 
  fold (function None -> []
               | Some(x, xs) -> if p x then x :: xs else xs)

let interleave0 list = 
  fold (function None -> []
               | Some(x, xs) -> x :: 0 :: xs)

Merging two sorted lists is an unfold:

let unfold f seed = 
  match f seed with
  | None -> []
  | Some(x, seed') -> x :: (unfold f seed')

let merge (<) xs ys = 
  unfold (function ([], []) -> None
                 | (x :: xs, y :: ys) when x < y -> Some(x, (xs, y :: ys))
                 | (x :: xs, y :: ys) -> Some(y, (x :: xs, ys))
                 | ([], y :: ys) -> Some(y, ([], ys))
                 | (x :: xs, []) -> Some(x, (xs, [])))
          (xs, ys)

Interesting. It did not occur to me

Interesting. It did not occur to me to use unfold that way. I guess that I have my "unfilter" function then, since filter is fold unfilter is unfold.