How to write `zipWith` for the Fold/List datatype.

.project-settings.yml

module-template: ! 'module MODULE_NAME where

'
extensions: {}
environment: null
cabal-file: project.cabal
modules:
  Main(gistfile1.hs):
    filename: gistfile1.hs
version: 1
ghc-args: []

gistfile1.hs

{-# LANGUAGE Rank2Types #-}

import Prelude hiding (zipWith, take)
import qualified Prelude as P

data List a = List (forall r. (a -> r -> r) -> r -> r)

zipWith :: (a -> b -> c) -> List a -> List b -> List c
zipWith f (List xs) (List ys) = List $ \g z ->
  let cons_ x xs  = \ys -> runMatcher ys x xs
      nil_        = \_  -> z
      _cons y ys  = Matcher $ \x xs -> g (f x y) (xs ys)
      _nil        = Matcher $ \_ _  -> z
  in (xs cons_ nil_) (ys _cons _nil)

newtype Matcher a r = Matcher { runMatcher :: a -> (Matcher a r -> r) -> r }

data Peano  = Peano (forall r. r -> (r -> r) -> r)

take :: Peano -> List a -> List a
take (Peano n) (List ys) = List $ \g z ->
  let zero_       = \_  -> z
      succ_ xs    = \ys -> runMatcherTake ys xs
      _cons y ys  = MatcherTake $ \xs -> g y (xs ys)
      _nil        = MatcherTake $ \_  -> z
  in (n zero_ succ_) (ys _cons _nil)

newtype MatcherTake r = MatcherTake { runMatcherTake :: (MatcherTake r -> r) -> r}

-- Conversion for testing
fromData :: [a] -> List a
fromData xs = List $ \f z -> foldr f z xs

toData :: List a -> [a]
toData (List xs) = xs (:) []

fromNat n = Peano $ \z s -> foldnat z s n
  where foldnat z s 0 = z
        foldnat z s n = s (foldnat z s $ n - 1)

main = print $ toData $ take (fromNat 6) $ fromData [0..4]

See https://gist.github.com/jasonreich/4761643/revisions for the evolution of the solution.