Как написать функцию связывания компаратора?

Question

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

Я придумал следующую функцию:

import Data.Monoid

chainCompare :: [a -> a -> Ordering] -> a -> a -> Ordering
chainCompare = mconcat . map ($)

РЕДАКТИРОВАТЬ: chainCompare также можно записать как (спасибо Витусу за указание на это):

chaincompare = mconcat

Пример использования этой функции:

import Data.List
import Data.Ord

sortBy (chainCompare [comparing length, comparing sum]) [[1..100], [1..20], [100..200]]

Однако эта функция требует явного сравнения, поэтому я попытался изменить функцию следующим образом:

chainCompare :: Ord b => [a -> b] -> a -> a -> Ordering
chainCompare = mconcat . map (comparing $)

Тем не мение, chainCompare в этом случае вызовет ошибку компиляции (также, даже если этот пример компилируется, он не будет работать для пустых строк):

 sortBy (chainCompare [length, head]) [['a'..'z'], ['A'..'Z'], "Lorem ipsum dolor sit amet"]

Можно ли сделать chainCompare полиморфный в том смысле, что b может быть любого типа instance Ord? Я видел некоторый код на Haskell, используя forall расширения и пытался их искать, но я до сих пор не могу понять, для чего полезно каждое конкретное расширение.

Answer 1

chainCompare [f, g] всегда будет вызывать ошибку, если f а также g являются функциями с разными типами - независимо от того, как вы определяете chainCompare, Вы даже можете удалить chainCompare и просто напиши [f, g] и это все равно вызовет ошибку. Причина в том, что просто невозможно иметь значения разных типов в списке.

Иногда, когда вы хотите сохранить значения разных типов в одном и том же списке, имеет смысл использовать экзистенциальные типы (расширение GHC). С этим вы можете определить экзистенциальный тип Comparator и использовать список [Comparator length, Comparator head], Однако это не имеет никакого преимущества по сравнению с использованием comparing как вы делали в первом примере, так что в этом случае это было бы совершенно бессмысленно.

Итак, ваш первый код, использующий comparing действительно лучшее, что вы можете сделать.

Для записи вот как будет выглядеть код с использованием экзистенциальных типов:

{-# LANGUAGE ExistentialQuantification #-}

import Data.Monoid
import Data.Ord

data Comparator a = forall b. Ord b => Comparator (a -> b)

chainCompare :: [Comparator a] -> a -> a -> Ordering
chainCompare = mconcat . map comp
  where comp (Comparator f) = comparing f

-- Usage:
list = [['a'..'z'], ['A'..'Z'], "Lorem ipsum dolor sit amet"]
sortedList = sortBy (chainCompare [Comparator length, Comparator head]) list

Единственная разница в использовании по сравнению с вашей первой версией заключается в том, что вы должны написать Comparator вместо comparing и что невозможно использовать функцию сравнения, которая не сравнивает на основе ключа. Как я уже сказал, это не добавляет никакой выгоды по сравнению с вашей первой версией.