Блог

Я новичок в Haskell. Я пытаюсь создать мини-язык в Haskell и хотел бы, если возможно, вызвать функцию более высокого порядка opp (сокращение от «противоположный»), которая преобразует ряд знакомых функций в их очевидные противоположности. Например, opp succ будет ли функция pred , opp head будет last и так далее. У меня нет какого-то общего определения того, что значит преобразовать функцию в ее противоположность: я просто хочу выбрать несколько ключевых примеров и объявить, каковы их противоположности. Итак, я хочу очень полиморфную функцию, которая вряд ли когда-либо определяется.

Трудность, по-видимому, заключается в том, что я хочу распознавать функции по их именам, а не по их сути (так сказать). Одним из проявлений этой трудности является то, что если я напишу

opp succ = pred

тогда Haskell обрабатывает succ как переменную и, следовательно, дает мне постоянную функцию, которая всегда принимает значение pred . Что я действительно хочу, так это сказать что-то вроде: «Если вы когда-нибудь увидите строку opp succ , подумайте об этом как о другом имени для pred » . Но после довольно долгого поиска я не могу понять, как это сделать (если это вообще возможно).

Подводя итог, я хотел бы определить функцию

opp :: (a -> b) -> (a -> b)

говоря такие вещи, как

opp succ = pred

opp pred = succ

opp head = last

opp last = head

и добавление в этот список всякий раз, когда мне захочется. Очевидно, что я не могу сделать это так, но есть ли какой-нибудь не ужасный способ достижения того же эффекта?

Да, вы можете, однако вам требуются RankNTypes, чтобы иметь хорошую реализацию.

 {-# LANGUAGE TypeOperators #-}
{-# LANGUAGE RankNTypes #-}
module Opposites where

class Opposite f where
  makeOpposite :: (a -> b) -> (a -> b) -> f a b


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

instance Opposite (->) where
  makeOpposite = const

instance Opposite FunctionAndOpposite where
  makeOpposite = FunctionAndOpposite

opp :: FunctionAndOpposite a b -> a -> b
opp (FunctionAndOpposite _ f) = f

type a :<-> b = forall f. Opposite f => f a b

succ' :: Enum a => a :<-> a
succ' = makeOpposite succ pred

pred' :: Enum a => a :<-> a
pred' = makeOpposite pred succ

head' :: [a] :<-> a
head' = makeOpposite head last

last' :: [a] :<-> a
last' = makeOpposite last head
  

Пример использования:

 > head' [1,2,3]
1
> opp head' [1,2,3]
3
  

Как это работает

Во-первых, есть Opposite класс. Это просто описывает f a b то, что может быть построено из двух функций (a -> b) (нормальной и противоположной функций).

Далее определяется тип данных FunctionAndOpposite . Это просто сохраняет две функции. Теперь и стандартная функция, и this являются экземплярами класса Opposite . Экземпляр функции просто отбрасывает противоположную функцию.

Теперь opp функция может быть определена. Это просто выводит вторую функцию из a FunctionAndOpposite .

Наконец, мы получаем строку, которая объединяет все это вместе:

 type a :<-> b = forall f. Opposite f => f a b
  

это определяет синоним типа, который принимает два входных типа a и b, затем возвращает тип f a b , где f может быть любым Opposite (в зависимости от того, что необходимо).

( :<-> это просто причудливое имя для типа, включенного с TypeOperators помощью).

Рассмотрим код head' [1,2,3] . head' имеет тип forall f. Opposite f => f [a] a . Однако, поскольку он используется как приложение-функция (поскольку сразу после этого у него есть аргумент), f должно быть -> . Поэтому используется реализация функции Opposite , возвращающая первый аргумент makeOpposite , который head (отлично!).

Однако, допустим opp head' [1,2,3] , вызывается. opp имеет тип FunctionAndOpposite a b -> a -> b , поэтому f должно быть FunctionAndOpposite . Поэтому FunctionAndOpposite Opposite вызывается экземпляр, создающий тип данных с использованием обоих аргументов to makeOpposite . opp затем извлекает вторую функцию, которая last .

Кроме того, это делается с использованием аналогичной техники, используемой в lens библиотеке для Isomorphism . Изоморфизм — это, по сути, пара функций, которые являются обратными друг другу. Например ( 2) , и (-2) , reverse и само по себе. Это, вероятно, более полезная концепция в целом, поскольку она позволяет выполнять операции над типом данных поверх преобразования. См. Control.Lens .Iso для получения более подробной информации, однако обратите внимание, что для понимания этого вам нужно будет понять концепции объектива, что является довольно большой работой.

Если мы переформулируем ваш вопрос в эту форму, проблема может стать для вас более понятной:

 opp x | x == succ = pred
      | x == pred = succ
  

Это выдаст вам ошибку, (a -> b) у которой нет Eq экземпляра, которого она не может иметь, поскольку равенство для функций не определено.

Решением этой проблемы было бы определить отдельный тип данных, для которого вы можете сопоставить шаблон.

Возможно, можно использовать какую-то хэш-карту на основе адреса замыкания в куче для идентификации функций. Тогда вы могли бы создать такую обратную таблицу. К сожалению, вы на самом деле не получите то, что хотите, поскольку функции — это просто значения, и как таковые они создаются всякий раз, когда компилятор (или среда выполнения) решает это сделать.

Например. даже когда вы говорите, что

 opp head = last
  

Вы можете (в зависимости от реализации компилятора) ничего не добиться для

 opp (λx.head x) 
  

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