Patrón de diseño Functor en Haskell

Question

Pido disculpas por no encontrar un buen título para esta pregunta. Tengo problemas para expresar lo que necesito. Tengo un problema simple en Haskell y me pregunto cuál es el mejor enfoque para resolverlo.

Digamos que tengo una lista de números: [-3,2,1,2]. Quiero devolver el valor con el valor absoluto más alto. Es decir, quiero regresar -3. Así que quiero:

f = maximum . map abs 

El problema es, por supuesto, que este devuelve el valor calculado (3) y no el valor original (-3).

Pude encontrar una manera de hacer esto, tal vez asociar la lista original a una tupla de (originalValue, calculatdValue), encontrar la tupla cuyo snd es devuelto por mi función (máximo) y luego devolver el primero de esa tupla.

Pero esto parece un montón de "cañerías" para un problema simple como este, y me pregunto si hay alguna abstracción que me falta que resuelva esto. Es decir, generalmente hay un procedimiento que hago todo el tiempo, y quiero hacerlo de manera clara:

1. Deseo tomar una lista de elementos.
2. Quiero asignarlos a un cierto valor (digamos el valor absoluto)
3. Luego quiero seleccionar uno basado en algunos criterios (digamos que quiero el máximo o quizás el mínimo).
4. Pero luego quiero devolver el valor original. (Si la lista era [-3,2,1,2] y quiero devolver el valor con los valores más altos, entonces devolvería -3).

¿Existe una función de biblioteca para esto? ¿Hay un functor o una mónada para esto?

Creo que quiero una función con la firma:

f :: ([b] -> b) -> (a -> b) -> [a] -> a 

decir

f maximum abs [-3,2,1,2] 

Esto se siente muy "functory" a mí o tal vez "monádico".

Answer 1

Use maximumBy, que toma una función de comparación. A continuación, puede pasar alguna función que se compare de la manera que desee.

maximumBy (compare `on` abs) 

Answer 2

creo que algo en la línea de la siguiente debería funcionar.

foldl abs_max (head xs) xs 
where abs_max x y = if (abs x) > (abs y) then x else y 

Mirando más allá de la tarea en cuestión se podría generalizar a cabo mediante la abstracción de la función de comparación y pasándolo en adelante.

Answer 3

Aquí hay algo que he cocinado.Es un poco meh, ya que requiere (Ec b)

selectOn :: (Eq b) => ([b] -> b) -> (a -> b) -> [a] -> a 
selectOn reducer f list = head $ filter (\x -> f(x) == k) list 
    where k = reducer $ map f list 

Y luego:

selectOn maximum abs [1,2,-3] 

O:

selectOn sum id [-3, 0, 3] 

supongo que puedo generalizar comparar on y obtener exactamente el mismo efecto.

Answer 4

Si usted está tratando de tener algo ordenado y comparado por una proyección siempre, en lugar de sólo a un uso específico (en cuyo caso, véase la respuesta de augustss), a continuación, utilizar un envoltorio newtype:

newtype AbsInt = AbsInt Int 

instance Eq AbsInt where 
    AbsInt x == AbsInt y = abs x == abs y 

instance Ord AbsInt where 
    compare (AbsInt x) (AbsInt y) = compare x y 

Ahora, por ejemplo:

maximum [AbsInt 1, AbsInt 10, AbsInt (-50)] = AbsInt (-50) 

Es de suponer que estaría trabajando con AbsInt como sus objetos de estudio, por lo que no estaría escribiendo estas AbsInt s en todas partes.

Cuantas más operaciones necesite en AbsInt, más repetitivo necesitará. Sin embargo, si solo desea "pasar" algunas instancias, GHC tiene una extensión GeneralizedNewtypeDeriving que permite eso; por ejemplo .:

{-# LANGUAGE GeneralizedNewtypeDeriving #-} 

newtype AbsInt = AbsInt Int 
    deriving (Num) 

Ahora AbsInt comporta como un Int con respecto a la aritmética, pero (dados los casos arriba) por los valores absolutos con respecto a la comparación. También tenga en cuenta que la instancia Num le da la capacidad de utilizar literales, por lo que:

(maximum [1,2,-3] :: AbsInt) = AbsInt (-3) 

Answer 5

parada ... Hoogle tiempo!

Así que tienes una lista de cosas [a]. Y quiere terminar con uno de esos a. También desea comparar elementos de esta lista de alguna manera especial (no su ordenamiento natural), para determinar qué viene primero. Esta es la parte difícil, pero debería poder ver que lo que he descrito es una función del formulario a -> a -> Ordering.

Poner todo junto:

(a -> a -> Ordering) -> [a] -> a

Y hoogle it. maximumBy y minimumBy son los primeros hits :) Hoogle puede ser un activo poderoso cuando aprende a usarlo.(Véase la respuesta de augustss para obtener más información sobre cómo utilizar maximumBy en este caso)

Answer 6

Otra manera de hacerlo, si la conversión es un poco caro:

maximumWith :: (Ord b) => (a -> b) -> [a] -> a 
maximumWith f = snd . maximumBy (compare `on` fst) . map (f &&& id) 

Este tipo es similar a GHC.Exts 's sortWith, lo que nos da otra manera de hacerlo:

maximumWith :: (Ord b) => (a -> b) -> [a] -> a 
maximumWith f = head . sortWith (Down . f) 

podemos definir una minimumWith parecida:

minimumWith :: (Ord b) => (a -> b) -> [a] -> a 
minimumWith f = head . sortWith f 

Un vistazo a la fuente de sortWith revela que está implementado por sortBy, por lo que carece del almacenamiento en caché que tenía la primera definición de maximumWith.

Esto, obviamente, las llamadas por alguna evaluación comparativa:

module Main where 
import Control.Arrow ((&&&)) 
import Data.List (sortBy) 
import Data.Function (on) 
import GHC.Exts (sortWith) 
import Criterion.Main 

sortWith :: (Ord b) => (a -> b) -> [a] -> [a] 
sortWith f = map snd . sortBy (compare `on` fst) . map (f &&& id) 

badFib :: Int -> Int 
badFib 0 = 1 
badFib 1 = 1 
badFib n = badFib (n - 1) + badFib (n - 2) 

main = defaultMain [ bench "GHC.Exts.sortWith" $ nf (GHC.Exts.sortWith badFib) [0..20] 
        , bench "Main.sortWith" $ nf (Main.sortWith badFib) [0..20] 
        ] 

Los resultados en mi portátil:

benchmarking GHC.Exts.sortWith 
collecting 100 samples, 12 iterations each, in estimated 1.504415 s 
bootstrapping with 100000 resamples 
mean: 1.264608 ms, lb 1.260519 ms, ub 1.270248 ms, ci 0.950 
std dev: 24.42169 us, lb 19.21734 us, ub 31.50275 us, ci 0.950 
found 8 outliers among 100 samples (8.0%) 
    5 (5.0%) high mild 
    3 (3.0%) high severe 
variance introduced by outliers: 0.996% 
variance is unaffected by outliers 

benchmarking Main.sortWith 
collecting 100 samples, 50 iterations each, in estimated 1.516733 s 
bootstrapping with 100000 resamples 
mean: 305.9089 us, lb 304.0602 us, ub 310.9257 us, ci 0.950 
std dev: 14.41005 us, lb 6.680240 us, ub 30.26940 us, ci 0.950 
found 18 outliers among 100 samples (18.0%) 
    9 (9.0%) high mild 
    9 (9.0%) high severe 
variance introduced by outliers: 0.999% 
variance is unaffected by outliers