对从另一个 Iso 构建一个 Iso 感到困惑

Question

我目前正在编写一些代码以特定方式处理逻辑形式。为此，我编写了以下使用镜头的代码：

{-# LANGUAGE NoImplicitPrelude #-}            
{-# LANGUAGE Rank2Types #-} 

module Logic.Internal.Formula where 

import BasicPrelude hiding (empty, negate)        
import qualified Data.Set as Set 
import Control.Lens 

data Atom = Pos { i :: Integer}                                                                                           
          | Neg { i :: Integer}                                                                                           
          deriving (Eq, Ord, Show, Read)                                                                                  

negatingAtom :: Iso' Atom Atom                                                                                            
negatingAtom = iso go go                                                                                                  
  where go (Pos x) = Neg x                                                                                                
        go (Neg x) = Pos x                                                                                                

newtype Conjunction a = Conjunction (Set a)                                                                               
  deriving (Eq, Ord, Read, Show)                                                                                          

conjuncts :: Conjunction a -> [a]                                                                                         
conjuncts (Conjunction x) = Set.toList x                                                                                  

newtype Disjunction a = Disjunction (Set a)                                                                               
  deriving (Eq, Ord, Read, Show)
disjuncts :: Disjunction a -> [a]                                                                                         
disjuncts (Disjunction x) = Set.toList x                                                                                  

negatingClause :: Iso' (Conjunction Atom) (Disjunction Atom)                                                              
negatingClause = liftClause negatingAtom                                                                                  

type CNF = Conjunction (Disjunction Atom)                                                                                 
type DNF = Disjunction (Conjunction Atom)

-- Helper stuff                                                               

liftClause :: (Ord a) => Iso' a a -> Iso' (Conjunction a) (Disjunction a)                                                 
liftClause x = let pipeline = Set.fromList . fmap (view x) in                                                             
  iso (Disjunction . pipeline . conjuncts) (Conjunction . pipeline . disjuncts)

然后，我尝试以（我认为是）自然的方式写下以下内容：

type CNF = Conjunction (Disjunction Atom)                                                                                 
type DNF = Disjunction (Conjunction Atom)                                                                                 

negatingForm :: Iso' CNF DNF                                                                                              
negatingForm = liftClause negatingClause

然而，类型检查器绝对对此不满意，我完全不确定为什么。确切的输出如下：

Couldn't match type ‘Conjunction Atom’ with ‘Disjunction Atom’                                                            
Expected type: p1 (Disjunction Atom) (f1 (Disjunction Atom))                                                              
               -> p1 (Disjunction Atom) (f1 (Disjunction Atom))                                                           
  Actual type: p1 (Disjunction Atom) (f1 (Disjunction Atom))                                                              
               -> p1 (Conjunction Atom) (f1 (Conjunction Atom))                                                           
In the first argument of ‘liftClause’, namely ‘negatingClause’                                                            
In the expression: liftClause negatingClause

我对镜头有点陌生，真的很想了解我在这里误解了什么，以及我将如何实现所需的 Iso。

Answer 1

liftClause 只能在 Iso' a a 上运行 - 即两个域必须具有相同的类型 - 类型 a.

但是 negatingClause 有类型：

negatingClause :: Iso' (Conjunction Atom) (Disjunction Atom)

所以你不能调用 liftClause 因为 Conjunction Atom 和 Disjunction Atom 不一样。

Answer 2

我没有足够详细地阅读这篇文章来弄清楚你应该做什么，但是liftClause需要一个Iso' a a，即同构某种类型本身。 negatingClause 是一个 Iso' (Conjunction Atom) (Disjunction Atom)；这绝对不匹配 Iso' a a。这就是类型错误抱怨无法将 Conjunction Atom 与 Disjunction Atom.

匹配的原因

Answer 3

（答案也发布到 http://lpaste.net/164691）

这是一个使用 TypeFamilies 的解决方案。

首先我们将简化设置：

 {-# LANGUAGE TypeFamilies #-}

 import Control.Lens

 data Atom = Pos Int | Neg Int deriving (Show)
 newtype And a = And [a]       deriving (Show)
 newtype Or a  = Or [a]        deriving (Show)

目标是创建以下函数序列：

f0 :: Atom -> Atom                      g0 :: Atom -> Atom
f1 :: And Atom -> Or Atom               g1 :: Or Atom -> And Atom
f2 :: And (Or Atom) -> Or (And Atom)    g1 :: Or (And Atom) -> And (Or Atom)
...

f 和 g 互为倒数。从这些函数我们可以创建 Iso' 个镜头：

iso0 = iso f0 g0  :: Iso' Atom Atom
iso1 = iso f1 g1  :: Iso' (And Atom) (Or Atom)
iso2 = iso f2 g2  :: Iso' (And (Or Atom)) (Or (And Atom))

我们首先创建充当类型函数的类型族 Negated。 Negated a 是 f 函数（或 g 函数）将 a 映射到的类型。

 type family Negated a

 type instance Negated Atom = Atom
 type instance Negated (And a) = Or (Negated a)
 type instance Negated (Or a) = And (Negated a)

例如，Negated (And (Or Atom))是类型Or (And Atom))。

接下来，我们定义一个类型class来执行反转操作：

 class Invertible a where
   invert :: a -> Negated a

 instance Invertible Atom where
   invert (Pos a) = Neg a
   invert (Neg a) = Pos a

 instance Invertible a => Invertible (And a) where
   invert (And clauses) =  Or (map invert clauses)

 instance Invertible a => Invertible (Or a) where
   invert (Or clauses) = And (map invert clauses)

同构的定义现在很简单：

 iso0 :: Iso' Atom Atom
 iso0 = iso invert invert

 iso1  :: Iso' (And Atom) (Or Atom)
 iso1 = iso invert invert

 iso2 :: Iso' (And (Or Atom)) (Or (And Atom))
 iso2 = iso invert invert

示例：

 and1 = And [ Pos 1, Neg 2, Pos 3 ]
 or1 = Or [and1]

 test1 = invert and1                 -- Or [Neg 1,Pos 2,Neg 3]
 test2 = invert or1                  -- And [Or [Neg 1,Pos 2,Neg 3]]

请注意，这种对逻辑谓词建模的方法的一个限制是所有原子在表达式树中的深度必须相同。例如，你不能表示这棵树（这里 x、y 和 z 是原子）：

对从另一个 Iso 构建一个 Iso 感到困惑

Confused about constructing an Iso from another Iso

haskell

haskell-lens