Haskell中的精确流量控制

Question

想法

你好!我正在尝试在Haskell中实现一个基于数据流意识形态的图像处理库.我有一个问题与我想要如何处理控制流程有关.

主要想法是介绍一个time.的time是Float,它可以在任何地方的代码访问(你可以认为它像约州单子,但有点滑稽).有趣的是,我们可以timeShift对结果使用操作,影响相应操作的时间.

一个例子最好解释这种情况.让我们使用以下数据流图:

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

和它的伪代码(它不是类似的 - 如果我们在这里使用或者记号,它不重要,这个想法应该是清楚的):

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是time我们想要运行的test功能.该timeShift函数影响其左侧的所有操作(在数据流图中) - 在这种情况下,函数readImage将运行两次 - 对于两个分支 - 较低的一个将使用帧5而上一个帧5*2 = 10.

问题

我在这里提供了一个非常简单的实现,它很有用,但我想解决一些注意事项.问题是,我想保持所有IO操作的顺序.以底部为例,这将阐明我的意思.

示例实施

下面是算法的示例实现和代码,它构造了以下数据流图:

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

代码:

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"

请注意正确的输出("(add (blur k10) (blur f5))",5)-这意味着,我们添加图片k10到f5-分别从第10和第5帧.

进一步的要求 我正在寻找一个解决方案,它允许用户编写简单的代码(比如在test函数中 - 它当然可以在Monad中),但我不希望他们手动处理时移逻辑.

结论

唯一的区别是IO动作执行的顺序.我希望保留IO操作的顺序,就像它们在test函数中编写一样.我试图实现使用的想法Countinuations,Arrows以及一些有趣的国家,但没有成功.

Answer 1

AMonad无法重新排序组成 和 的组件img1步骤img2

addImage :: (Monad m) => m [i] -> m [i] -> m [i]
addImage img1 img2 = do
    i1 <- img1
    i2 <- img2
    return $ i1 ++ i2

如果存在m [i]其结果取决于副作用的任何结果。AnyMonadIO m具有m [i]，其结果取决于副作用，因此您无法重新排序img1和的组成步骤img2。

上述脱糖为

addImage :: (Monad m) => m [i] -> m [i] -> m [i]
addImage img1 img2 =
    img1 >>=
        (\i1 ->
            img2 >>=
                (\i2 ->
                    return (i1 ++ i2)
                )
        )

让我们关注第一点>>=（记住这一点(>>=) :: forall a b. m a -> (a -> m b) -> m b）。专门针对我们的类型，这是(>>=) :: m [i] -> ([i] -> m [i]) -> m [i]. 如果我们要实现它，我们必须写类似的东西

(img1 :: m [i]) >>= (f :: [i] -> m [i]) = ... 

为了执行任何操作f，我们需要将其传递给[i]. [i]我们唯一正确的就是被困在里面img1 :: m [i]。我们需要 的结果来img1对 做任何事情f。现在有两种可能性。在不执行其副作用的情况下，我们要么可以或不能确定结果。img1我们将检查这两种情况，从我们不能的时候开始。

不能

当我们无法确定img1不执行其副作用的结果时，我们只有一个选择——我们必须执行img1其所有副作用。我们现在有一个[i]，但所有img1s 的副作用都已经执行了。我们无法执行img2某些副作用之前的任何副作用，img1因为副作用img1已经发生了。

能

img1如果我们能够在不执行其副作用的情况下确定结果，那么我们很幸运。我们找到 的结果img1并将其传递给f，获得我们想要的新m [i]结果。我们现在可以检查两者的副作用img1和 新m [i]的并对它们重新排序（尽管这里有一个关于 的结合律的巨大警告>>=）。

手头的问题

由于这适用于我们的情况，对于任何MonadIO，存在以下情况，在不执行其副作用的情况下无法确定其结果，这使我们牢牢处于无法对副作用进行重新排序的情况。

counterExample :: (MonadIO m) => m String
counterExample = liftIO getLine

还有许多其他反例，例如类似readImage1或 的任何东西readImage2必须实际从 读取图像IO。