haskell - 使用箭头对电路进行建模

Question

我有:

class Arrow circ ⇒ Circuit circ where
    wire    :: circ Bool Bool
    notGate :: circ Bool Bool
    orGate  :: circ (Bool , Bool ) Bool

    wire = id
    notGate = arr not
    orGate = arr $ uncurry (||)

我想实现:

-- A and B
andGate :: Circuit circ ⇒ circ (Bool , Bool ) Bool
-- not (A and B)
nandGate :: Circuit circ ⇒ circ (Bool , Bool ) Bool
-- A xor B
xorGate :: Circuit circ ⇒ circ (Bool , Bool ) Bool

我不想使用像 (arr and) 这样简单的东西，而是结合已有的功能。我无法理解如何像使用函数那样组合箭头。

谢谢。

Answer 1

我建议您查看Control.Arrow ，特别是(***), (&&&), and (>>>) 。 This tutorial也确实不错。

• (***) 允许您采用两个箭头并将它们并排放入具有输入和输出(作为元组)的箭头中:

  (***) :: Arrow a => a b c -> a b' c' -> a (b, b') (c, c')
  

• (&&&) 让您再次组合两个箭头并获取其输出的元组，但这次两个箭头将消耗相同输入:

  (&&&) :: Arrow a => a b c -> a b c' -> a b (c, c')
  

• (>>>) 可让您对两个箭头进行排序(组合)。这与函数组合非常相似。事实上，(>>>) 只是 Control.Category 的广义 (.)，其参数翻转了。

  (>>>) :: Arrow a => a b c -> a c d -> a b d
  

  (实际上，约束只需要是Category，但这不是这里的重点。)

然后，我们可以使用一些常见的逻辑等价来获得andGate、nandGate和xorGate:

-- Use (x NAND y) === ((NOT x) OR (NOT y))
nandGate :: Circuit circ => circ (Bool, Bool) Bool
nandGate = (notGate *** notGate) >>> orGate

-- Use (x NAND y) === (NOT (x NAND y))
andGate :: Circuit circ => circ (Bool, Bool) Bool
andGate = nandGate >>> notGate

-- Use (x XOR y) === ((x OR y) AND (x NAND y))
xorGate :: Circuit circ => circ (Bool, Bool) Bool
xorGate = (orGate &&& nandGate) >>> andGate

在-XArrows 旁边

有一个非常简洁的语法扩展，可以让您使用特殊的类似 do 的符号来编写 Arrow。这比神秘的 Control.Arrow 运算符更具可读性，尤其是当您有一堆相互作用的箭头时。

{-# LANGUAGE Arrows #-}

 nandGate :: Circuit circ => circ (Bool , Bool ) Bool
 nandGate = proc (x,y) -> do
              x' <- notGate -< x
              y' <- notGate -< y
              orGate -< (x',y')

 andGate :: Circuit circ => circ (Bool, Bool) Bool
 andGate = proc (x,y) -> do
              z <- nandGate -< (x,y)
              notGate -< z

 xorGate :: Circuit circ => circ (Bool, Bool) Bool
 xorGate = proc (x,y) -> do
              z <- orGate -< (x,y)
              w <- nandGate -< (x,y)
              andGate -< (z,w)