哈斯克尔的传感器和单态限制 [英] Transducers in Haskell and the monomorphism restriction

问题描述

我在Haskell中实现了换能器，如下所示：

{ - ＃LANGUAGE RankNTypes＃ - }

导入Prelude隐藏（foldr）
导入Data.Foldable

类型Reducer ba = a - > b - > b
型传感器a b = forall t。减速器t b - > Reducer t a

class可折叠c => Collection c其中
insert :: a - > c a - > c a
empty :: c a

reduce :: Collection c =>传感器a b - > c a - > c b
reduce f = foldr（f insert）empty

mapping ::（a - > b） - >传感器ab
映射fgx = g（fx）


现在我想定义一个通用 map 函数。因此，我将上面的代码加载到GHCi中：

  Prelude> ：load Transducer 
 [1的1]编译Main（Transducer.hs，解释）
好​​了，加载模块：Main。 
 * Main>让map = reduce。映射
 
< interactive>：3：20：
无法匹配类型'Reducer t0 b1  - >减速机t0 a1'
与'forall t。减速器t b  - > Reducer t a'
预期类型：（a1  - > b1） - >换能器a b 
实际类型：（a1  - > b1） - >减速机t0 b1  - > Reducer t0 a1 
相关绑定包括
 map ::（a1  - > b1） - > c a  - > c（绑定在< interactive>：3：5）
在'（。）'的第二个参数中，即'映射'
在表达式：reduce中。映射
 * Main>让map f = reduce（映射f）
 * Main> ：t map 
 map :: Collection c => （a  - > b） - > c a  - > c b 
  

所以我无法定义 map = reduce。映射。不过，我可以定义 map f = reduce（映射f）。我相信这个问题是由单态限制。我真的很想写 map = reduce。映射而不是映射f = reduce（映射f）。因此，我有两个问题：

1. 是什么导致了这个问题？是否确实是单态限制？


2. 如何解决这个问题？

解决如果你使 Transducer a newtype ，那么GHC将会找出更多的类型更好。存在型变量不会转义范围—换能器将保持多态。

换句话说，用下面的定义 map = reduce。 mapping works

  { - ＃LANGUAGE RankNTypes＃ - } 
 
 import Prelude隐藏（foldr，map，（。），id）
导入Control.Category 
导入Data.Foldable 
 
类型Reducer ba = a  - > b  - > b 
 newtype传感器a b = MkTrans {unTrans :: forall t。减速器t b  - > Reducer t a} 
 
 class可折叠c => Collection c其中
 insert :: a  - > c a  - > ca 
 empty :: ca 
 
实例集合[]其中
 insert =（:) 
 empty = [] 
 
 reduce ::集合c =>传感器a b  - > c a  - > c b 
 reduce f = foldr（unTrans f insert）empty 
 
 mapping ::（a  - > b） - >换能器a b 
映射f = MkTrans $ \g x  - > g（f x）
 
 filtering ::（a  - > Bool） - >换能器a 
过滤f = MkTrans $ \g x y  - >如果f x则g x y else y 
 
 map :: Collection c => （a  - > b） - > c a  - > c b 
 map = reduce。映射
 
 filter :: Collection c => （a  - > Bool） - > c a  - > c a 
 filter = reduce。过滤
 
实例类别传感器其中
 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（过滤偶数映射配音）[1..10] 
  -  -  [2,4,6,8,10,12,14,16,18,20] 
 
 test2 :: [Int] 
 test2 = reduce（映射配音过滤） [1..10] 
  -  [4,8,12,16,20] 
  

< hr>

  * Main> ：减少。映射
 reduce。 mapping :: Collection c => （a  - > b） - > c a  - > cb 
  

---

您也可以检查
其中定义为 type Transducer ab = ::（a - > Constant（Endo x）a） - > （b->常数（Endo x）b）和其他各种。还有其他各种讨论。

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:

1. What's causing this problem? Is it indeed the monomorphism restriction?
2. How do I fix this problem?

解决方案

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 interestig discussion.

这篇关于哈斯克尔的传感器和单态限制的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！