Haskell and type composition the easy way

Below is a small Haskell module that I wrote as an exercise. It defines nifty little utility in the form of a generic type composition mechanism. A composite type is any type in which a type constructor is applied to a another type (denoted with type variables, like a (b c)). It can represent for example a list of optional values, i.e [Maybe Int], aka [] (Maybe Int), or an IO operation sequence that operates on a list of values (IO [a]), etc.

Haskell provides many useful high-level programming constructs for managing individual types, but its standard libraries lack a truly flexible denotation for extending those high-level functions to composition data types. Some of these issues are solved by using so-called "monad transformers", which are very sophisticated, but must be separately defined for each individual monad. And as the name says, their application is limited to monads, and they cannot be used for the many quite useful classes of type constructors at the lower levels of the functor hierarchy, such as Functors, Foldables, Traversables or Applicatives.

The small (and silly) test function at the end of the modules shows, how this modules enables flexible intermingling of overlapping data types using both the monadic do syntax and plain fmap calls. While this only seems to apply to compositions of two types at a time, it quite easily generalizes to any number of types, via meta-composition. If a, b, c ... g are functors, then so is (Comp a b). IO [Maybe Int] can be tagged as Comp (Comp IO []) Maybe Int. Hmmm... Maybe the next step is to generalize these operations to a recursive data type representing arbitrary chains of composition.

One cannot help but appreciate how all of these very useful operations are relatively short one-liners. (Readability for persons not familiar with Haskell or Scala is another question.

{-# LANGUAGE FlexibleContexts #-}

-- A generic type composition module by Reino Ruusu, December 2017, Espoo, Finland

-- The simple type composition tag defined here can do many of the tasks that
-- monad transformers are used for, but in a much more generic way, allowing
-- useful compositions of Functors, Foldables, Traversables, Applicatives and
-- Monads (with certain restrictions).

import Control.Applicative
import Control.Monad
import Data.Foldable
import Data.List

-- This type tags a composition type as a parameterized type constructor
newtype Comp m n a = Comp (m (n a))

-- Decorate a `raw' composition type
comp :: m (n a) -> Comp m n a
comp = Comp

-- Undecorate a tagged composition type
decomp :: Comp m n a -> m (n a)
decomp (Comp x) = x

-- Lift a raw outer type to the composition type (inner has to be Applicative)
lift1 :: (Functor m, Applicative n) => m a -> Comp m n a
lift1 = Comp . (pure <$>)

-- Lift a raw inner type to the composition type (outer has to be Applicative)
lift2 :: (Applicative m) => n a -> Comp m n a
lift2 = Comp . pure

-- Foldable instance
instance (Foldable m, Foldable n) => Foldable (Comp m n) where
  -- foldMap :: Monoid k => (a -> k) -> Comp m n a -> k
  foldMap f (Comp x) = foldr (\a l -> foldMap f a `mappend` l) mempty x 

-- Functor instance
instance (Functor m, Functor n) => Functor (Comp m n) where
  -- fmap :: (a -> b) -> (Comp m n a) -> (Comp m n b)
  fmap f (Comp x) = Comp (fmap (fmap f) x)

-- Applicative instance
instance (Applicative m, Applicative n) => Applicative (Comp m n) where
  -- pure :: a -> Comp m n a
  pure = comp . pure . pure
  -- (<*>) :: Comp m n (a -> b) -> Comp m n a -> Comp m n b
  Comp f <*> Comp x = Comp (liftA2 (<*>) f x)

-- Monoid instance
instance (Applicative m, Applicative n, Monoid a) => Monoid (Comp m n a) where
  -- mempty :: Comp m n a
  mempty = pure mempty
  -- mappend :: Comp m n a -> Comp m n a -> Comp m n a
  mappend = (*>)

-- Monad instance (only works if inner type is Traversable, unlike IO, for example)
instance (Monad m, Monad n, Traversable n) => Monad (Comp m n) where
  -- return = pure
  -- (>>=) :: Comp m n a -> (a -> Comp m n b) -> Comp m n b
  Comp x >>= f = Comp $ x >>= fmap join . sequence . fmap (decomp . f)


-- Test routine, builds a (Comp IO []) monad in the do block
-- First fmap (show) applies to (Comp IO [] Int), resulting in (Comp IO [] String).
-- After decomp, second fmap applies to (IO [String]).
-- Execution results in 4*(1 + 4) calls to print, and a return value of
-- "4, 5, 6, 7, 3, 4, 5, 6, 2, 3, 4, 5, 1, 2, 3, 4"

test :: () -> IO String
test () = fmap (intercalate ", ") $ decomp $ fmap (show) $ do
  a <- lift2 [1, 2, 3, 4]
  lift1 (print a)
  b <- lift2 [5, 6, 7, 8]
  lift1 (print (a, b))
  return (b - a) :: Comp IO [] Int