Что такое функция Zap Functor и zap в Haskell?

Ответ 1

Об этом говорит замечательный пост в блоге Kmett, Cofree Comonad и проблема выражения. К сожалению, в этом блоге довольно много терминологии, и я не совсем понимаю все сам, но мы можем попытаться набросать детали.

Числа Peano

Определим естественные числа очень странным образом. Сначала мы определим функции нуля Перо и преемника:

zero :: ()
zero = ()

incr :: a -> Identity a
incr = Identity

Тогда мы можем определить некоторые числа:

one :: Identity ()
one = incr zero

two :: Identity (Identity ())
two = incr . incr $ zero

three :: Identity (Identity (Identity ()))
three = incr . incr . incr $ zero

Необычный, но, похоже, он работает. Вы можете преобразовать 3 :: Int в three и обратно. (Попробуйте.) Можем ли мы написать функцию f для преобразования любого произвольного числа в наше странное представление и обратно? К сожалению нет. Система типа Haskell не позволит нам построить бесконечный тип, который является точным типом, который мы хотим для f.

Еще большая проблема заключается в том, что, как ленивый функциональный программист, я хочу перестать набирать Identity столько раз. При такой скорости я буду вынужден вводить ее O (n ^ 2) раз, чтобы определить n чисел. Это 2016 год, и я считаю это неприемлемым.

Мы можем обратиться к бесплатному типу данных за помощью для обеих наших проблем. (Некоторые люди называют эту Свободную монаду, но нет оснований для нас говорить "монада", когда мы можем просто сказать "тип".)

newtype Free f a = Free (Either a (f (Free f a)))

zero :: a -> Free Identity a
zero x = Free (Left x)

incr :: Free Identity a -> Free Identity a
incr = Free . Right . Identity

one :: a -> Free Identity a
one x = incr (zero x)

two :: a -> Free Identity a
two x = incr (incr (zero x))

three :: a -> Free Identity a
three = incr . incr . incr . zero

Довольно. Это (как ни удивительно, возможно) идентично нашему необычному представлению Identity, описанному выше.

Струйные

Теперь попробуем создать поток. Скажем, поток центриальных високосных лет, начиная с 2000 года (2000, 2400, 2800). Но странным образом.

unfold :: (a -> a) -> a -> (a, (a, (a, ...)))
unfold a2a a = (a, unfold a2a (a2a a))

centurials :: (Int, (Int, (Int, ...)))
centurials = unfold (+ 400) 2000

Предполагая, что компилятор позволил нам записать наш бесконечный тип, это было бы подходящим представлением для потока чисел. К спасению приходит Cofree, "двойной" тип Free. Двойной в категории теоретический смысл, где, если вы потратили время и вытащили учебник теории категорий и отварили много кофе и вытащили категорическую диаграмму, а затем перевернули все стрелки, которые вы переходили от одного к другому (или другое к одному). Это неудовлетворительное объяснение должно быть достаточным в качестве ручного парашюта о двойственности.

newtype Cofree f a = Cofree (a, f (Cofree f a))

unfold :: Functor f => (a -> f a) -> a -> Cofree f a
unfold a2fa a = Cofree (a, fmap (unfold a2fa) (a2fa a))

centurials :: Cofree Identity Int
centurials = unfold (Identity . (+ 400)) 2000

Это (опять-таки удивительно возможно) эквивалентно нашему представлению о кукольной королеве, представленном выше.

Индексирующие потоки с номерами Пеано

Но как искать конкретные элементы в потоке? Воспользовавшись дуальностью между Free и Cofree, мы можем фактически использовать наше представление чисел Пеано для индексации в наше представление потоков.

Оказывается, что в Haskell, если f и g являются двойственными в математическом смысле, то имеет место следующее свойство:

class Zap f g | f -> g, g -> f where
  zap :: (a -> b -> r) -> f a -> g b -> r

Нам придется преодолеть дискуссию о двойственности и почему это свойство справедливо для двойственных функторов.

Мы можем реализовать простейший экземпляр: математическую двойственность между тождественным функтором (представленным в Haskell как newtype Identity a = Identity a) и самим.

instance Zap Identity Identity where
  zap ab2r (Identity a) (Identity b) = ab2r a b

Это свойство может быть распространено и на бифунторы:

class Bizap f g | f -> g, g -> f where
  bizap :: (a -> c -> r) -> (b -> d -> r) -> f a b -> g c d -> r

Мы можем создать экземпляр этого класса для кодировки Хаскелла суммы и произведения, которые (нетривиально!) двойственны в теории категорий:

instance Bizap Either (,) where
  bizap ac2r bd2r (Left a) (c, d) = ac2r a c
  bizap ac2r bd2r (Right b) (c, d) = bd2r b d

instance Bizap (,) Either where
  bizap ac2r bd2r (a, b) (Left c) = ac2r a c
  bizap ac2r bd2r (a, b) (Right d) = bd2r b d

Теперь у нас достаточно механизмов, чтобы показать ту же двойственность в Haskell между Free и Cofree.

instance Zap f g => Zap (Cofree f) (Free g) where
  zap ab2r (Cofree as) (Free bs) = bizap ab2r (zap (zap ab2r)) as bs

instance Zap f g => Zap (Free f) (Cofree g) where
  zap ab2r (Free as) (Cofree bs) = bizap ab2r (zap (zap ab2r)) as bs

Эти случаи используют двойную бифунториальную природу Либо и (,), а также унаследованную zap по двойственности f и g, которая в наших примерах всегда будет Identity и Identity чтобы "отменить" слой с Free и Cofree и рекурсивно вызвать zap на этом нижнем уровне.

Наконец, посмотрим его в действии:

year2800 :: Int
year2800 = zap id (two id) centurials

Используя это свойство zap или "annhilation", мы можем извлекать значения из потока, созданного Cofree, с использованием натуральных индексов чисел, созданных Free. Хотя это далеко не реальный пример, этот код существует как упражнение в том, как мы можем кодировать идеи с высоким falutin из теории категорий в типах Haskell и типах. То, что мы в состоянии сделать это, служит мозговой дразнилкой, а также проверкой здравого смысла для нашего выбора типов для Free и Cofree.

Вы можете найти примеры, которые могут быть полезны для однострочных линий или когда структура данных оказывается в правильном порядке, как указано в ответе Гуркенгласа. Если вы обнаружите, что двойственность является полезным свойством для использования, обязательно достигните этой части пакета категорий. Но даже если мы не сможем найти его для использования, мы, безусловно, можем оценить красоту всего, что аккуратно сочетается.

Что касается zping

Вы правы, думая, что существует связь между Zap и Zip. Они названы в стиле Kmett развития, основанного на словах. Кодирование zippable-функторов приводит к очень похожей категории Zip:

class Functor f => Zip f where
  fzipWith :: (a -> b -> c) -> f a -> f b -> f c

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

Ответ 2

Zap связывает двойные функторы. В Haskell это означает, что один несет дополнительную информацию, а другой использует ее и что все они делают. (r, a) - значение, несущее дополнительное значение r, r -> b - значение b, которое сначала требует значения r. zapWith (+) read ("123", 321) подключит "123" к считыванию и подключит 123 и 321 к (+). Все Zap это помогает при подключении, если вы найдете фрагмент кода, в котором он подходит. zap = uncurry для этого экземпляра, кстати. Reader и Coreader изоморфны ((->) r) и ((,) r) соответственно. Другие экземпляры были бы одним, обеспечивающим два значения, а другие с использованием обоих, или f, обеспечивающих r, а затем использование s, а g - s, затем использует r.