像这样写下 foldLM 的定义需要什么样的知识或训练？

Question

最近，我正在尝试在我的一些实际案例生产系统中使用Haskell。 Haskell 类型系统真的给了我很大的帮助。例如，当我意识到我需要一些类型为

的函数时

f :: (Foldable t, Monad m) => ( a-> b -> m b) -> b -> t a -> m b

实际上有foldM、foldlM和foldrM等函数。

然而，真正让我震惊的是这些函数的定义，如：

foldlM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
foldlM f z0 xs = foldr f' return xs z0
  where f' x k z = f z x >>= k

所以函数 f' 的类型必须是：

f' :: a -> b -> b

根据 foldr 的要求，那么 b 必须属于 *-> m *，所以 foldlM 的整个定义才有意义。

另一个示例包括 liftA2 和 <*>

的定义

(<*>) :: f (a -> b) -> f a -> f b
(<*>) = liftA2 id

liftA2 :: (a -> b -> c) -> f a -> f b -> f c
liftA2 f x = (<*>) (fmap f x)

在查看源代码之前，我尝试了一些自己的解决方案。但是差距是如此之大，以至于我认为无论我将来写多少行代码，我都不可能想出这个解决方案。

所以我的问题是，在如此高度抽象的层次上进行推理需要什么样的知识或特定的数学分支。

我知道范畴论可能会提供一些帮助，我已经关注 this great lecture 很长时间并且仍在努力。

Answer 1

您不需要任何特定的数学知识来编写像 foldM 这样的函数。我在生产中使用 Haskell 已经 4 年了，而且我也在努力理解 foldM 的这个定义。但这主要是因为它写得不好。拜托，如果您看不懂一些晦涩的代码，请不要将其视为个人错误。这是 foldlM

的更具可读性的版本

foldlM
    :: forall t m a b .
       (Foldable t, Monad m)
    => (b -> a -> m b)  -- ^ Monadic action
    -> b                -- ^ Starting accumulator
    -> t a              -- ^ List of values
    -> m b              -- ^ Computation result inside a monad
foldlM f z xs = (foldr step pure xs) z
  where
    step :: a -> (b -> m b) -> b -> m b
    step cur next acc = do
        result <- f acc cur
        next result

这个功能仍然不是最简单的功能。主要是因为它具有 foldr 的非典型用法，其中中间累加器是一个函数。但是你可以看到一些使这样的定义更具可读性的可能：

关于函数参数的评论。
更好的参数名称（仍然简短且惯用，但它们至少更具可读性）。
内部函数的显式类型签名where（所以你知道参数的形状）。

看到这样的函数后，您现在可以执行等式推理技巧逐步展开定义，看看它是如何工作的。想出这些功能的能力来自于经验。我没有很强的数学家技能，这个函数也不是典型的 Haskell 函数。但是你练习得越多，效果就越好:)

Answer 2

总的来说，逻辑等等，我会想象。但是您也可以通过实践来学习它。 :) 随着时间的推移，您会注意到一些模式，掌握一些技巧。

像这样 foldr 加上一个额外的参数。有些人认为它折叠成函数，因此它们可以通过 . 和 id（sometimes are really <=< 和 return）、

组合

foldr g z xs  =  foldr ($) z . map g $ xs
              =  foldr (.) id (map g xs) z
         ~/=  foldr (<=<) return (map g xs) z
{-
  (\f -> f . f) :: (a -> a) -> (a -> a)

  (\f -> f <=< f) :: Monad m => (a -> m a) -> (a -> m a)
                            (still just a type, not a kind)
-}

有些人发现用更简单的句法术语更容易理解，如

foldr g z [a,b,c,...,n] s =
     g a (foldr g z [b,c,...,n]) s

所以当 g 在其第二个参数中是非严格的时，s 可以作为从左边传递的状态，即使我们在右边折叠，作为一个例如。

Answer 3

