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

Question

As an example, let's take the following algorithm for computing the longest common subsequence of two sequences, copied from 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 impicitly assumes that both arguments are of type Eq a => [a]; indeed, if I try to explicitly give the signature lcs :: [a] -> [a] -> [a] an error occurs on the line where x == y is, whereas the signature lcs :: Eq a => [a] -> [a] -> [a] works.

Now let's suppose I have two lists l1 and l2, both of type [(a,b)], and that I want the LCS between them, but in a way that uses the == operator in the definition of lcs only between the snds of each element (obviously b is required to belong to Eq typeclass).

I could provide lcs with not only the two lists, but also with the equality operator, which in the specific example above would be (==) `on` snd. The signature of lcs would then be (a -> a -> Bool) -> [a] -> [a] -> [a].

However, this would force the user to provide the equality operator even in the trivial case that one wants to use a plain (==), and wrapping the (a -> a) argument in a Maybe wouldn't help either.

In other words I feel that in the general case the constraint on the argument via Eq a => is ok, but in other cases one might want to pass a custom equality operator removing that constraint, which makes me thing of function overloading.

How should I go about this?

Answer 1

You simply provide both – a custom-operator version lcsBy, and an Eq a => version which is implemented in terms of that.

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

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

This is analogous to how the base library provides both maximum and maximumBy.

Answer 2

Providing both is the simpler option, as @leftaroundabout wrote.

Still, in some specific cases, there are ways to call a function like

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

providing a custom equality operator like yours. For instance,

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

converts [(a,b)] to [OnSnd a b] using a zero-cost safe coercion, applies lcs (which will use the custom == of OnSnd a b), and converts the result back (zero-cost, again).

For this approach to work, however, == must be definable at the top-level, i.e. it can not be a generic closure depending on, say, an additional parameter to lcsOnSnd.