Haskell converters and monomorphism restriction

Question

I implemented the converters in Haskell as follows:

{-# LANGUAGE RankNTypes #-} import Prelude hiding (foldr) import Data.Foldable type Reducer ba = a -> b -> b type Transducer ab = forall t. Reducer tb -> Reducer ta class Foldable c => Collection c where insert :: a -> ca -> ca empty :: ca reduce :: Collection c => Transducer ab -> ca -> cb reduce f = foldr (f insert) empty mapping :: (a -> b) -> Transducer ab mapping fgx = g (fx) 

Now I want to define a generic map function. Therefore, I load the above code into GHCi:

 Prelude> :load Transducer [1 of 1] Compiling Main ( Transducer.hs, interpreted ) Ok, modules loaded: Main. *Main> let map = reduce . mapping <interactive>:3:20: Couldn't match type 'Reducer t0 b1 -> Reducer t0 a1' with 'forall t. Reducer tb -> Reducer t a' Expected type: (a1 -> b1) -> Transducer ab Actual type: (a1 -> b1) -> Reducer t0 b1 -> Reducer t0 a1 Relevant bindings include map :: (a1 -> b1) -> ca -> cb (bound at <interactive>:3:5) In the second argument of '(.)', namely 'mapping' In the expression: reduce . mapping *Main> let map f = reduce (mapping f) *Main> :t map map :: Collection c => (a -> b) -> ca -> cb 

Therefore, I cannot define map = reduce . mapping map = reduce . mapping . However, I can define map f = reduce (mapping f) .

I believe that this problem is caused by the restriction of monomorphism. I would really like to write map = reduce . mapping map = reduce . mapping instead of map f = reduce (mapping f) . Therefore, I have two questions:

• What causes this problem? Is this a restriction of monomorphism?
• How to fix this problem?

Answer 1

If you make Transducer a newtype than the GHC will be better off developing types. An existential type variable does not go out of scope - the transformer remains polymorphic.

In other words, below is the definition of map = reduce . mapping map = reduce . mapping works

 {-# LANGUAGE RankNTypes #-} import Prelude hiding (foldr, map, (.), id) import Control.Category import Data.Foldable type Reducer ba = a -> b -> b newtype Transducer ab = MkTrans { unTrans :: forall t. Reducer tb -> Reducer ta } class Foldable c => Collection c where insert :: a -> ca -> ca empty :: ca instance Collection [] where insert = (:) empty = [] reduce :: Collection c => Transducer ab -> ca -> cb reduce f = foldr (unTrans f insert) empty mapping :: (a -> b) -> Transducer ab mapping f = MkTrans $ \gx -> g (fx) filtering :: (a -> Bool) -> Transducer aa filtering f = MkTrans $ \gxy -> if fx then gxy else y map :: Collection c => (a -> b) -> ca -> cb map = reduce . mapping filter :: Collection c => (a -> Bool) -> ca -> ca filter = reduce . filtering instance Category Transducer where id = MkTrans id MkTrans f . MkTrans g = MkTrans $ \x -> g (fx) dub :: Num a => a -> a dub x = x + x test1 :: [Int] test1 = reduce (filtering even . mapping dub) [1..10] -- [2,4,6,8,10,12,14,16,18,20] test2 :: [Int] test2 = reduce (mapping dub . filtering even) [1..10] -- [4,8,12,16,20] 

---

 *Main> :t reduce . mapping reduce . mapping :: Collection c => (a -> b) -> ca -> cb 

---

You can also check http://www.reddit.com/r/haskell/comments/2cv6l4/clojures_transducers_are_perverse_lenses/ where the definition of type Transducer ab =:: (a -> Constant (Endo x) a) -> (b -> Constant (Endo x) b) and more. Also other interesting discussions.