某人写下这样的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)

在探究源代码之前，我尝试了一些自己的解决方案。但是差距是如此之大，以至于我以后再写多少行代码都无法提出这种解决方案。

所以我的问题是，某人在如此高度抽象的水平上进行推理，需要哪种知识或特定的数学分支。

我知道类别理论可能会提供一些帮助，并且我一直在关注这个出色的演讲很长时间，并且仍在继续研究。

Answer 1

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

像这样foldr还有一个额外的参数。有些人将其视为折叠成函数，以便可以通过.and组合它们id（有时实际上是<=<and 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

因此，wheng的第二个参数是非严格的，s可以作为从左侧传递的状态，即使我们在右侧折叠，作为一个例子。