Question about typing

[Matt Harden]

In a lazy language like Haskell, a list is essentially the same as a
lazy stream, though I'm not well versed in the parallel stuff...

Anyway, it can be quite desirable to be able to "zip" together data
structures other than lists; trees or arrays for example.  The standard
prelude and library does not include any class to do this.  I played
with this awhile back, and came up with the following:

   module Zip where
   import Prelude hiding (zip, zipWith, zipWith3, zip3)

   class (Functor f) => ZipFunctor f where
      -- "zap" stands for "zip apply"
      -- it applies a set of functions to a set
      -- of arguments, producing a set of results
      zap :: f (a->b) -> f a -> f b

   instance ZipFunctor [] where
      (f:fs) `zap` (x:xs) = f x : fs `zap` xs
      _ `zap` _ = []

   instance ZipFunctor Maybe where
      (Just f) `zap` (Just x) = Just (f x)
      _ `zap` _ = Nothing

   zipWith  :: (ZipFunctor f) => (a->b->c) -> f a -> f b -> f c
   zipWith  f xs ys = f `fmap` xs `zap` ys

   zipWith3 :: (ZipFunctor f) => (a->b->c->d)->f a->f b->f c->f d
   zipWith3 f xs ys zs = f `fmap` xs `zap` ys `zap` zs

   zip  :: ZipFunctor f => f a -> f b -> f (a,b)
   zip  = zipWith  (,)
   zip3 :: ZipFunctor f => f a -> f b -> f c -> f (a,b,c)
   zip3 = zipWith3 (,,)

One can easily create ZipFunctor instances for trees and other data
structures.  I can provide examples if you like.  With multiple
parameter type classes (MPTCs, they are not in Haskell 98) as well as
functional dependencies (also not in h98), one can also create a
"Zippable" class to generalize the zip function over multiple tuple
types and eliminate zip3, zip4, etc.

I don't know of any way to make option 1 below equivalent to the other
two; I think it is impossible with Haskell's current type systems. 
However, you can create an "Id" type, which is a wrapper that holds
exactly one instance of another type.  Id happens to trivially be a
Functor and a Monad, is also trivially a ZipFunctor, and can be defined
as a newtype to eliminate overhead in the compiled program.  Then you
would have option 1 as follows:
   1. Adding two integers together: Id Int -> Id Int -> Id Int
The function for all three options would then be (zipWith (+)).

Hope this helps,
Matt


andrew@andrewcooke.free-online.co.uk wrote:
> 
> Is there a class that both lists and lazy streams could implement, so
> that zip et al could be more general?  The distinction between 2 and 3
> below seems a bit arbitrary.  Something like fmap/Functor?  (If there
> is, I guess it could apply to 1 too?; if not, why not - is it
> impractical (efficiency?) or just wrong?)
> 
> Curious,
> Andrew
> 
> On Thu, Apr 05, 2001 at 06:19:30PM +0100, Toby Watson wrote:
> > Intuitively the following scenarios seem to be related, can anyone point my
> > in the direction of formal work on this, or give me the formal terms I need
> > to search around?
> >
> > 1. Adding two integers together: Int -> Int -> Int
> >
> > 2. Adding two lists of Integers together: [Int] -> [Int] -> [Int]
> >
> > 3. Adding two lazy streams of integers together, possibly in seperate
> > (parallel) processes for example.
> >
> >
> > cheers,
> > Toby
> >
> >
> > _______________________________________________
> > Haskell-Cafe mailing list
> > Haskell-Cafe@haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> >
> 
> --
> http://www.andrewcooke.free-online.co.uk/index.html
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe