Simple powerlist implementation in Haskell (http://web.archive.org/web/20070417161203/http://www.cs.utexas.edu/users/psp/powerlist.pdf)

powerlist.hs

{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE DeriveFoldable #-}
{-# LANGUAGE DeriveTraversable #-}
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE FlexibleInstances #-}

import Prelude hiding (zip, unzip)
import qualified Prelude as P
import Data.List (transpose)
import Control.Comonad
import Data.Foldable
import Data.Traversable
import Data.Vector (Vector(..))
import qualified Data.Vector as V

-- | type level arithmetic to statically verify the length of 'PowerList's
data Nat = Z | S Nat deriving Show
type Z1 = S Z

{- |
Conceptually, a 'PowerList' is a list indexed by its length, which is
constrained to be a power of 2 by smart constructors.

PowerList is implemented here as a balanced binary tree whose raw constructors
are not exported.
-}
data PowerList :: Nat -> * -> * where
    Leaf :: a -> PowerList Z1 a
    (:+) :: PowerList n a -> PowerList n a -> PowerList (S n) a

deriving instance Show a => Show (PowerList n a)
deriving instance Functor (PowerList n)
deriving instance Foldable (PowerList n)
deriving instance Traversable (PowerList n)

instance Comonad (PowerList n) where
    extract (Leaf x) = x
    extract (p :+ q) = extract p

    duplicate (Leaf x) = Leaf (Leaf x)
    duplicate l@(p :+ q) = (l <$ p) :+ (l <$ q)

{- | Construct a singleton @PowerList@ from one element. -}
singleton :: a -> PowerList Z1 a
singleton = Leaf

{- | Construct a @PowerList@ of length @n*2@ from two lists of length @n@ -}
tie :: PowerList n a -> PowerList n a -> PowerList (S n) a
tie = (:+)

{- | Deconstruct a @PowerList@ as if it were constructed via 'tie' -}
untie :: PowerList (S n) a -> (PowerList n a -> PowerList n a -> r) -> r
untie (p :+ q) f = f p q

{- |
Construct a @PowerList@ of length @n*2@ by interleaving two lists of length @n@
-}
zip :: PowerList n a -> PowerList n a -> PowerList (S n) a
zip p@(Leaf _) q@(Leaf _) = p :+ q
zip (p1 :+ p2) (q1 :+ q2) = (zip p1 q1) :+ (zip p2 q2)

{- | Deconstruct a @PowerList@ as if it were constructed via 'zip' -}
unzip :: PowerList (S n) a -> (PowerList n a -> PowerList n a -> r) -> r
unzip ((Leaf p) :+ (Leaf q)) f = f (Leaf p) (Leaf q)
unzip ((p1 :+ p2) :+ (q1 :+ q2)) f = f (z1 :+ z2) (w1 :+ w2) where
    (z1, z2) = unzip (p1 :+ q1) (,)
    (w1, w2) = unzip (p2 :+ q2) (,)

s1,s2,s3,s4 :: PowerList Z1 Int
s1 = singleton 1
s2 = singleton 2
s3 = singleton 3
s4 = singleton 4

p1 = s1 `tie` s3
p2 = s2 `tie` s4
p3 = p1 `zip` p2

test_1 = untie p3 $ \p q -> (extract p, extract q)
test_2 = unzip p3 $ \p q -> (extract p, extract q)

m1,m2,m3,m4 :: PowerList Z1 (IO Int)
m1 = singleton $ return 1
m2 = singleton $ return 2
m3 = singleton $ return 3
m4 = singleton $ return 4

pm1 = m1 `tie` m3
pm2 = m2 `tie` m4
pm3 = pm1 `zip` pm2