преобразователи в Haskell и ограничение -мономорфизм

Question

I реализованы датчики в Haskell следующим образом:

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

Теперь я хочу, чтобы определить общий map функцию. Поэтому я загружаю выше код в 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 

Так что я не могу определить map = reduce . mapping. Однако я могу определить map f = reduce (mapping f).

Я считаю, что эта проблема вызвана ограничением мономорфизма. Я бы очень хотел написать map = reduce . mapping вместо map f = reduce (mapping f). Следовательно, у меня есть два вопроса:

1. В чем причина этой проблемы? Действительно ли это ограничение мономорфизма?
2. Как исправить эту проблему?

Answer 1

Если вы делаете Transducer a newtype, чем GHC будет работать над типами намного лучше. Экзистенциальная переменная типа не выйдет из области — преобразователь останется полиморфным.

Другими словами, с определением ниже map = reduce . mapping работы

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

---

Также Вы можете хотеть проверить http://www.reddit.com/r/haskell/comments/2cv6l4/clojures_transducers_are_perverse_lenses/ где определение type Transducer a b =:: (a -> Constant (Endo x) a) -> (b -> Constant (Endo x) b) и различные другие. Также интересное обсуждение.