在Haskell precise流量控制 [英] Precise flow control in Haskell

问题描述

思想

您好！我想要的图像处理库基于数据流的意识形态在Haskell实现。我有连接到我希望如何处理控制流程的问题。

Hello! I'm trying to implement in Haskell an image processing library based on dataflow ideology. I've got a problem connected to how I want to handle the flow of control.

主要思路是引入时间。该时间是浮动，这可能会在code任何地方访问（你可以认为它像有关国家单子，但有点滑稽）。关于它的有趣的事情是，我们可以使用结果时间转换运行，影响相应的操作会看到的时间。

The main idea is to introduce a time. The time is a Float, which could be accessed anywhere in the code (you can think of it like about State monad, but a little funnier). The funny thing about it, is that we can use timeShift operation on results, affecting the time corresponding operations would see.

一个例子是最好的解释这种情况。让我们用下面的数据流图：

An example would be best to explain this situation. Lets use following dataflow diagram:

--               timeShift(*2) --
--              /                 \
-- readImage --                    addImages -> out
--              \                 /
--                blur ----------

和伪code （其中DEOS没有类型检查 - 它并不重要，如果我们用做或者让这里的符号，这个想法应该清楚）：

and its pseudocode (which deos not typecheck - its not important if we use do or let notation here, the idea should be clear):

test = do
    f      <- frame
    a      <- readImage $ "test" + show f + ".jpg"
    aBlur  <- blur a
    a'     <- a.timeShift(*2)
    out    <- addImage aBlur a'

main = print =<< runStateT test 5

在 5 是时间我们要运行的测试与功能。该时间转换功能会影响它的左侧的所有操作（在数据流图） - 在这种情况下，函数 readImage 将被运行两次 - 为两个分支 - 较低的人会使用帧 5 和上一帧 5 * 2 = 10 。

The 5 is the time we want to run the test function with. The timeShift function affects all the operations on the left of it (in the dataflow diagram) - in this case the function readImage would be run twice - for both branches - the lower one would use frame 5 and the upper one frame 5*2 = 10.

问题

我在这里提供一个非常简单的实现，是伟大的工程，但有一些注意事项我要解决的问题。现在的问题是，我要保留所有的IO操作的顺序。看底部的例子，这将澄清我的意思。

I'm providing here a very simple implementation, that works great, but has some caveats I want to solve. The problem is, that I want to keep the order of all IO operations. Look at the bottom for example, which will clarify what I mean.

样品实施

下面是算法和code，它构建了以下数据流图的实现：

Below is a sample implementation of the algorithm and a code, which constructs following dataflow graph:

-- A --- blur --- timeShift(*2) --
--                                \
--                                 addImages -> out
--                                /
-- B --- blur --------------------

在code：

the code:

import Control.Monad.State

-- for simplicity, lets assume an Image is just a String
type Image = String

imagesStr = ["a0","b1","c2","d3","e4","f5","g6","h7","i8","j9","k10","l11","m12","n13","o14","p15","q16","r17","s18","t19","u20","v21","w22","x23","y24","z25"]
images = "abcdefghjiklmnoprstuwxyz"

--------------------------------
-- Ordinary Image processing functions

blurImg' :: Image -> Image
blurImg' img = "(blur " ++ img ++ ")"

addImage' :: Image -> Image -> Image
addImage' img1 img2 = "(add " ++ img1 ++ " " ++ img2 ++ ")"

--------------------------------
-- Functions processing Images in States

readImage1 :: StateT Int IO Image
readImage1 = do
    t <- get
    liftIO . putStrLn $ "[1] reading image with time: " ++ show t
    return $ imagesStr !! t

readImage2 :: StateT Int IO Image
readImage2 = do
    t <- get
    liftIO . putStrLn $ "[2] reading image with time: " ++ show t
    return $ imagesStr !! t

blurImg :: StateT Int IO Image -> StateT Int IO Image
blurImg img = do
    i <- img
    liftIO $ putStrLn "blurring"
    return $ blurImg' i

addImage :: StateT Int IO Image -> StateT Int IO Image -> StateT Int IO Image
addImage img1 img2 = do
    i1 <- img1
    i2 <- img2
    liftIO $ putStrLn "adding images"
    return $ addImage' i1 i2


timeShift :: StateT Int IO Image -> (Int -> Int) -> StateT Int IO Image
timeShift img f = do
    t <- get
    put (f t)
    i <- img
    put t
    return i

