Haskell/Arrow 教程
箭头提供了一种替代方法，可以用来用基本函子类结构化计算。本章提供了一个关于箭头的实践教程，而下一章 理解箭头 用概念概述补充了它。我们建议你从教程开始，这样你就可以尝尝用箭头编程的感觉。你当然可以在教程和理解箭头的第一部分之间来回切换，如果你更喜欢以更慢的速度进行。一定要在 GHC(i) 上按照教程的每一步进行操作。
Stephen 的 Arrow 教程
[edit | edit source]在本教程中，我将创建自己的箭头，展示如何使用箭头 proc 表示法，并展示 ArrowChoice 的工作原理。我们最终会得到一个简单的猜字游戏。
首先，我们给出一个语言 pragma（省略），以便在编译器中启用箭头 do 表示法。然后，是一些导入
module Main where
import Control.Arrow
import Control.Monad
import qualified Control.Category as Cat
import Data.List
import Data.Maybe
import System.Random
任何 Haskell 函数都可以作为箭头，因为函数类型构造器 (->) 有一个 Arrow 实例。在本教程中，我将构建一个比这个更有意思的箭头，它能够维护状态（普通 Haskell 函数箭头无法做到）。箭头可以产生各种各样的效果，包括 I/O，但我们只探索一些简单的例子。
我们将新箭头称为 Circuit，以暗示我们可以将箭头可视化为电路。[1]
Circuit 的类型定义
[edit | edit source]作为箭头的普通 Haskell 函数类型为 a -> b。我们的 Circuit 箭头有两个显著的特点：首先，我们用 newtype 声明把它包起来，以清晰地定义 Arrow 实例。其次，为了让电路能够维护自己的内部状态，我们的箭头返回一个自身的替代品，以及正常的 b 输出值。
newtype Circuit a b = Circuit { unCircuit :: a -> (Circuit a b, b) }
为了使它成为一个箭头，我们需要使它成为 Category 和 Arrow 的实例。在这些定义中，我们总是用它返回的新版本替换每个 Circuit。
instance Cat.Category Circuit where
id = Circuit $ \a -> (Cat.id, a)
(.) = dot
where
(Circuit cir2) `dot` (Circuit cir1) = Circuit $ \a ->
let (cir1', b) = cir1 a
(cir2', c) = cir2 b
in (cir2' `dot` cir1', c)
Cat.id 函数用自身的副本替换自身，而不维护任何状态。(.) 函数的目的是从右到左将两个箭头链接起来。(>>>) 和 (<<<) 是基于 (.) 的。它需要用执行参数 Circuits 返回的两个替换值的 `dot` 来替换自身。
instance Arrow Circuit where
arr f = Circuit $ \a -> (arr f, f a)
first (Circuit cir) = Circuit $ \(b, d) ->
let (cir', c) = cir b
in (first cir', (c, d))
arr 将一个普通 Haskell 函数提升为箭头。与 id 一样，它给出的替换值只是它本身，因为普通 Haskell 函数无法维护状态。
现在我们需要一个函数来运行电路
runCircuit :: Circuit a b -> [a] -> [b]
runCircuit _ [] = []
runCircuit cir (x:xs) =
let (cir',x') = unCircuit cir x
in x' : runCircuit cir' xs
对于像我这样的 mapAccumL 迷来说，这可以写成
runCircuit :: Circuit a b -> [a] -> [b]
runCircuit cir inputs =
snd $ mapAccumL (\cir x -> unCircuit cir x) cir inputs
或者，在 eta-reduction 后，简化为
runCircuit :: Circuit a b -> [a] -> [b]
runCircuit cir = snd . mapAccumL unCircuit cir
Circuit 原语
[edit | edit source]让我们定义一个广义的累加器，作为我们以后工作的基础。accum' 是 accum 的一个不那么通用的版本。
-- | Accumulator that outputs a value determined by the supplied function.
accum :: acc -> (a -> acc -> (b, acc)) -> Circuit a b
accum acc f = Circuit $ \input ->
let (output, acc') = input `f` acc
in (accum acc' f, output)
-- | Accumulator that outputs the accumulator value.
accum' :: b -> (a -> b -> b) -> Circuit a b
accum' acc f = accum acc (\a b -> let b' = a `f` b in (b', b'))
这是一个有用的具体累加器，它会对所有作为输入传递给它的数字进行累加。
total :: Num a => Circuit a a
total = accum' 0 (+)
我们可以这样运行这个电路
*Main> runCircuit total [1,0,1,0,0,2]
[1,1,2,2,2,4]
*Main>
Arrow proc 表示法
[edit | edit source]这里是一个统计平均函数
mean1 :: Fractional a => Circuit a a
mean1 = (total &&& (const 1 ^>> total)) >>> arr (uncurry (/))
它维护两个累加器单元，一个用于求和，一个用于元素的数量。它使用 "fanout" 运算符 &&& 拆分输入，并在第二个流的输入之前，它丢弃输入值并用 1 替换它。
const 1 ^>> total 是 arr (const 1) >>> total 的简写。第一个流是输入的总和。第二个流是每个输入的 1 的总和（即输入数量的计数）。然后，它用 (/) 运算符合并两个流。
以下是同一个函数，但使用箭头 proc 表示法编写
mean2 :: Fractional a => Circuit a a
mean2 = proc value -> do
t <- total -< value
n <- total -< 1
returnA -< t / n
proc 表示法描述了箭头之间相同的关系，但以完全不同的方式。你不需要明确地描述连接方式，而是使用变量绑定和纯 Haskell 表达式将箭头粘合在一起，编译器会为你处理所有 arr, (>>>), (&&&) 的东西。箭头 proc 表示法还包含一个与单子 do 一样的纯 'let' 语句。
proc 是引入箭头表示法的关键字，它将箭头输入绑定到一个模式（本例中为 value）。do 块中的箭头语句采用以下形式之一
变量绑定模式 <- 箭头 -< 给出箭头输入的纯表达式箭头 -< 给出箭头输入的纯表达式
与单子一样，do 关键字只用于使用 <- 的变量绑定模式组合多行。与单子一样，最后一行不允许有变量绑定模式，最后一行输出的值就是箭头的输出值。returnA 是一个与 'total' 相同的箭头（事实上，returnA 只是身份箭头，定义为 arr id）。
与单子一样，除了最后一行之外的其它行可能没有变量绑定，你只获得效果，丢弃返回值。在 Circuit 中，这样做永远没有意义（因为除了返回值之外，没有状态可以逃逸），但在许多箭头中，会有意义。
如你所见，对于这个例子来说，proc 表示法使代码更具可读性。让我们试试它们
*Main> runCircuit mean1 [0,10,7,8]
[0.0,5.0,5.666666666666667,6.25]
*Main> runCircuit mean2 [0,10,7,8]
[0.0,5.0,5.666666666666667,6.25]
*Main>
猜字游戏：选择一个词
[edit | edit source]现在来玩我们的猜字游戏。让我们从词典中选择一个词
generator :: Random a => (a, a) -> StdGen -> Circuit () a
generator range rng = accum rng $ \() rng -> randomR range rng
dictionary = ["dog", "cat", "bird"]
pickWord :: StdGen -> Circuit () String
pickWord rng = proc () -> do
idx <- generator (0, length dictionary-1) rng -< ()
returnA -< dictionary !! idx
使用 generator，我们使用累加器功能来保存我们的随机数生成器。pickWord 没有引入任何新内容，除了生成器箭头是由一个接受参数的 Haskell 函数构造的。以下是输出
*Main> rng <- getStdGen
*Main> runCircuit (pickWord rng) [(), (), ()]
["dog","bird","dog"]
*Main>
我们将在稍后使用这些小箭头。第一个在第一次返回 True，然后永远返回 False
oneShot :: Circuit () Bool
oneShot = accum True $ \_ acc -> (acc, False)
*Main> runCircuit oneShot [(), (), (), (), ()]
[True,False,False,False,False]
第二个存储一个值并返回它，当它得到一个新的值时
delayedEcho :: a -> Circuit a a
delayedEcho acc = accum acc (\a b -> (b,a))
可以缩写为
delayedEcho :: a -> Circuit a a
delayedEcho acc = accum acc (flip (,))
*Main> runCircuit (delayedEcho False) [True, False, False, False, True]
[False,True,False,False,False]
游戏的主箭头将重复执行，我们希望在第一次迭代中只选择一次单词，并在游戏的其余部分记住它。我们更希望只运行一次 `pickWord`（因为在实际实现中它可能非常慢），而不是在随后的循环中屏蔽它的输出。然而，就目前而言，电路中的数据流**必须**沿着组件箭头的**所有**路径向下流动。为了允许数据流沿着一条路径流动，而另一条路径不流动，我们需要使我们的箭头成为 `ArrowChoice` 的实例。以下是最小定义
instance ArrowChoice Circuit where
left orig@(Circuit cir) = Circuit $ \ebd -> case ebd of
Left b -> let (cir', c) = cir b
in (left cir', Left c)
Right d -> (left orig, Right d)
getWord :: StdGen -> Circuit () String
getWord rng = proc () -> do
-- If this is the first game loop, run pickWord. mPicked becomes Just <word>.
-- On subsequent loops, mPicked is Nothing.
firstTime <- oneShot -< ()
mPicked <- if firstTime
then do
picked <- pickWord rng -< ()
returnA -< Just picked
else returnA -< Nothing
-- An accumulator that retains the last 'Just' value.
mWord <- accum' Nothing mplus -< mPicked
returnA -< fromJust mWord
因为定义了 `ArrowChoice`，编译器现在允许我们在 `<-` 之后添加 `if`，从而选择要执行的箭头（运行 `pickWord` 或跳过它）。请注意，这不是普通的 Haskell `if`：编译器使用 `ArrowChoice` 实现这一点。编译器也以相同的方式在这里实现 `case`。
重要的是要理解，除了 `if` 或 `case` 条件中，没有一个局部名称绑定（包括 `proc` 参数）在 `<-` 和 `-<` 之间处于作用域。例如，以下是非法的
{-
proc rng -> do
idx <- generator (0, length dictionary-1) rng -< () -- ILLEGAL
returnA -< dictionary !! idx
-}
要执行的箭头（这里为 `generator (0, length dictionary -1) rng`）在 `proc` 语句之外存在的范围中进行评估。`rng` 在此范围内不存在。如果你仔细想想，这是有道理的，因为箭头只在开始时（`proc` 之外）构造。如果它是为箭头的每次执行而构造的，那么它将如何保持其状态呢？
让我们尝试 `getWord`
*Main> rng <- getStdGen
*Main> runCircuit (getWord rng) [(), (), (), (), (), ()]
["dog","dog","dog","dog","dog","dog"]
*Main>
现在是游戏
attempts :: Int
attempts = 5
livesLeft :: Int -> String
livesLeft hung = "Lives: ["
++ replicate (attempts - hung) '#'
++ replicate hung ' '
++ "]"
hangman :: StdGen -> Circuit String (Bool, [String])
hangman rng = proc userInput -> do
word <- getWord rng -< ()
let letter = listToMaybe userInput
guessed <- updateGuess -< (word, letter)
hung <- updateHung -< (word, letter)
end <- delayedEcho True -< not (word == guessed || hung >= attempts)
let result = if word == guessed
then [guessed, "You won!"]
else if hung >= attempts
then [guessed, livesLeft hung, "You died!"]
else [guessed, livesLeft hung]
returnA -< (end, result)
where
updateGuess :: Circuit (String, Maybe Char) String
updateGuess = accum' (repeat '_') $ \(word, letter) guess ->
case letter of
Just l -> map (\(w, g) -> if w == l then w else g) (zip word guess)
Nothing -> take (length word) guess
updateHung :: Circuit (String, Maybe Char) Int
updateHung = proc (word, letter) -> do
total -< case letter of
Just l -> if l `elem` word then 0 else 1
Nothing -> 0
main :: IO ()
main = do
rng <- getStdGen
interact $ unlines -- Concatenate lines out output
. ("Welcome to Arrow Hangman":) -- Prepend a greeting to the output
. concat . map snd . takeWhile fst -- Take the [String]s as long as the first element of the tuples is True
. runCircuit (hangman rng) -- Process the input lazily
. ("":) -- Act as if the user pressed ENTER once at the start
. lines -- Split input into lines
这是一个示例会话。为了获得最佳效果，请编译游戏并从终端运行它，而不是从 GHCi 运行它
Welcome to Arrow Hangman ___ Lives: [#####] a ___ Lives: [#### ] g __g Lives: [#### ] d d_g Lives: [#### ] o dog You won!
在本节中，我将完成对箭头表示法的介绍。
我们这样实现 `mean2`
mean2 :: Fractional a => Circuit a a
mean2 = proc value -> do
t <- total -< value
n <- total -< 1
returnA -< t / n
GHC 为将箭头语句与作用于箭头的函数组合定义了香蕉括号语法。（在 Ross Paterson 的论文 [2] 中使用了 `form` 关键字，但 GHC 代之以采用了香蕉括号。）虽然没有真正的理由，但我们可以这样写 `mean`
mean3 :: Fractional a => Circuit a a
mean3 = proc value -> do
(t, n) <- (| (&&&) (total -< value) (total -< 1) |)
returnA -< t / n
`(| ... |)` 中的第一个项目是一个函数，它接受任意数量的箭头作为输入并返回一个箭头。此处不能使用中缀表示法。它后面跟着参数，这些参数采用 `proc` 语句的形式。这些语句可能包含 `do` 和使用 `<-` 的绑定，如果你愿意的话。每个参数都转换为一个箭头，并作为参数传递给函数 `(&&&)`。
你可能会问，这有什么意义呢？我们可以很愉快地组合箭头，而无需 `proc` 表示法。好吧，意义在于你可以方便地在语句中使用局部变量绑定。
实际上不需要香蕉括号。编译器足够智能，可以假设当您像这样编写它时，这就是您的意思（注意，此处允许使用中缀表示法）
mean4 :: Fractional a => Circuit a a
mean4 = proc value -> do
(t, n) <- (total -< value) &&& (total -< 1)
returnA -< t / n
那么为什么我们需要香蕉括号呢？对于这种更简单的语法模棱两可的情况。原因是 `proc` 命令的箭头部分**不是普通的 Haskell 表达式**。回想一下，对于在 `proc` 语句中指定的箭头，以下内容成立
- 局部变量绑定只允许在 `-<` 之后的输入表达式中，以及 `if` 和 `case` 条件中。箭头本身在 `proc` 之外存在的范围中进行解释。
- `if` 和 `case` 语句不是简单的 Haskell。它们是使用 `ArrowChoice` 实现的。
- 用于组合箭头的函数也不是正常的 Haskell。它们是香蕉括号表示法的简写。
为了不重复使用 `mean` 示例，这里还有另一种使用递归绑定来实现它的方法。为了使它起作用，我们需要一个将输入延迟一步的箭头
delay :: a -> Circuit a a
delay last = Circuit $ \this -> (delay this, last)
以下是 `delay` 的作用
*Main> runCircuit (delay 0) [5,6,7]
[0,5,6]
*Main>
这是我们的 `mean` 的递归版本
mean5 :: Fractional a => Circuit a a
mean5 = proc value -> do
rec
(lastTot, lastN) <- delay (0,0) -< (tot, n)
let (tot, n) = (lastTot + value, lastN + 1)
let mean = tot / n
returnA -< mean
`rec` 块类似于 `do`' 块，除了
- 最后一行可以是，通常是，一个变量绑定。它可以是 `let`，也可以是使用 `<-` 的 `do`-块绑定。
- `rec` 块没有返回值。`var <- rec ...` 是非法的，`rec` 不允许是 `do` 块中的最后一个元素。
- 预期变量的使用将形成一个循环（否则 `rec` 就没有意义）。
`rec` 的机制由 `ArrowLoop` 类中的 `loop` 函数处理，我们为 Circuit 这样定义它
instance ArrowLoop Circuit where
loop (Circuit cir) = Circuit $ \b ->
let (cir', (c,d)) = cir (b,d)
in (loop cir', c)
在幕后，它的工作原理是这样的
- 在 `rec` 中定义的任何在 `rec` 中向前引用的变量都会通过传递给 `loop` 的第二个元组元素来循环。实际上，变量绑定及其引用可以按任何顺序排列（但箭头语句的顺序对于效果来说是重要的）。
- 在 `rec` 中定义的任何从 `rec` 外部引用的变量都会在 `loop` 的第一个元组元素中返回。
重要的是要理解 `loop`（因此 `rec`）只是绑定变量。它不会保留值并在下次调用时传递回来 - `delay` 完成了这部分工作。由变量引用形成的循环必须由某种延迟箭头或延迟评估来打破，否则代码将陷入无限循环，就好像您在普通的 Haskell 中编写了 `let a = a+1` 一样。
如前所述，箭头语句（在 `-<` 之前）的箭头部分不能包含在 `proc` 中绑定的任何变量。有一个替代运算符 `-<<`，它消除了此限制。它要求箭头实现 `ArrowApply` 类型类。
注意
- ↑ 这种将箭头视为电路的解释松散地基于 Yampa 函数式反应式编程库。
- ↑ Ross Paterson 的论文，它指定了箭头 `proc` 表示法