Существуют ли полезные приложения для класса Divisible Type?

Ответ 1

Я рассмотрю пример основных типов данных в обобщенных методах сортировки по методу Фрица Хэнлейна, реализованных Эдвардом Кемтом в discrimination пакет.

В то время как там происходит многое, он в основном фокусируется на типе, подобном этому

data Group a = Group (forall b . [(a, b)] -> [[b]])

Если у вас есть значение типа Group a, у вас должно быть отношение эквивалентности на a, потому что если я дам вам связь между a и некоторым типом b, полностью неизвестным вам, тогда вы можете дать мне "группировки" b.

groupId :: Group a -> [a] -> [[a]]
groupId (Group grouper) = grouper . map (\a -> (a, a))

Вы можете видеть это как основной тип для написания библиотеки утилиты группировок. Например, мы можем хотеть знать, что если мы можем Group a и Group b, тогда мы можем Group (a, b) (подробнее об этом через секунду). Основная идея Henglein заключается в том, что если вы можете начать с базового Group для целых чисел, мы можем написать очень быстрые реализации Group Int32 с помощью сортировки radix, а затем использовать комбинаторы для их расширения по всем типам, тогда у вас будет обобщенная сортировка radix для алгебраических типы данных.

Итак, как мы можем построить нашу библиотеку комбинаторов?

Ну, f :: Group a -> Group b -> Group (a, b) довольно важен, поскольку он позволяет создавать группы типов продуктов. Обычно мы получаем это из Applicative и liftA2, но Group, вы заметите, что это Contravaiant, а не Functor.

Поэтому вместо этого мы используем Divisible

divided :: Group a -> Group b -> Group (a, b)

Обратите внимание, что это происходит странным образом из

divide :: (a -> (b, c)) -> Group b -> Group c -> Group a

поскольку он имеет типичный характер "противоположной стрелки" контравариантных вещей. Теперь мы можем понимать такие вещи, как divide и conquer в терминах их интерпретации на Group.

Разделить говорит, что если я хочу построить стратегию для приравнивания a, используя стратегии для приравнивания b и c s, я могу сделать следующее для любого типа x

• Возьмите свое частное отношение [(a, x)] и нарисуйте над ним функцию f :: a -> (b, c) и небольшую манипуляцию с набором, чтобы получить новое отношение [(b, (c, x))].

• Используйте Group b для выделения [(b, (c, x))] в [[(c, x)]]

• Используйте мой Group c, чтобы различать каждый [(c, x)] в [[x]], давая мне [[[x]]]

• Сгладьте внутренние слои, чтобы получить [[x]], как нам нужно

  instance Divisible Group where
    conquer = Group $ return . fmap snd
    divide k (Group l) (Group r) = Group $ \xs ->
      -- a bit more cleverly done here...
      l [ (b, (c, d)) | (a,d) <- xs, let (b, c) = k a] >>= r
  

Мы также получаем интерпретации более сложного Decidable уточнения Divisible

class Divisible f => Decidable f where
  lose   :: (a -> Void) -> f a
  choose :: (a -> Either b c) -> f b -> f c -> f a

instance Decidable Group where
  lose   :: (a -> Void) -> Group a
  choose :: (a -> Either b c) -> Group b -> Group c -> Group a

Они говорят, что для любого типа a, из которого мы можем гарантировать, что нет значений (мы не можем произвольно производить значения Void, функция a -> Void является средством создания Void данного a, таким образом, мы не сможем либо не производить значений a любыми способами!), то мы сразу получаем группировку нулевых значений

lose _ = Group (\_ -> [])

Мы также можем провести аналогичную игру с divide выше, за исключением того, что вместо использования нашего использования входных дискриминаторов мы чередуем.

Используя эти методы, мы создаем библиотеку "Group способных" вещей, а именно Grouping

class Grouping a where
  grouping :: Group a

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

Ответ 2

Один пример:

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

Divisible полезен для сериализации (следует ли теперь называть это сопоставление?), потому что вы можете превратить делимые сериализаторы частей в сериализатор целых, нуждающихся только в чистой функции для разделения целого на части.

Я действительно не видел проект, который работал таким образом, но я (медленно) работаю над реализацией Avro для Haskell, которая делает.

Когда я впервые встретил Divisible, я хотел его для divide и понятия не имел, какое возможное использование conquer может быть другим, кроме обмана (f a из ниоткуда, для любого a?). Но чтобы заставить Divisible законы проверить, что мои сериализаторы conquer стали "сериализатором", который кодирует что-либо нулевым байтам, что имеет большой смысл.

Ответ 3

Вот возможный вариант использования.

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

Эти складки контравариантны на своих входах и могут быть сделаны Divisible. Это означает, что если у вас есть поток элементов, где каждый элемент может быть каким-то образом разбит на части b и c, и у вас также случится сложение, которое потребляет b и другую складку, которая потребляет c s, то вы можете создать сгиб, который потребляет исходный поток.

Фактические складки из foldl не реализуют Divisible, но они могут, используя оболочку newtype. В моем пакете process-streaming у меня есть складной тип, который реализует Divisible.

divide требует, чтобы возвращаемые значения составляющих складок были одного типа, и этот тип должен быть экземпляром Monoid. Если складки возвращают разные, несвязанные моноиды, обходной путь заключается в том, чтобы поместить каждое возвращаемое значение в отдельное поле кортежа, оставив другое поле как mempty. Это работает, потому что кортеж моноидов сам по себе является Monoid.