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

[Lennart Augustsson]

Kevin Atkinson wrote:

> Ok you haskell experts.  I have an interesting challenge (or maybe just
> a question if you have seen it before).
>
> Is it possible to zip two sequences together with just:
>
> cons   :: a -> c a -> c a
> empty  :: c
> foldr  :: (a -> b -> b) -> b -> c a -> b
>
> And if so how would one do so.
>
> Remember you may ONLY use the three functions given above and NOTHING
> else.  Creating a list with "foldr (:) []" is also not allowed.

With only that you definitely cannot do it since zip involes pairs.  Assuming that
you allow pairs and lambda expressions you can do it like this:

caseList xs n c =
    fst (foldr (\ x (_, xs) -> (\ n c -> c x xs, x `cons` xs))
               (\ n c -> n, empty) xs) n c

zip =
  foldr (\ a g ys -> caseList ys empty ( \ b bs ->(a,b) `cons` g bs))
        (\ _ -> empty)

    -- Lennart