Будет ли класс типа "между категориями и стрелой" иметь смысл?
Часто у вас есть что-то вроде 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
вместе с (&&&)
для создания новой стрелки из двух входов должно дать вам категорию с продуктами, что абсолютно разумно с теоретической точки зрения, а также не совместимо с обратимыми стрелками, которые вы используете по причинам, которые вы нашли.