test = out where
    i1   = readImage1
    j1   = readImage2

    i2   = blurImg i1
    j2   = blurImg j1

    i3   = timeShift i2 (*2)
    out  = addImage i3 j2


main = do
    print =<< runStateT test 5
    print "end"

的输出是：

[1] reading image with time: 10
blurring
[2] reading image with time: 5
blurring
adding images
("(add (blur k10) (blur f5))",5)
"end"

和应该是：

[1] reading image with time: 10
[2] reading image with time: 5
blurring
blurring
adding images
("(add (blur k10) (blur f5))",5)
"end"

请注意正确的输出（（添加（模糊K10）（模糊F5）），5） - 这意味着，我们添加的图像 K10 到 F5 - 分别从第10和第5帧

Please note that the correct output is ("(add (blur k10) (blur f5))",5) - which means, that we added image k10 to f5 - from respectively 10th and 5th frame.

进一步要求 我正在寻找一个解决方案，这将允许用户编写简单的code（如在测试功能 - 当然它可能是一个Monad的），但我不想让他们手工处理时移逻辑。

Further requirements I'm looking for a solution, which would allow users to write simple code (like in test function - it could of course be in a Monad), but I do not want them to handle the time-shifting logic by hand.

结论

唯一不同的是IO操作执行的顺序。我很想preserve就像他们都写在测试功能IO操作的顺序。我试图用实现的想法 Countinuations ，箭头和一些有趣的国家，但都没有成功。

The only difference is the order of IO actions execution. I would love to preserve the order of the IO actions just like they are written in the test function. I was trying to implement the idea using Countinuations, Arrows and some funny states, but without success.

推荐答案

数据流，并在Haskell功能反应编程库通常用应用型方面或箭头。这些都是不那么普遍比单子抽象计算秒 - 的应用型和箭头类型类不公开的一种方式计算的结构依赖于其它的计算的结果。其结果是，库只露出这些类型类可以独立地执行这些计算的推理运算的在库中的结构。我们会解决你的问题而言的应用型类型类

Dataflow and functional reactive programming libraries in Haskell are usually written in terms of Applicative or Arrow. These are abstractions for computations that are less general than Monads - the Applicative and Arrow typeclasses do not expose a way for the structure of computations to depend on the results of other computations. As a result, libraries exposing only these typeclasses can reason about the structure of computations in the library independently of performing those computations. We will solve your problem in terms of the Applicative typeclass

class Functor f => Applicative f where
    -- | Lift a value.
    pure :: a -> f a    
    -- | Sequential application.
    (<*>) :: f (a -> b) -> f a -> f b

应用型允许图书馆用户作出新的计算与纯，与<$ C $现有的计算操作C> FMAP （从的函子）和＆LT组成的计算在一起; *＆GT; ，使用一个计算结果作为输入另一个。它不允许库用户进行的计算，使得另一计算，然后使用直接该计算的结果;有没有办法，用户可以写加入:: F（FA） - ＆GT; F A 。这个限制将继续我们的库运行到我在其他的答案描述的问题。

Applicative allows a library user to make new computations with pure, operate on existing computations with fmap (from Functor) and compose computations together with <*>, using the result of one computation as an input for another. It does not allow a library user to make a computation that makes another computation and then use the result of that computation directly; there's no way a user can write join :: f (f a) -> f a. This restriction will keep our library from running into the problem I described in my other answer.

您的例子的问题是相当复杂的，所以我们要拉出一堆高水平哈斯克尔的技巧，使自己的一些新的问题。前两个招数，我们要拉出来是变压器和的免费的数据类型。变压器是一种需要的类型与像的函子 S，应用型 s或的一种类型单子和产生新的类型跟实物一样。

Your example problem is quite involved, so we are going to pull out a bunch of high level Haskell tricks, and make a few new ones of our own. The first two tricks we are going to pull out are transformers and free data types. Transformers are types that take types with a kind like that of Functors, Applicatives or Monads and produce new types with the same kind.

变形金刚通常如下所示双击的例子。 双击可以采取任何的函子或应用型或单子并进行版本的它总是拥有两个值，而不是一个

Transformers typically look like the following Double example. Double can take any Functor or Applicative or Monad and make a version of it that always holds two values instead of one

newtype Double f a = Double {runDouble :: f (a, a)}

