Transducers trong Haskell và những hạn chế monomorphism

Question

tôi thực hiện đầu dò trong Haskell như sau:

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

Bây giờ tôi muốn xác định một map hàm tổng quát. Do đó tôi tải mã trên vào 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 

Vì vậy, tôi không thể xác định map = reduce . mapping. Tuy nhiên, tôi có thể xác định map f = reduce (mapping f).

Tôi tin rằng vấn đề này là do hạn chế monomorphism. Tôi thực sự muốn viết map = reduce . mapping thay vì map f = reduce (mapping f). Do đó, tôi có hai câu hỏi:

1. Điều gì gây ra sự cố này? Nó thực sự là hạn chế monomorphism?
2. Làm cách nào để khắc phục sự cố này?

Answer 1

Nếu bạn thực hiện Transducer một newtype, hơn GHC sẽ làm việc tốt hơn nhiều. Biến loại tồn tại sẽ không thoát khỏi phạm vi Bộ chuyển đổi — sẽ vẫn ở dạng đa hình.

Nói cách khác, với định nghĩa dưới đây map = reduce . mapping làm việc

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

---

Ngoài ra bạn có thể muốn kiểm tra http://www.reddit.com/r/haskell/comments/2cv6l4/clojures_transducers_are_perverse_lenses/ nơi định nghĩa là type Transducer a b =:: (a -> Constant (Endo x) a) -> (b -> Constant (Endo x) b) và khác nhau khác. Ngoài ra thảo luận interestig khác.