On Wed, Sep 19, 2012 at 8:36 PM, wren ng thornton <w...@freegeek.org> wrote: >> P.S. It is actually possible to write zip function using Boehm-Berarducci >> encoding: >> http://okmij.org/ftp/ftp/Algorithms.html#zip-folds > > > Of course it is; I just never got around to doing it :)
If you do, you might want to consider not using the above method, as I seem to recall it doing an undesirable amount of extra work (repeated O(n) tail). One can do better with some controversial types (this is not my idea originally; ski (don't know his real name) on freenode's #haskell showed it to me a long time ago): ---- snip ---- {-# LANGUAGE PolymorphicComponents #-} module ABC where newtype L a = L { unL :: forall r. (a -> r -> r) -> r -> r } nil :: L a nil = L $ \_ z -> z cons :: a -> L a -> L a cons x (L xs) = L $ \f -> f x . xs f newtype A a c = Roll { unroll :: (a -> A a c -> L c) -> L c } type B a c = a -> A a c -> L c zipWith :: (a -> b -> c) -> L a -> L b -> L c zipWith f (L as) (L bs) = unroll (as consA nilA) (bs consB nilB) where -- nilA :: A a c nilA = Roll $ const nil -- consA :: a -> A a c -> A a c consA x xs = Roll $ \k -> k x xs -- nilB :: B a c nilB _ _ = nil -- consB :: b -> B a c -> B a c consB y ys x xs = f x y `cons` unroll xs ys ---- snip ---- This traverses each list only once. -- Dan _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe