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

### 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)
list

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


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.