Дизайн шаблона Functor в Haskell

Я прошу прощения за то, что не придумал хорошего названия для этого вопроса. У меня проблемы с выражением того, что мне нужно. У меня есть простая проблема в Haskell, и мне интересно, как лучше всего ее решить.

Скажем, у меня есть список чисел: [-3,2,1,2]. Я хочу вернуть значение с наивысшим абсолютным значением. То есть, я хочу вернуться -3. Поэтому я хочу:

f = maximum . map abs

Проблема заключается в том, что это возвращает вычисленное значение (3), а не исходное значение (-3).

Я мог бы найти способ сделать это, возможно, сопоставляя исходный список с кортежем (originalValue, calculatdValue), находя кортеж, snd которого возвращается моей функцией (максимум), а затем возвращает fst этого кортежа.

Но это похоже на "сантехнику" для простой проблемы, подобной этой, и мне интересно, есть ли какая-то абстракция, которую я пропускаю, которая решает это. То есть, это обычно процедура, которую я делаю все время, и я хочу, чтобы ее способ аккуратно выполнял:

Я хочу взять список элементов.
Я хочу сопоставить их с определенным значением (допустим, абсолютное значение)
Затем я хочу выбрать один, основанный на некоторых критериях (скажем, я хочу максимум или, может быть, минимум).
Но тогда я хочу вернуть исходное значение. (Если список был [-3,2,1,2], и я хочу вернуть значение с наивысшим абс, то я бы вернул -3).

Есть ли для этого библиотечная функция? Есть ли функтор или монада для этого?

Я думаю, что мне нужна функция с сигнатурой:

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

то есть.

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

Это кажется мне "функциональным" или "монадическим".

Ответ 1

Используйте максимумBy, который выполняет функцию сравнения. Затем вы можете передать некоторую функцию, которая сравнивает то, что вы хотите.

maximumBy (compare `on` abs)

Ответ 2

Остановить... hoogle time!

Итак, у вас есть список вещей [a]. И вы хотите получить только один из них a. Вы также хотите сравнить элементы этого списка каким-то особым образом (а не их естественным порядком), чтобы определить, что на первом месте. Это сложная часть, но вы должны уметь видеть, что то, что я описал, является функцией формы a -> a -> Ordering.

Объедините все это:

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

И hoogle it. maximumBy и minimumBy - первые хиты:). Hoogle может стать мощным активом, когда вы научитесь его использовать. (Подробнее об использовании maximumBy в этом случае см. В августовском ответе)

Ответ 3

Другой способ сделать это, если преобразование немного дорого:

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

Этот тип похож на GHC.Exts sortWith, который дает нам другой способ сделать это:

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

Мы можем определить минимум так же:

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

Взгляд на источник sortWith показывает, что он реализован с помощью sortBy, поэтому ему не хватает кэширования, которое было для первого определения для maximumWith.

Это, очевидно, требует некоторого бенчмаркинга:

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]
                   ]

Результаты на моем ноутбуке:

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

Ответ 4

Если вы пытаетесь выполнить что-то упорядоченное и сопоставляемое проекцией всегда, а не только при определенном использовании (в этом случае см. ответ augustss), используйте оболочку 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

Теперь, например:

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

Предположительно, вы будете работать с AbsInt в качестве объектов изучения, поэтому вы не будете писать эти AbsInt всюду.

Чем больше операций вам нужно на AbsInt, тем больше требуется вам. Однако, если вы просто хотите "пропустить" некоторые экземпляры, GHC имеет расширение GeneralizedNewtypeDeriving, которое позволяет это; например:.

{-# LANGUAGE GeneralizedNewtypeDeriving #-}

newtype AbsInt = AbsInt Int
    deriving (Num)

Теперь AbsInt ведет себя как a Int в отношении арифметики, но (с учетом приведенных выше экземпляров) абсолютными значениями для сравнения. Также обратите внимание, что экземпляр Num дает вам возможность использовать литералы, поэтому:

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

Ответ 5

Я считаю, что что-то в соответствии с приведенными ниже должно работать.

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

Выглядя за рамки поставленной задачи, вы можете обобщить ее, абстрагировав функцию сравнения и передав ее позже.

Ответ 6

Вот что я приготовил. Это своего рода meh, потому что для этого требуется (Eq 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

И затем:

selectOn maximum abs [1,2,-3]

Или:

selectOn sum id [-3, 0, 3]

Я думаю, я могу обобщить сравнение on и получить тот же эффект.