如何优雅地处理算法的自定义点以及参数的约束？

Question

举个例子，我们用下面的算法来计算两个序列的最长公共子序列，复制自Rosetta Code：

longest xs ys = if length xs > length ys then xs else ys
 
lcs [] _ = []
lcs _ [] = []
lcs (x:xs) (y:ys) 
  | x == y    = x : lcs xs ys
  | otherwise = longest (lcs (x:xs) ys) (lcs xs (y:ys))

lcs 隐含地假设两个参数都是 Eq a => [a] 类型；实际上，如果我尝试显式给出签名 lcs :: [a] -> [a] -> [a]，则 x == y 所在的行会发生错误，而签名 lcs :: Eq a => [a] -> [a] -> [a] 有效。

现在假设我有两个列表 l1 和 l2，都是 [(a,b)] 类型，并且我想要它们之间的 LCS，但是在某种程度上使用 == 运算符在 lcs 的定义中仅在每个元素的 snd 之间（显然 b 需要属于 Eq 类型类）。

我不仅可以为 lcs 提供两个列表，还可以为 lcs 提供相等运算符，在上面的具体示例中为 (==) `on` snd。 lcs 的签名将是 (a -> a -> Bool) -> [a] -> [a] -> [a].

但是，即使在想要使用普通 (==) 并将 (a -> a) 参数包装在 [=30= 中的微不足道的情况下，这也会迫使用户提供相等运算符] 也无济于事。

换句话说，我觉得在一般情况下，通过 Eq a => 对参数的约束是可以的，但在其他情况下，人们可能想传递一个自定义相等运算符来删除该约束，这让我觉得函数重载。

我该怎么办？

Answer 1

您只需同时提供 – 自定义运算符版本 lcsBy 和根据该版本实现的 Eq a => 版本。

lcsBy :: (a->a->Bool) -> [a] -> [a] -> [a]
...
lcsBy compOp (x:xs) (y:ys) 
 | compOp x y  = ...
 ...

lcs :: Eq a => [a] -> [a] -> [a]
lcs = lcsBy (==)

这类似于基础库如何同时提供 maximum and maximumBy。

Answer 2

如@leftaroundabout 所写，提供两者是更简单的选择。

不过，在某些特定情况下，有一些方法可以调用像

这样的函数

lcs :: Eq a => [a] -> [a] -> [a]

提供像您一样的自定义相等运算符。例如，

{-# LANGUAGE ScopedTypeVariables #-}
import Data.Coerce
import Data.Function

newtype OnSnd a b = OnSnd { getPair :: (a, b) }
instance Eq b => Eq (OnSnd a b) where
   (==) = (==) `on` (snd . getPair)

lcsOnSnd :: forall a b. Eq b => [(a,b)] -> [(a,b)] -> [(a,b)]
lcsOnSnd xs ys = coerce $ lcs (coerce xs) (coerce ys :: [OnSnd a b])
-- OR turn on TypeApplications, then:
-- lcsOnSnd = coerce (lcs @(OnSnd a b))

使用零成本安全强制将 [(a,b)] 转换为 [OnSnd a b]，应用 lcs（将使用 OnSnd a b 的自定义 ==），并将结果转换回来（再次是零成本）。

但是，要使这种方法起作用，== 必须在顶层可定义，即它不能是一个通用闭包，它取决于 lcsOnSnd 的附加参数。

如何优雅地处理算法的自定义点以及参数的约束？

How to deal gracefully with customization points of algorithms as well as constraints on their arguments?

haskell

functional-programming

overloading

typeclass

customization-point