I implemented transducers in Haskell as follows:
{-# LANGUAGE RankNTypes #-}
import Prelude hiding (foldr)
import Data.Foldable
type Reducer b a = a -> b -> b
type Transducer a b = forall t. Reducer t b -> Reducer t a
class Foldable c => Collection c where
insert :: a -> c a -> c a
empty :: c a
reduce :: Collection c => Transducer a b -> c a -> c b
reduce f = foldr (f insert) empty
mapping :: (a -> b) -> Transducer a b
mapping f g x = g (f x)
Now I want to define a generic map
function. Hence 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 t b -> Reducer t a’
Expected type: (a1 -> b1) -> Transducer a b
Actual type: (a1 -> b1) -> Reducer t0 b1 -> Reducer t0 a1
Relevant bindings include
map :: (a1 -> b1) -> c a -> c b (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) -> c a -> c b
So I can't define map = reduce . mapping
. However, I can define map f = reduce (mapping f)
.
I believe that this problem is caused by the monomorphism restriction. I would really like to write map = reduce . mapping
instead of map f = reduce (mapping f)
. Hence, I have two questions:
If you make Transducer
a newtype
, than the GHC will work out the types much better. Existential type variable won't escape the scope — transducer will stay polymorphic.
In other words, with below definition map = reduce . mapping
works
{-# LANGUAGE RankNTypes #-}
import Prelude hiding (foldr, map, (.), id)
import Control.Category
import Data.Foldable
type Reducer b a = a -> b -> b
newtype Transducer a b = MkTrans { unTrans :: forall t. Reducer t b -> Reducer t a }
class Foldable c => Collection c where
insert :: a -> c a -> c a
empty :: c a
instance Collection [] where
insert = (:)
empty = []
reduce :: Collection c => Transducer a b -> c a -> c b
reduce f = foldr (unTrans f insert) empty
mapping :: (a -> b) -> Transducer a b
mapping f = MkTrans $ \g x -> g (f x)
filtering :: (a -> Bool) -> Transducer a a
filtering f = MkTrans $ \g x y -> if f x then g x y else y
map :: Collection c => (a -> b) -> c a -> c b
map = reduce . mapping
filter :: Collection c => (a -> Bool) -> c a -> c a
filter = reduce . filtering
instance Category Transducer where
id = MkTrans id
MkTrans f . MkTrans g = MkTrans $ \x -> g (f x)
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) -> c a -> c b
Also you could want to check http://www.reddit.com/r/haskell/comments/2cv6l4/clojures_transducers_are_perverse_lenses/
where definition is type Transducer a b =:: (a -> Constant (Endo x) a) -> (b -> Constant (Endo x) b)
and various other. Also other interesting discussion.