Будет ли класс типа "между категориями и стрелой" иметь смысл?

Часто у вас есть что-то вроде Applicative без pure, или что-то вроде Monad, но без return. Пакет semigroupoid охватывает эти случаи с помощью Apply и Bind. Теперь я в аналогичной ситуации относительно Arrow, где я не могу определить значимую функцию arr, но я думаю, что другие функции будут иметь смысл.

Я определил тип, который содержит функцию и обратную функцию:

import Control.Category

data Rev a b = Rev (a -> b) (b -> a)

reverse (Rev f g) = Rev g f
apply (Rev f _) x = f x
applyReverse (Rev _ g) y = g y
compose (Rev f f') (Rev g g') = Rev ((Prelude..) f g) ((Prelude..) g' f') 

instance Category Rev where
  id = Rev Prelude.id Prelude.id
  (.) x y = compose x y 

Теперь я не могу реализовать Arrow, но что-то слабее:

--"Ow" is an "Arrow" without "arr"
class Category a => Ow a where
  first :: a b c -> a (b,d) (c,d)
  first f = stars f Control.Category.id

  second :: a b c -> a (d,b) (d,c)
  second f = stars Control.Category.id f

  --same as (***)
  stars :: a b c -> a b' c' -> a (b,b') (c,c')

 ...
 import Control.Arrow 

 instance Ow Rev where
    stars (Rev f f') (Rev g g') = Rev (f *** g) (f' *** g')  

Я думаю, что не могу реализовать эквивалент &&&, поскольку он определен как f &&& g = arr (\b -> (b,b)) >>> f *** g, а (\b -> (b,b)) не может быть обратимым. Однако, как вы думаете, этот более слабый тип класса может быть полезен? Это даже имеет смысл с теоретической точки зрения?

Ответы

Ответ 1

Этот подход был рассмотрен в разделе "Там и обратно: стрелки для обратимого программирования": http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.153.9383

По каким именно причинам вы столкнулись, это оказалось плохим подходом, который не получил широкого распространения. Совсем недавно Тиллманн Рендель произвел восхитительный подход к обратимому синтаксису, который заменил частичные изоморфизмы для двумерных диаграмм (http://www.informatik.uni-marburg.de/~rendel/rendel10invertible.pdf). Это было упаковано на хаке, в котором люди могут использовать и играть с: http://hackage.haskell.org/package/invertible-syntax

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

Изменить: там также Адам Мегач Обобщенные стрелки (http://www.cs.berkeley.edu/~megacz/garrows/). Возможно, это и не полезно для обратимого программирования (хотя базовый класс стилей кажется инвертированным), но у них есть использование в других ситуациях, где arr слишком силен, но другие операции со стрелками могут иметь смысл.

Ответ 2

С точки зрения теории категорий класс Category описывает любую категорию, стрелки которой могут быть описаны непосредственно в Haskell конструктором типа. Почти любая дополнительная функция, которую вы хотите построить поверх этого, в виде новых примитивных стрелок или функций построения стрелок, будет иметь смысл в некоторой степени, если вы сможете реализовать ее с использованием общих функций. Единственное предостережение заключается в том, что добавление выразительной мощности может нарушить другие требования, как это часто бывает с arr.

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

Функция arr примерно равна функтору (в смысле теории категорий) от функций Haskell до экземпляра Arrow, оставляя объекты одинаковыми (то есть параметры типа). Простое удаление arr из Arrow дает вам... что-то еще, что, вероятно, не очень полезно само по себе, без по крайней мере добавления эквивалентов arr fst и arr snd в качестве примитивов.

Я считаю, что добавление примитивов для fst и snd вместе с (&&&) для создания новой стрелки из двух входов должно дать вам категорию с продуктами, что абсолютно разумно с теоретической точки зрения, а также не совместимо с обратимыми стрелками, которые вы используете по причинам, которые вы нашли.