免费的数据类型的变压器是做两件事情。首先，鉴于基础类型的一些简单的属性增益令人振奋的新特性的转换类型。该免费 单子提供了单子给出任何的函子，和自由应用型，鸭，使一个应用型出任何的函子。另一件事是免费的类型做的是他们的帧间preTER尽可能的免费的执行。下面是自由应用型，鸭的类型，自由单子，免费，以及免费的单子主变差，孚瑞特。免费的单子变压器提供了一个单子变压器免费给予了的函子

Free data types are transformers that do two things. First, given some simpler property of the underlying type the gain new exciting properties for the transformed type. The Free Monad provides a Monad given any Functor, and the free Applicative, Ap, makes an Applicative out of any Functor. The other thing "free" types do is they "free" the implementation of the interpreter as much as possible. Here are the types for the free Applicative, Ap, the free Monad, Free, and the free monad transfomer, FreeT. The free monad transformer provides a monad transformer for "free" given a Functor

-- Free Applicative
data Ap f a where
    Pure :: a -> Ap f a
    Ap   :: f a -> Ap f (a -> b) -> Ap f b

-- Base functor of the free monad transformer
data FreeF f a b
    = Pure a    
    | Free (f b)    

-- Free monad transformer
newtype FreeT f m a = FreeT {runFreeT :: m (FreeF f a (FreeT f m a)}

-- The free monad is the free monad transformer applied to the Identity monad
type Free f = FreeT f Identity

下面是我们的目标草图 - 我们要为合并计算，其中，在底部，允许提供一个应用型接口单子 IC计算。我们想自由间preTER尽可能使之能有希望重新排列计算。要做到这一点，我们将结合双方的自由应用型和自由单子变压器。

Here's a sketch of our goal - we want to provide an Applicative interface for combining computations, which, at the bottom, allows Monadic computations. We want to "free" the interpreter as much as possible so that it can hopefully reorder computations. To do this, we will be combining both the free Applicative and the free monad transformer.

我们希望有一个应用型接口，和一个最容易提出的是一个我们可以得到自由，它很好地对准释放interpeter的球门 越多越好。这表明我们的类型是要看起来像

We want an Applicative interface, and the easiest one to make is the one we can get for "free", which aligns nicely with out goal of "freeing the interpeter" as much as possible. This suggests our type is going to look like

Ap f a

对于一些的函子 F 任何 A 。我们希望底层的计算是对一些单子和单子是仿函数，但是我们希望自由的跨preTER高达posssible。我们会抓住免费的单子变压器作为底层仿函数鸭，给我们

for some Functor f and any a. We'd like the underlying computation to be over some Monad, and Monads are functors, but we'd like to "free" the interpreter as much as posssible. We'll grab the free monad transformer as the underlying functor for Ap, giving us

Ap (FreeT f m) a

对于一些的函子 F ，有些单子 M ，以及任何 A 。我们知道单子 M 很可能将是 IO ，但我们会离开我们的code尽可能地通用。我们只需要提供的函子为孚瑞特。所有 Applicatives 是函子，所以鸭本身可用于为 F ，我们会写类似

for some Functor f, some Monad m, and any a. We know the Monad m is probably going to be IO, but we'll leave our code as generic as possible. We just need to provide the Functor for FreeT. All Applicatives are Functors, so Ap itself could be used for f, we'd write something like

type ApT m a = Ap (FreeT (ApT m) m) a

这使编译器配合，这样反而我们将移动设备的鸭内定义

This gives the compiler fits, so instead we'll mover the Ap inside and define

newtype ApT m a = ApT {unApT :: FreeT (Ap (ApT m)) m a}

我们会得到某些情况下，这和一个插曲后讨论它的真正动机。

We'll derive some instances for this and discuss its real motivation after an interlude.

要运行所有这code，你需要以下。该地图和 Control.Concurrent 只需要共享的计算，稍后更多了。

To run all of this code, you'll need the following. The Map and Control.Concurrent are only needed for sharing computations, more on that much later.

{-# LANGUAGE GADTs #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}

module Main where

import Control.Monad.Trans.Class
import Control.Monad.IO.Class

import Control.Monad.Trans.Reader
import Control.Applicative

import Control.Applicative.Free hiding (Pure)
import qualified Control.Applicative.Free as Ap (Ap(Pure))
import Control.Monad.Trans.Free

import qualified Data.Map as Map
import Control.Concurrent

馅它

我误导你在previous部分，pretended发现 APT 从resoning这个问题。我却发现 APT 通过尝试任何事情，一切尝试的东西单子 IC计算成应用型，并能够控制他们的订单，当它走了出来。很长一段时间，我试图解决如何实施 mapApM （下）为了写 flipImage （我更换你的模糊）。这里的 APT 单子变压器在其所有的荣耀。这是为了用作的函子为鸭，并用鸭作为自己的的函子为孚瑞特，可以神奇的东西值到应用型应该不会似乎不可能。

Stuffing it

I mislead you in the previous section, and pretended to discover ApT from resoning about the problem. I actually discovered ApT by trying anything and everything to try to stuff Monadic computations into an Applicative and be able to control their order when it came out. For a long time, I was trying to solve how to implement mapApM (below) in order to write flipImage (my replacement for your blur). Here's the ApT Monad transformer in all its glory. It's intended to be used as the Functor for an Ap, and, by using Ap as its own Functor for FreeT, can magically stuff values into an Applicative that shouldn't seem possible.

newtype ApT m a = ApT {unApT :: FreeT (Ap (ApT m)) m a}
     deriving (Functor, Applicative, Monad, MonadIO)

这可能源自孚瑞特更实例，这些只是我们需要的人。它不能获得 MonadTrans ，但我们可以做到这一点自己：

It could derive even more instances from FreeT, these are just the ones we need. It can't derive MonadTrans, but we can do that ourselves:

instance MonadTrans ApT where
    lift = ApT . lift

runApT :: ApT m a -> m (FreeF (Ap (ApT m)) a (FreeT (Ap (ApT m)) m a))
runApT = runFreeT . unApT

真正的美 APT 是我们可以写一些看似不可能code像

The real beauty of ApT is we can write some seemingly impossible code like

stuffM :: (Functor m, Monad m) => m (ApT m a) -> ApT m a
stuffMAp :: (Functor m, Monad m) => m (ApT m a) -> Ap (ApT m) a

在 M 在外面disappeares，连成鸭这仅仅是应用型。

The m on the outside disappeares, even into Ap that's merely Applicative.

此工作，因为功能，每一个都可以从东西它上面的函数的输出入它下面的函数的输入端的下一周期。第一个函数开头的 APT MA ，和一个最后一个结束。 （这些定义都没有计划的一部分）

This works because of the following cycle of functions, each of which can stuff the output from the function above it into the input of the function below it. The first function starts with an ApT m a, and the last one ends with one. (These definitions aren't part of the program)

liftAp' :: ApT m a ->
           Ap (ApT m) a
liftAp' = liftAp

fmapReturn :: (Monad m) =>
               Ap (ApT m) a ->
               Ap (ApT m) (FreeT (Ap (ApT m)) m a)
fmapReturn = fmap return

free' :: Ap (ApT m) (FreeT (Ap (ApT m)) m a) ->
         FreeF (Ap (ApT m)) a (FreeT (Ap (ApT m)) m a)
free' = Free

pure' :: a ->
         FreeF (Ap (ApT m)) a (FreeT (Ap (ApT m)) m a)
pure' = Pure

return' :: (Monad m) =>
           FreeF (Ap (ApT m)) a (FreeT (Ap (ApT m)) m a) ->
           m (FreeF (Ap (ApT m)) a (FreeT (Ap (ApT m)) m a))
return' = return

freeT :: m (FreeF (Ap (ApT m)) a (FreeT (Ap (ApT m)) m a)) ->
         FreeT (Ap (ApT m)) m a
freeT = FreeT

apT :: FreeT (Ap (ApT m)) m a ->
       ApT m a
apT = ApT

这让我们写

-- Get rid of an Ap by stuffing it into an ApT.
stuffAp :: (Monad m) => Ap (ApT m) a -> ApT m a
stuffAp = ApT . FreeT . return . Free . fmap return

-- Stuff ApT into Free
stuffApTFree :: (Monad m) => ApT m a -> FreeF (Ap (ApT m)) a (FreeT (Ap (ApT m)) m a)
stuffApTFree = Free . fmap return . liftAp

-- Get rid of an m by stuffing it into an ApT
stuffM :: (Functor m, Monad m) => m (ApT m a) -> ApT m a
stuffM = ApT . FreeT . fmap stuffApTFree

-- Get rid of an m by stuffing it into an Ap
stuffMAp :: (Functor m, Monad m) => m (ApT m a) -> Ap (ApT m) a
stuffMAp = liftAp . stuffM

和对工作的一个变压器堆栈一些实用功能

And some utility functions for working on a transformer stack

mapFreeT :: (Functor f, Functor m, Monad m) => (m a -> m b) -> FreeT f m a -> FreeT f m b
mapFreeT f fa = do
    a <- fa
    FreeT . fmap Pure . f . return $ a

mapApT :: (Functor m, Monad m) => (m a -> m b) -> ApT m a -> ApT m b
mapApT f = ApT . mapFreeT f . unApT

mapApM :: (Functor m, Monad m) => (m a -> m b) -> Ap (ApT m) a -> Ap (ApT m) b
mapApM f = liftAp . mapApT f . stuffAp

我们要开始写我们的示例图像处理器，但是首先我们需要采取另一种分流，以解决一个硬性要求。

We'd like to start writing our example image processors, but first we need to take another diversion to address a hard requirement.

您第一个示例说明

--               timeShift(*2) --
--              /                 \
-- readImage --                    addImages -> out
--              \                 /
--                blur ----------

这意味着 readImage 的结果应该之间共享模糊和时光平移（* 2）。我认为这意味着该结果 readImage 只能每次计算一次。

implying that the result of readImage should be shared between blur and timeShift(*2). I take this to mean that the results of readImage should only be computed once for each time.

应用型是没有强大到足以捕捉到这一点。我们会成为一个新的类型类重新present计算，其输出可分为多个相同的视频流。

Applicative isn't powerful enough to capture this. We'll make a new typeclass to represent computations whose output can be divided into multiple identical streams.

-- The class of things where input can be shared and divided among multiple parts
class Applicative f => Divisible f where
    (<\>) :: (f a -> f b) -> f a -> f b

我们会作出一个变压器，增加了这一功能，以现有的应用型取值

We'll make a transformer that adds this capability to existing Applicatives

-- A transformer that adds input sharing
data LetT f a where
    NoLet :: f a -> LetT f a
    Let   :: LetT f b -> (LetT f b -> LetT f a) -> LetT f a

和提供一些实用功能和实例吧。

And provide some utility functions and instances for it

-- A transformer that adds input sharing
data LetT f a where
    NoLet :: f a -> LetT f a
    Let   :: LetT f b -> (LetT f b -> LetT f a) -> LetT f a

liftLetT :: f a -> LetT f a
liftLetT = NoLet

mapLetT :: (f a -> f b) -> LetT f a -> LetT f b
mapLetT f = go
    where
        go (NoLet a) = NoLet (f a)
        go (Let b g) = Let b (go . g)

instance (Applicative f) => Functor (LetT f) where
    fmap f = mapLetT (fmap f)

-- I haven't checked that these obey the Applicative laws.
instance (Applicative f) => Applicative (LetT f) where
    pure = NoLet . pure
    NoLet f <*> a = mapLetT (f <*>) a
    Let c h <*> a = Let c ((<*> a) . h)   

instance (Applicative f) => Divisible (LetT f) where
    (<\>) = flip Let

图像处理器

使用我们所有的变压器的地方，我们就可以开始写我们的图像处理器。在我们的堆栈的底部，我们有我们的 APT 从前面的部分。

Image processors

With all of our transformers in place, we can start writing our image processors. At the bottom of our stack we have our ApT from an earlier section

Ap (ApT IO)

该计算需要能够读取环境的时间，因此我们将添加一个 READER™软件为

ReaderT Int (Ap (ApT IO))

最后，我们希望能够分享计算，所以我们将添加了快报变压器顶部，使整个键入 IP 我们的图像处理器

Finally, we'd like to be able to share computations, so we'll add out LetT transformer on top, giving the entire type IP for our image processors

type Image = String
type IP = LetT (ReaderT Int (Ap (ApT IO)))

我们会阅读 IO 图像。 函数getline 让有趣的互动例子。

We'll read images from IO. getLine makes fun interactive examples.

readImage :: Int -> IP Image
readImage n = liftLetT $ ReaderT (\t -> liftAp . liftIO $ do
    putStrLn $  "[" ++ show n ++ "] reading image for time: " ++ show t
    --getLine
    return $ "|image [" ++ show n ++ "] for time: " ++ show t ++ "|"
    )

我们可以转移投入的时间

We can shift the time of inputs

timeShift :: (Int -> Int) -> IP a -> IP a
timeShift f = mapLetT shift
    where
        shift (ReaderT g) = ReaderT (g . f)  

添加多张图片一起

addImages :: Applicative f => [f Image] -> f Image
addImages = foldl (liftA2 (++)) (pure [])

和翻转图像pretending使用一些卡住了在 IO 库。我无法弄清楚如何模糊字符串...

And flip images pretending to use some library that's stuck in IO. I couldn't figure out how to blur a string...

inIO :: (IO a -> IO b) -> IP a -> IP b
inIO = mapLetT . mapReaderT . mapApM        

flipImage :: IP [a] -> IP [a]
flipImage = inIO flip'
    where
        flip' ma = do
            a <- ma
            putStrLn "flipping"
            return . reverse $ a

国米preting快报

我们的快报共享的结果是我们的变压器堆栈的顶部。我们需要跨preT它得到在它下面的计算。国米preT 快报我们需要一种方式来分享成果 IO ，其中 memoize的提供，并且interpeter，消除从堆栈顶部的快报变压器。

Interpreting LetT

Our LetT for sharing results is at the top of our transformer stack. We'll need to interpret it to get at the computations underneath it. To interpret LetT we will need a way to share results in IO, which memoize provides, and an interpeter that removes the LetT transformer from the top of the stack.

要分享，我们需要存储它们在某处计算，这个 memoize的秒的 IO 计算的 IO ，确保它只会发生一次，甚至可以跨多个线程。

To share computations we need to store them somewhere, this memoizes an IO computation in IO, making sure it happens only once even across multiple threads.

memoize :: (Ord k) => (k -> IO a) -> IO (k -> IO a)
memoize definition = do
    cache <- newMVar Map.empty
    let populateCache k map = do
        case Map.lookup k map of
            Just a -> return (map, a)
            Nothing -> do
                a <- definition k
                return (Map.insert k a map, a)        
    let fromCache k = do
        map <- readMVar cache
        case Map.lookup k map of
            Just a -> return a
            Nothing -> modifyMVar cache (populateCache k)
    return fromCache

为了国米preT一个让，我们需要评估的基本 APT IO 来纳入该定义的让绑定。由于计算的结果依赖于从阅读环境的 READER™软件，我们将采用与 READER™软件处理到这一步。更复杂的方法是使用变压器类，但变压器类应用型是一个不同的问题的一个话题。

In order to interpret a Let, we need an evaluator for the underlying ApT IO to incorporate into the definitions for the Let bindings. Since the result of computations depends on the environment read from the ReaderT, we will incorporate dealing with the ReaderT into this step. A more sophisticated approach would use transformer classes, but transformer classes for Applicative is a topic for a different question.

compileIP :: (forall x. ApT IO x -> IO x) ->  IP a -> IO (Int -> ApT IO a)
compileIP eval (NoLet (ReaderT f)) = return (stuffAp . f)
compileIP eval (Let b lf) = do
            cb <- compileIP eval b
            mb <- memoize (eval . cb)
            compileIP eval . lf . NoLet $ ReaderT (liftAp . lift . mb)

国米preting APT

我们的跨preTER使用以下国家来避免需要偷看里面的 AST ，孚瑞特和 FreeF 所有的时间。

Interpreting ApT

Our interpreter uses the following State to avoid needing to peek inside AsT, FreeT, and FreeF all the time.

data State m a where
    InPure :: a -> State m a
    InAp :: State m b -> State m (b -> State m a) -> State m a
    InM :: m a -> State m a

instance Functor m => Functor (State m) where
    fmap f (InPure a) = InPure (f a)
    fmap f (InAp b sa) = InAp b (fmap (fmap (fmap f)) sa)
    fmap f (InM  m)  = InM  (fmap f m)

Interpereting 鸭是比它看起来更难。我们的目标是把数据在 Ap.Pure ，并把它放在 InPure 和数据是在鸭，并把它放在 INAP 。 除preTAP 实际需要与更大的类型，每次去时称自己陷入了更深的鸭;功能不断拿起另一种说法。第一个参数 T 提供了一种方法来简化这些否则爆炸的类型。

Interpereting Ap is harder than it looks. The goal is to take data that's in Ap.Pure and put it in InPure and data that's in Ap and put it in InAp. interpretAp actually needs to call itself with a larger type each time it goes into a deeper Ap; the function keeps picking up another argument. The first argument t provides a way to simplify these otherwise exploding types.

interpretAp :: (Functor m) => (a -> State m b) -> Ap m a -> State m b
interpretAp t (Ap.Pure a) = t a
interpretAp t (Ap mb ap) = InAp sb sf
    where
        sb = InM mb
        sf = interpretAp (InPure . (t .)) $ ap

interperetApT 获取数据了的APT ，孚瑞特和 FreeF ，进入状态M

interperetApT gets data out of ApT, FreeT, and FreeF and into State m

interpretApT :: (Functor m, Monad m) => ApT m a -> m (State (ApT m) a)
interpretApT = (fmap inAp) . runApT
    where
        inAp (Pure a) = InPure a
        inAp (Free ap) = interpretAp (InM . ApT) $ ap

通过这些简单的跨preting件，我们可以为跨preting成果的战略。每一个策略是从内部preTER的国家来一个新的国家，可能出现的副作用发生在函数方式。的顺序的策略选择执行的副作用在确定的副作用的顺序。我们会让两个示例策略。

With these simple interpreting pieces we can make strategies for interpreting results. Each strategy is a function from the interpreter's State to a new State, with possible side effect happening on the way. The order the strategy chooses to execute side effects in determines the order of the side effects. We'll make two example strategies.

第一个策略执行上的一切，已经准备好进行计算，并结合结果当他们准备好只差一步。这可能是你想要的策略。

The first strategy performs only one step on everything that's ready to be computed, and combines results when they are ready. This is probably the strategy that you want.

stepFB :: (Functor m, Monad m) => State (ApT m) a -> m (State (ApT m) a)
stepFB (InM ma)   = interpretApT ma
stepFB (InPure a) = return (InPure a)
stepFB (InAp b f) = do
    sf <- stepFB f
    sb <- stepFB b
    case (sf, sb) of
        (InPure f, InPure b) -> return (f b)
        otherwise            -> return (InAp sb sf)

这等策略进行所有的计算，只要它知道它们。它执行他们都在一个单一的通行证。

This other strategy performs all the calculations as soon as it knows about them. It performs them all in a single pass.

allFB :: (Functor m, Monad m) => State (ApT m) a -> m (State (ApT m) a)
allFB (InM ma) = interpretApT ma
allFB (InPure a) = return (InPure a)
allFB (InAp b f) = do
    sf <- allFB f
    sb <- allFB b
    case (sf, sb) of
        (InPure f, InPure b) -> return (f b)
        otherwise            -> allFB (InAp sb sf)

很多很多其他的策略是可行的。

Many, many other strategies are possible.

我们可以运行它，直到它会产生一个结果评价的战​​略。

We can evaluate a strategy by running it until it produces a single result.

untilPure :: (Monad m) => ((State f a) -> m (State f a)) -> State f a -> m a
untilPure s = go
    where
        go state =
            case state of
                (InPure a) -> return a
                otherwise  -> s state >>= go

执行INTE preTER

要执行跨preTER，我们需要一些示例数据。这里有一些有趣的例子。

Executing the intepreter

To execute the interpreter, we need some example data. Here are a few interesting examples.

example1  = (\i -> addImages [timeShift (*2) i, flipImage i]) <\> readImage 1
example1' = (\i -> addImages [timeShift (*2) i, flipImage i, flipImage . timeShift (*2) $ i]) <\> readImage 1
example1'' = (\i -> readImage 2) <\> readImage 1
example2 = addImages [timeShift (*2) . flipImage $ readImage 1, flipImage $ readImage 2]

在快报除preTER需要知道使用绑定的值是什么评估，所以我们只定义一次，我们的评估。一个除pretApT 揭开序幕评估通过找到最初的国家间preTER 。

The LetT interpreter needs to know what evaluator to use for bound values, so we'll define our evaluator only once. A single interpretApT kicks off the evaluation by finding the initial State of the interpreter.

evaluator :: ApT IO x -> IO x
evaluator = (>>= untilPure stepFB) . interpretApT

我们将编译例2 ，基本上是你的榜样，并运行时间5。

We'll compile example2, which is essentially your example, and run it for time 5.

main = do
    f <- compileIP evaluator example2
    a <- evaluator . f $ 5
    print a

这几乎产生期望的结果，所有的读取任何翻转之前发生的事情。

Which produces almost the desired result, with all reads happening before any flips.

[2] reading image for time: 5
[1] reading image for time: 10
flipping
flipping
"|01 :emit rof ]1[ egami||5 :emit rof ]2[ egami|"

这篇关于在Haskell precise流量控制的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！