Home » forums » LtU Forum

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;[]])]

By Denis Bredelet -jido at 2008-04-22 11:25 | LtU Forum | previous forum topic | next forum topic | other blogs | 5965 reads

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".

By fadrian at Tue, 2008-04-22 14:59 | login or register to post comments

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)

By neelk at Tue, 2008-04-22 16:07 | login or register to post comments

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.

By Denis Bredelet -jido at Tue, 2008-04-22 18:37 | login or register to post comments