haskell - 如果类实例可用，则使用专门的实现

Question

考虑以下情况:

slow_func :: Eq a  => [a] -> [a]
fast_func :: Ord a => [a] -> [a]

我有两个函数，slow_func 和 fast_func。这些函数是同一抽象函数的不同实现(它们执行相同的操作)，但其中一个比另一个更快。仅当可以订购 a 类型时，才能实现更快的实现。有没有办法构造一个函数，在可能的情况下充当 fast_func ，否则恢复为 slow_func ？

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

我已经尝试过以下操作:

{-# LANGUAGE OverlappingInstances  #-}

class Func a where
    as_fast_as_possible_func :: [a] -> [a]

instance Ord a => Func a where
    as_fast_as_possible_func = fast_func

instance Eq a => Func a where
    as_fast_as_possible_func = slow_func

不幸的是，这无法编译，生成以下错误:

Duplicate instance declarations:
  instance Ord a => Func a
    -- Defined at [...]
  instance Eq a => Func a
    -- Defined at [...]

原因是 OverlappingInstances 希望实例之一相对于实例规范而言是最专业的，而忽略其上下文(而不是使用最严格的上下文，这就是我们需要的)。

有办法做到这一点吗？

Answer 1

事实证明你确实可以。说真的，我开始认为 Haskell 中一切皆有可能...您可以使用最近宣布的结果 constraint-unions方法。我使用的代码类似于 @leftaroundabout 编写的代码。不确定我以最好的方式做到了这一点，只是尝试应用建议方法的概念:

{-# OPTIONS_GHC -Wall -Wno-name-shadowing #-}

{-# LANGUAGE AllowAmbiguousTypes        #-}
{-# LANGUAGE ConstraintKinds            #-}
{-# LANGUAGE FlexibleContexts           #-}
{-# LANGUAGE FlexibleInstances          #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE MultiParamTypeClasses      #-}
{-# LANGUAGE RankNTypes                 #-}
{-# LANGUAGE ScopedTypeVariables        #-}
{-# LANGUAGE TypeApplications           #-}
{-# LANGUAGE TypeOperators              #-}

module Main where

import           Data.List (group, nub, sort)

infixr 2 ||
class  c || d where
    resolve :: (c => r) -> (d => r) -> r

slowFunc :: Eq a => [a] -> [a]
slowFunc = nub

fastFunc :: Ord a => [a] -> [a]
fastFunc = map head . group . sort

as_fast_as_possible_func :: forall a. (Ord a || Eq a) => [a] -> [a]
as_fast_as_possible_func = resolve @(Ord a) @(Eq a) fastFunc slowFunc

newtype SlowWrapper = Slow Int deriving (Show, Num, Eq)
newtype FastWrapper = Fast Int deriving (Show, Num, Eq, Ord)

instance      (Ord FastWrapper || d) where resolve = \r _ -> r
instance d => (Ord SlowWrapper || d) where resolve = \_ r -> r

main :: IO ()
main = print . sum . as_fast_as_possible_func $ (Fast . round) 
                                             <$> [sin x * n | x<-[0..n]]
  where n = 20000

这里的关键部分是as_fast_as_possible_func:

as_fast_as_possible_func :: forall a. (Ord a || Eq a) => [a] -> [a]
as_fast_as_possible_func = resolve @(Ord a) @(Eq a) fastFunc slowFunc

它根据a是Ord还是Eq使用适当的函数。我将 Ord 放在第一位，因为 Ord 的所有内容都会自动 Eq 并且类型检查器规则可能不会触发(尽管我没有测试过)这个函数的约束交换了)。如果您在此处使用 Slow (Fast . round) 而不是 Fast，您可以观察到明显较慢的结果:

$ time ./Nub  # With `Slow` 
Slow 166822

real    0m0.971s
user    0m0.960s
sys     0m0.008s


$ time ./Nub  # With `Fast` 
Fast 166822

real    0m0.038s
user    0m0.036s
sys     0m0.000s

更新

我已经更新了所需的实例。而不是

instance (c || Eq SlowWrapper)  where resolve = \_ r -> r

现在是

instance d => (Ord SlowWrapper || d) where resolve = \_ r -> r

Thanks @rampion for explanation!