2

作为示例，让我们采用以下算法来计算两个序列的最长公共子序列，从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隐含地假设两个参数都是 type Eq a => [a]；实际上，如果我尝试明确给出签名lcs :: [a] -> [a] -> [a]，则会在 where 行发生错误x == y，而签名lcs :: Eq a => [a] -> [a] -> [a]有效。

现在假设我有两个列表l1and l2，两者都是 type [(a,b)]，并且我想要它们之间的 LCS，但是在==定义中使用运算符的方式lcs仅在snd每个元素的 s 之间（显然b需要属于Eqtypeclass） .

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

然而，这将迫使用户提供相等运算符，即使是在人们想要使用 plain 的琐碎情况下，并且将参数(==)包装在 a 中也无济于事。(a -> a)Maybe

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

我该怎么办？

4

2 回答 2

4

您只需提供两者——一个自定义操作符版本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。

于 2021-02-20T12:43:15.270 回答
3

正如@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。

于 2021-02-20T12:58:28.873 回答