trasduttori a Haskell e la restrizione monomorfismo

Question

ho implementato trasduttori in Haskell come segue:

{-# 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) 

Ora voglio definire una funzione generica map. Da qui si carica il codice sopra in 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 

Quindi non posso definire map = reduce . mapping. Tuttavia, posso definire map f = reduce (mapping f).

Credo che questo problema sia causato dalla limitazione del monomorfismo. Mi piacerebbe davvero scrivere map = reduce . mapping anziché map f = reduce (mapping f). Quindi, ho due domande:

1. Che cosa sta causando questo problema? È davvero la restrizione del monomorfismo?
2. Come posso risolvere questo problema?

Answer 1

Se si effettua Transducer a newtype, il GHC risolverà i tipi molto meglio. La variabile di tipo esistenziale non sfugge allo scope Il trasduttore — rimane polimerfo.

In altre parole, con sotto la definizione map = reduce . mapping funziona

{-# 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 

---

Inoltre, si potrebbe voler controllare http://www.reddit.com/r/haskell/comments/2cv6l4/clojures_transducers_are_perverse_lenses/ cui definizione è type Transducer a b =:: (a -> Constant (Endo x) a) -> (b -> Constant (Endo x) b) e vari altri. Anche altre discussioni interessanti.