如果类实例可用，则使用专门的实现 [英] Use specialized implementation if a class instance is available

问题描述

请考虑以下情况:

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

我有两个功能，slow_func和fast_func.这些函数是同一抽象函数的不同实现(它们执行相同的操作)，但是一个比另一个要快.仅当可以订购a类型时，才可以使用更快的实现.有没有办法构造一个尽可能充当fast_func的函数，否则返回到slow_func?

I have two functions, slow_func and fast_func. These functions are different implementations of the same abstract function (they do the same thing), but one is faster than the other. The faster implementation is only available if the type a can be ordered. Is there a way to construct a function which acts as fast_func when possible, and reverts to slow_func otherwise?

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

我已经尝试了以下方法:

I have already tried the following:

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

不幸的是，它无法编译，并产生以下错误:

Unfortunately, this doesn't compile, generating the following error:

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

原因是OverlappingInstances希望其中一个实例相对于实例规范而言是最专业的，而忽略其上下文(而不是使用限制性最强的上下文，这正是我们所需要的)在这里).

The reason is that OverlappingInstances wants one of the instances to be most specialized with respect to the instance specification, ignoring its context (rather than using the most restrictive context, which is what we need here).

有什么办法吗?

推荐答案

实际上可以.严重的是，我开始认为Haskell一切皆有可能...您可以使用最近宣布的 constraint-unions 方法.我使用的代码类似于 @leftaroundabout 编写的代码.不确定我是否以最佳方式做到了，只是尝试应用建议方法的概念:

Turned out actually you can. Seriously, I'm starting to think that everything is possible in Haskell... You can use results of recently announced constraint-unions approach. I'm using code similar to one that was written by @leftaroundabout. Not sure I did it in best way, just tried to apply concepts of proposed approach:

{-# 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，则会观察到明显慢得多的结果:

It uses appropriate function depending on whether a is Ord or Eq. I put Ord on the first place because everything that is Ord is automatically Eq and type checker rules might not trigger (though I didn't tested this function with constraints swapped). If you use Slow here (Fast . round) instead of Fast you can observe significantly slower results:

$ 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

更新

我已经更新了所需的实例.代替

I've updated required instances. Instead of

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

现在是

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

感谢@rampion进行解释！

这篇关于如果类实例可用，则使用专门的实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！