所以理解它的最好方法就是亲身实践。下面是使用 foldl 而不是 foldr 的 foldlM 的实现。这是一个很好的练习，尝试一下，稍后再看我建议的解决方案。该示例解释了我为实现它所做的所有推理，这可能与您的不同，并且可能有偏见，因为我已经知道使用函数累加器。

第 1 步：让我们试着用 foldl

来写 foldlM

-- this doesn't compile because f returning type is (m b) and not just (b) 
foldlM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
foldlM f z0 xs = foldl f z0 xs 

-- So let substitute f by some undefined f'
foldlM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
foldlM f z0 xs = foldl f' z0 xs
  where f' = undefined

-- cool, but f' should use f somehow in order to get the monadic behaviour
foldlM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
foldlM f z0 xs = foldl f' z0 xs
  where f' b a = f somethingIDontkNow

在这里你意识到 f' 是纯粹的，你需要提取 f 的结果来匹配类型。 'extract' monadic 值的唯一方法是使用 >>= 运算符，但是这样的运算符需要在使用后立即换行。

所以作为一个结论：每次你以 I'd like to fully unwrap this monad，放弃。方法不对

第 2 步：让我们尝试根据 foldl 编写 foldlM，但首先使用 [] 作为可折叠的，因为它很容易模式匹配（即我们实际上不需要使用 fold）

-- This is not very hard. It is pretty standard recursion schema. :)
foldlM' :: (Monad m) => (b -> a -> m b) -> b -> [a] -> m b
foldlM' f z0 []     = return z0
foldlM' f z0 (x:xs) = f z0 x >>= \c -> foldlM' f c xs

好的，这很简单。让我们将定义与列表

的通常 foldl 定义进行比较

foldlM' :: (Monad m) => (b -> a -> m b) -> b -> [a] -> m b
foldlM' f z0 []     = return z0
foldlM' f z0 (x:xs) = f z0 x >>= \c -> foldlM' f c xs

myfoldl :: (b -> a -> b) -> b -> [a] -> b
myfoldl f z0 []     = z0
myfoldl f z0 (x:xs) = foldl f (f z0 x) xs

太棒了！！他们几乎是一样的。微不足道的案例是关于完全相同的事情。递归的情况有点不同，你想写的更像：foldlM' f (f z0 x) xs。但是它并没有像步骤 1 那样编译，所以你可能会想 好吧，我不想应用 f，只是为了保持这样的计算并用 >>= 组合它.我想写点更像 foldlM' f (f z0 x >>=) xs 的东西，如果它有意义...

步骤3意识到你要累加的是一个函数组合，而不是一个结果。（这里我可能有偏见，因为我已经知道了，因为你已经发布了它）。

foldlM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
foldlM f z0 xs = foldl f' initFunc xs
  where initFunc = undefined :: b -> m b
        f'       = undefined :: (b -> m b) -> a -> (b -> m b) -- This type signature can be deduce because f' should be applied to initFunc and a's from t a.

根据 initFunc 的类型并使用我们从步骤 2（递归定义）中获得的知识，我们可以推断出 initFunc = return。知道f'应该用f和>>=.

就可以完成f'的定义

foldlM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
foldlM f z0 xs = foldl f' return xs z0
--                        ^^^^^^
--                        |- Initial value
  where f' b a = \bvalue -> b bvalue >>= \bresult -> f bresult a -- this is equivalent to (b >=> \result -> f result a) which captures the sequence behaviour of the implementation
--         ^      ^^^^^^                  ^^^^^^^
--         |      |                       |- This is the result of previous computation
--         |      |- f' should return a function b -> m b. Any time you have to return a function, start writing a lambda  
--         |- This b is the accumulated value and has type b -> m b
-- Following the types you can write this with enough practise

如您所见，做起来并不难。它需要练习，但我不是专业的 haskell 开发人员，我可以自己做，这是练习的问题

像这样写下 foldLM 的定义需要什么样的知识或训练？

What kind of knowledge or training is necessary for someone to write down the definition of foldlM like this?

haskell

fold

higher-order-functions