将高阶函数提升为monad

Question

假设我有一个更高阶的函数,它使用它从函数参数中检索的值执行一些计算.

f :: a -> (b -> c) -> d

其中a,b,c,d是一些具体类型.

然后我有这种类型的功能

g :: b -> m c

其中m是一些monad.

现在有一种方法可以使用g和f.那就是把f变成一个产生m d代替的函数,d并且可以使用g作为它的第二个参数？

一个具体的例子是m是IO monad,f是计算从其功能参数检索的n个数字的总和的函数,g从标准输入读取数字.

f n g = sum $ map g (1..n)
g :: Int -> IO Int
g _ = readLn

我知道有一些函数可以将标准输入转换为惰性列表,这可以解决这个问题,但我的实际情况并不那么简单.

假设我有一个在图上做某事的算法.该算法使用功能参数来确定节点的邻居.这样我就可以有多个图形实现.

现在我想将此算法与非确定性图形(List monad)或未完全已知的图形(可能是monad)一起使用.我知道我可以重写算法使用monads然后使用身份monad作为基本情况,但这是唯一的方法吗？我认为编写没有monad的算法会更容易.

这种行为可能吗？我找不到它不应该的原因,但我无法找到一种方法.

Answer 1

所以你想要例如得出mapM给定的map.那就是你有一个简单的map:

map  :: (a -> b) -> [a] -> [b]

并且你想把它用作mapmonadic结构

mapM :: Monad m => (a -> m b) -> [a] -> m [b]

我们可以计算出mapM从map通过映射的IO操作,然后对其进行测序,这样的:

mapM f xs = sequence (map f xs)

现在我们有了更通用的形式,我们可以map通过mapM在Identity monad中运行来获取.然后经典map是mapM在身份monad.

> let g :: Int -> Identity Int
      g a = return (a^2)

哪里:

> runIdentity $ mapM g [1..10]
[1,4,9,16,25,36,49,64,81,100]

所以,是的,你需要将你的高阶函数归为正确的级别 - 无论是monad,functor还是applicative,那么你可以自由地用其他计算概念来代替,包括身份.

您可以通过转换函数的AST来机械地将任何纯函数重写为其monadic:

• 将结果值包装在中 return
• 识别新的monadic子表达式,并绑定它们.
• 用monadic bind替换变量绑定; 或者,如果它是适用的:
• 用monad中的应用程序替换应用程序(小心)

例如

map f []     = []
map f (x:xs) = f x : map f xs

至(应用风格)

mapM f []     = return []
mapM f (x:xs) = (:) <$> f x <*> mapM' f xs

或不太清楚,并修复评估顺序:

mapM f []     = return []
mapM f (x:xs) = do
    v  <- f x
    vs <- mapM f xs
    return (v:vs)

我们可以使用地图的应用程序,因为不需要monadic绑定来将结果从一步传递到下一步.不是这样的foldl:

foldl        :: (a -> b -> a) -> a -> [b] -> a
foldl f z0 xs0 = lgo z0 xs0
     where
        lgo z []     =  z
        lgo z (x:xs) = lgo (f z x) xs

foldlM :: Monad m => (a -> b -> m a) -> a -> [b] -> m a
foldlM f z0 xs0 = lgo z0 xs0
     where
        lgo z []     = return z
        lgo z (x:xs) = do
            v <- f z x
            lgo v xs