tipos - haskell ejemplos
Use implementación especializada si una instancia de clase está disponible (2)
Considera la siguiente situación:
slow_func :: Eq a => [a] -> [a]
fast_func :: Ord a => [a] -> [a]
Tengo dos funciones, slow_func y fast_func . Estas funciones son implementaciones diferentes de la misma función abstracta (hacen lo mismo), pero una es más rápida que la otra. La implementación más rápida solo está disponible si se puede ordenar el tipo a . ¿Hay alguna manera de construir una función que actúe como fast_func cuando sea posible, y revierte a slow_func contrario?
as_fast_as_possible_func :: Eq a => [a] -> [a]
Ya he intentado lo siguiente:
{-# 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
Desafortunadamente, esto no se compila, generando el siguiente error:
Duplicate instance declarations:
instance Ord a => Func a
-- Defined at [...]
instance Eq a => Func a
-- Defined at p...]
La razón es que OverlappingInstances quiere que una de las instancias sea más especializada con respecto a la especificación de la instancia, ignorando su contexto (en lugar de usar el contexto más restrictivo, que es lo que necesitamos aquí).
Alguna forma de hacer esto?
Consideraría dos opciones:
Reescribir las reglas
Puede usar slow_func nominalmente en todas partes, pero permita que las reglas de reescritura lo optimicen cuando sea posible. Por ejemplo,
import Data.List
slowFunc :: Eq a => [a] -> [a]
slowFunc = nub
fastFunc :: Ord a => [a] -> [a]
fastFunc = map head . group . sort
main = print . sum . slowFunc $ round <$> [sin x * n | x<-[0..n]]
where n = 100000
es lento (duh):
$ ghc -O2 Nub.hs && time ./Nub
[1 of 1] Compiling Main ( Nub.hs, Nub.o )
Linking Nub ...
-3670322
real 0m51.875s
user 0m51.867s
sys 0m0.004s
pero si agregamos (sin cambiar nada)
{-# NOINLINE slowFunc #-}
{-# RULES "slowFunc/Integer" slowFunc = fastFunc :: [Integer] -> [Integer] #-}
entonces
$ ghc -O2 Nub.hs && time ./Nub
[1 of 1] Compiling Main ( Nub.hs, Nub.o )
Linking Nub ...
-3670322
real 0m0.250s
user 0m0.245s
sys 0m0.004s
Las reglas de reescritura son un poco difíciles de confiar (la alineación es solo una cosa que puede interponerse en el camino), pero al menos puedes estar seguro de que algo que se ejecute con slowFunc seguirá funcionando (quizás no lo suficientemente rápido) pero definitivamente se ganará '' Me pierdo en algún problema de instancia faltante. Por otro lado, también debes asegurarte de que slowFunc y fastFunc comporten de la misma manera: en mi ejemplo, ¡esto no se da realmente! (Pero se puede modificar fácilmente en consecuencia).
Como Alec enfatiza en los comentarios, deberá agregar una regla de reescritura para cada tipo que desee crear rápidamente. Lo bueno es que esto se puede hacer después de que el código haya finalizado y exactamente donde los perfiles indican que es importante, en cuanto al rendimiento.
Instancias individuales
Esta es la solución confiable: abstenerse de todas las instancias comunes y en su lugar decidir para cada tipo lo que sea apropiado.
instance Func Int where
as_fast_as_possible_func = fast_func
instance Func Double where
as_fast_as_possible_func = fast_func
...
instance Func (Complex Double) where
as_fast_as_possible_func = slow_func
Puede guardar algunas líneas duplicadas haciendo que la versión más común sea la predeterminada:
{-# LANGUAGE DefaultInstances #-}
class Func a where
as_fast_as_possible_func :: [a] -> [a]
default as_fast_as_possible_func :: Ord a => [a] -> [a]
as_fast_as_possible_func = fast_func
instance Func Int
instance Func Double
...
instance Func (Complex Double) where
as_fast_as_possible_func = slow_func
Resultó que en realidad puedes. En serio, estoy empezando a pensar que todo es posible en Haskell ... Puedes usar los resultados del enfoque de constraint-unions recientemente anunciado. Estoy usando un código similar a uno que fue escrito por @leftaroundabout . No estoy seguro de haberlo hecho de la mejor manera, intenté aplicar los conceptos del enfoque propuesto:
{-# 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
La parte clave aquí es 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
Utiliza la función apropiada dependiendo de si a es Ord o Eq . Puse a Ord en primer lugar porque todo lo que es Ord es automáticamente Eq y las reglas del verificador de tipos pueden no dispararse (aunque no probé esta función con las restricciones intercambiadas). Si utiliza Slow aquí (Fast . round) lugar de Fast , puede observar resultados significativamente más lentos:
$ 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
ACTUALIZAR
He actualizado las instancias requeridas. En lugar de
instance (c || Eq SlowWrapper) where resolve = /_ r -> r
Ahora es
instance d => (Ord SlowWrapper || d) where resolve = /_ r -> r