在Haskell中定义类Psi组合子：能否用现有组合子替代自定义实现？

我正在用Haskell解决LeetCode的《Max Count of Pos & Neg Integer》问题，写出了两种实现方案，其中第二种用到了一个自定义组合子myCombinator，现在想找到用现有标准库组合子替代它的方法。

原代码如下：

-- First solution
maximumCount :: [Int] -> Int
maximumCount = liftM2 max (length . filter (> 0)) (length . filter (< 0))

-- Custom combinator that's ALMOST the Psi combinator
-- abcde.a(b(ce)(b(de))
myCombinator :: (c -> c -> d) -> (a -> b -> c) -> a -> a -> b -> d
myCombinator f g x y z = f (g x z) (g y z)

-- Second solution
maximumCount' :: [Int] -> Int
maximumCount' = myCombinator max (length .: filter) (> 0) (< 0)

分析自定义组合子的结构 #

myCombinator的核心逻辑是：给定一个二元函数f、一个二元函数g，以及两个参数x、y，返回一个函数，该函数接收z后，分别计算g x z和g y z，再用f组合这两个结果。

用标准库组合子替代的方法 #

方法1：利用函数的Applicative实例（推荐）

函数类型(->) b本身是Applicative实例，其中liftA2的行为正好是将两个函数作用于同一参数后再用二元函数组合结果。我们可以通过嵌套liftA2来实现myCombinator：

-- 用嵌套liftA2替代myCombinator
maximumCount' :: [Int] -> Int
maximumCount' = (liftA2 . liftA2) max (length .: filter) (> 0) (< 0)

这里(liftA2 . liftA2) max的作用等价于原myCombinator max：

• 外层liftA2处理a -> a -> ...的参数（即>0和<0）
• 内层liftA2处理b -> ...的参数（即输入的[Int]列表）

方法2：结合on与flip

如果想用Data.Function里的on组合子，可以通过flip调整g的参数顺序，再结合on实现：

import Data.Function (on)

-- 用on和flip替代myCombinator
maximumCount' :: [Int] -> Int
maximumCount' = \xs -> max `on` (\p -> length . filter p $ xs) (>0) (<0)

或者更贴合原组合子结构的写法：

import Data.Function (on)

myCombinator' :: (c -> c -> d) -> (a -> b -> c) -> a -> a -> b -> d
myCombinator' f g x y z = f `on` flip g z $ x y

方法3：用fmap与ap组合

也可以通过fmap（<$>）和ap（<*>）来手动组合逻辑，本质和liftA2是一致的：

maximumCount' :: [Int] -> Int
maximumCount' = \xs -> max <$> (length . filter (>0)) <*> (length . filter (<0)) $ xs

这其实和第一个解决方案的思路类似，只是显式处理了参数xs。

推导组合子写法的小技巧 #

• 拆解逻辑：把自定义组合子的实现拆成函数应用的链条，比如f (g x z) (g y z)可以看成(f <$> g x <*> g y) z，对应Applicative的操作。
• 利用函数的Applicative/Monad实例：函数作为实例时，liftA2、ap等组合子天然处理“共享参数”的场景，这在这类组合逻辑中非常常用。
• 匹配类型签名：查阅on、liftA2、(.)、flip等标准库组合子的类型签名，尝试将自定义逻辑的类型与它们匹配，找到适配的组合方式。

内容的提问来源于stack exchange，提问作者Matthew Ibbetson