Re: Zipping two sequences together with only cons, empty, foldr

[Valery Trifonov]

Kevin Atkinson wrote:
> 
> Laszlo Nemeth wrote:
[snip]
> > foldr (\ a g ys -> case ys of
> >                     []     -> empty
> >                     (b:bs) -> (a,b) `cons` g bs)
> >       (\ _ -> [])
> 
> But only for lists.  As you are patern matching on ":".

Apply the old "predecessor" trick to get the tail of a list using foldr.

foldr
  (\ a g -> fst . foldr (\ b (_,bs) -> ((a,b) : g bs, b:bs)) ([],[]))
  (const [])

Complexity was not in the specs. For better ideas on how to zip see [1].

Cheers,
Valery

[1] Leonidas Fegaras, Tim Sheard, Tong Zhou. Improving Programs which
Recurse over Multiple Inductive Structures. In Proc. PEPM'94; also
available from Fegaras' page.