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` 表示法