5

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

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

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

然后我有这种类型的功能

g :: b -> m c

其中 m 是一些单子。

现在有一种方法可以将 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）一起使用。我知道我可以重写算法以使用单子，然后将身份单子用于基本情况，但这是唯一的方法吗？我认为在没有单子的情况下编写算法会更容易。

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

4

1 回答 1

7

所以你想例如派生mapMgiven map。那就是你有一个简单的map：

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

并且您想将其用作map单子结构 

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

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

mapM f xs = sequence (map f xs)

现在我们有了更一般的形式，我们可以通过在Identity monadmap中运行来返回。然后经典在身份单子中。mapMmapmapM

> 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]

所以是的，你需要将你的高阶函数泛化到正确的水平——无论是单子、函子还是应用程序，然后你可以自由地替换其他计算概念，包括恒等式。

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

  • 将结果值包装在return
  • 识别新的单子子表达式，并绑定它们。
  • 用一元绑定替换变量绑定；或者，如果适用：
  • 用 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 使用应用程序，因为不需要单子绑定来将结果从一步传递到下一步。不是这样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
于 2013-03-03T12:46:17.907 回答