[Haskell-cafe] varargs zip

Dan Doel dan.doel at gmail.com
Fri Nov 21 17:23:17 EST 2008


On Friday 21 November 2008 9:40:14 am Jason Dusek wrote:
>   It came up on IRC last night that there is no "generic" zip in
>   Haskell. I decided to write one as an example, but it only
>   half works.
>
>   When the argument lists are all definitely of one type,
>   instance selection works as expected; however, with numeric
>   types, for example, things don't work out. I'm not sure how to
>   express the idea that the result tuple determines the
>   arguments types, with either of functional dependencies or
>   associated types.

Here's some fancy type system stuff for your viewing pleasure:

---- snip ----

{-# LANGUAGE
    GADTs
  , TypeFamilies
  , EmptyDataDecls
  , TypeOperators
  , ScopedTypeVariables
  , FlexibleContexts
  #-}

data Nil
data a ::: b

infixr :::

data Tuple ts where
  Nil   :: Tuple Nil
  (:::) :: t -> Tuple ts -> Tuple (t ::: ts)

type family Fun ts r :: *
type instance Fun Nil r = r
type instance Fun (t ::: ts) r = t -> Fun ts r

type family Lists ts :: *
type instance Lists Nil = Nil
type instance Lists (t ::: ts) = [t] ::: Lists ts

class Tup ts where
  uncurryT :: Fun ts r -> Tuple ts -> r
  curryT   :: (Tuple ts -> r) -> Fun ts r
  zipT :: Tuple (Lists ts) -> [Tuple ts]

instance Tup Nil where
  uncurryT r Nil = r
  curryT f = f Nil
  zipT Nil = repeat Nil

instance Tup ts => Tup (t ::: ts) where
  uncurryT f (v ::: vs) = uncurryT (f v) vs
  curryT f = \v -> curryT (\t -> f (v ::: t))
  zipT (l ::: ls) = zipWith (:::) l (zipT ls)

zipWithT :: forall ts r. (Tup ts, Tup (Lists ts)) => 
            ts -> Fun ts r -> Fun (Lists ts) [r]
zipWithT witness f = cT (\t -> map (uT f) (zipT t))
 where
 cT :: (Tuple (Lists ts) -> [r]) -> Fun (Lists ts) [r]
 cT = curryT
 uT :: Fun ts r -> Tuple ts -> r
 uT = uncurryT

zwp :: forall a. Num a => [a] -> [a] -> [a] -> [a]
zwp = zipWithT (undefined :: a ::: a ::: a ::: Nil) (\x y z -> x + y + z)

zwf :: forall a b c d. (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
zwf = zipWithT (undefined :: a ::: b ::: c ::: Nil)

---- snip ----

You'll need a GHC that's 6.10-ish for this to work.

Cheers,
-- Dan


More information about the Haskell-Cafe mailing list