haskell - 将高阶函数提升到 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)或不完全已知的图(Maybe monad)一起使用。我知道我可以重写算法以使用单子(monad)，然后将身份单子(monad)用于基本情况，但这是唯一的方法吗？我认为在没有单子(monad)的情况下编写算法会更容易。

这种行为可能吗？我找不到不应该这样做的原因，但我无法找到解决方法。

Answer 1

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

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

并且您想将其用作 map on monadic structures

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

我们可以计算 mapM来自 map通过映射 IO 操作，然后对它们进行排序，因此:

mapM f xs = sequence (map f xs)

现在我们有了更一般的形式，我们可以返回 map通过运行 mapM在 the 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)、仿函数还是应用程序，然后你可以自由地替换其他计算概念，包括恒等式。

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

将结果值包装在 return 中

识别新的单子(monad)子表达式，并绑定(bind)它们。

用一元绑定(bind)替换变量绑定(bind)；或者，如果适用:

用 monad 中的应用程序替换应用程序(小心)

例如。

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

To(应用风格)

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)

我们可以为 map 使用应用程序，因为不需要单子(monad)绑定(bind)来将结果从一步传递到下一步。 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