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

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

CCD_ 1不恰当地假设两个参数都是CCD_；事实上，如果我试图显式地给签名lcs :: [a] -> [a] -> [a]，则在x == y所在的行上会发生错误，而签名lcs :: Eq a => [a] -> [a] -> [a]有效。

现在让我们假设我有两个列表l1和l2，它们都是类型[(a,b)]，并且我希望它们之间有LCS，但在lcs0的定义中，只在每个元素的snds之间使用==运算符(显然b需要属于Eq类型类)。

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

然而，即使在想要使用普通(==)的琐碎情况下，这也会迫使用户提供相等运算符，并且将(a -> a)参数封装在Eq a => [a]0中也无济于事。

换言之，我觉得在一般情况下，通过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和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的附加参数的泛型闭包。