Почему нет класса типов для функций?

17

В проблеме обучения, с которой я возился, я понял, что мне нужен класс типов для функций с операциями для применения, создания и т. Д. Причины ...

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

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

Например, функции, которые применяют целочисленные смещения, могут быть представлены ADT, содержащим целое число. Применение этих функций просто означает добавление целого числа. Композиция реализуется путем добавления обернутых целых чисел. У обратной функции целое число отрицается. Идентификационная функция оборачивает ноль. Функция константы не может быть предоставлена, потому что для нее нет подходящего представления.

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

Я нашел модуль Data.Function , но нет класса типов - только некоторые общие функции, которые также доступны из Prelude.

Итак, почему нет класса типов для функций? Это "только потому, что нет" или "потому что это не так полезно, как вы думаете"? Или, может быть, есть фундаментальная проблема с идеей?

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

Больше подсказок

Пример кода, чтобы показать, к чему я стремлюсь ...

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE GADTs #-}

--  In my first version, Doable only had the one argument f. This version
--  seemed to be needed to support the UndoableOffset type.
--
--  It seems to work, but it also seems strange. In particular,
--  the composition function - a and b are in the class, but c isn't,
--  yet there's nothing special about c compared with a and b.
class Doable f a b where
  fwdApply :: f a b -> a -> b
  compDoable :: f b c -> f a b -> f a c

--  In the first version, I only needed a constraint for
--  Doable f a b, but either version makes sense.
class (Doable f a b, Doable f b a) => Undoable f a b where
  bwd      :: f a b -> f b a

  bwdApply :: f a b -> b -> a
  bwdApply f b = fwdApply (bwd f) b

--  Original ADT - just making sure I could wrap a pair of functions
--  and there were no really daft mistakes.
data UndoableFn a b = UFN { getFwd :: a -> b, getBwd :: b -> a }

instance Doable UndoableFn a b where
  fwdApply = getFwd
  compDoable f g = UFN ((getFwd f) . (getFwd g)) ((getBwd g) . (getBwd f))

instance Undoable UndoableFn a b where
  bwd f    = UFN (getBwd f) (getFwd f)
  bwdApply = getBwd

--  Making this one work led to all the extensions. This representation
--  can only represent certain functions. I seem to need the typeclass
--  arguments, but also to need to restrict which cases can happen, hence
--  the GADT. A GADT with only one constructor still seems odd. Perhaps
--  surprisingly, this type isn't just a toy (except that the whole thing's
--  a toy really) - it's one real case I need for the exercise. Still a
--  simple special case though.
data UndoableOffset a b where
  UOFF :: Int -> UndoableOffset Int Int

instance Doable UndoableOffset Int Int where
  fwdApply (UOFF x) y = y+x
  compDoable (UOFF x) (UOFF y) = UOFF (x+y)

instance Undoable UndoableOffset Int Int where
  bwdApply (UOFF x) y = y-x
  bwd (UOFF x) = UOFF (-x)

--  Some value-constructing functions
--  (-x) isn't shorthand for subtraction - whoops.
undoableAdd :: Int -> UndoableFn Int Int
undoableAdd x = UFN (+x) (\y -> y-x)

undoableMul :: Int -> UndoableFn Int Int
undoableMul x = UFN (*x) (`div` x)

--  With UndoableFn, it's possible to define an invertible function
--  that isn't invertible - to break the laws. To prevent that, need
--  the UFN constructor to be private (and all public ops to preserve
--  the laws). undoableMul is already not always invertible.
validate :: Undoable f a b => Eq a => f a b -> a -> Bool
validate f x = (bwdApply f (fwdApply f x)) == x

--  Validating a multiply-by-zero invertible function shows the flaw
--  in the validate-function plan. Must try harder.
main = do putStrLn . show $ validate (undoableAdd 3) 5
          putStrLn . show $ validate (undoableMul 3) 5
          --putStrLn . show $ validate (undoableMul 0) 5
          fb1 <- return $ UOFF 5
          fb2 <- return $ UOFF 7
          fb3 <- return $ compDoable fb1 fb2
          putStrLn $ "fwdApply fb1  3 = " ++ (show $ fwdApply fb1  3)
          putStrLn $ "bwdApply fb1  8 = " ++ (show $ bwdApply fb1  8)
          putStrLn $ "fwdApply fb3  2 = " ++ (show $ fwdApply fb3  2)
          putStrLn $ "bwdApply fb3 14 = " ++ (show $ bwdApply fb3 14)

Приложение включает в себя своего рода объединение, когда объединенные значения не равны, а связаны с помощью этих обратимых функций - логика в стиле Пролога, но с a = f(b)ограничениями a = b. Большая часть композиции будет получена в результате оптимизации структуры поиска объединения. Необходимость инверсий должна быть очевидной.

Если ни один элемент в унифицированном наборе не имеет точного значения, то определенный элемент может быть определен количественно только относительно другого элемента в этом унифицированном наборе. Вот почему я не хочу использовать «реальные» функции - вычислять эти относительные значения. Я мог бы отбросить весь функциональный аспект и просто иметь абсолютные и относительные величины - мне, вероятно, нужны только числа / векторы и (+)- но мой астронавт по внутренней архитектуре хочет его веселья.

Единственный способ, которым я снова разрываю ссылки, - это обратный трекинг, и все чисто - union-find будет сделан с использованием ключей в качестве IntMap«указателей». У меня есть простое объединение-поиск, но поскольку я еще не добавил обратимые функции, нет смысла перечислять его здесь.

Причины, по которым я не могу использовать Applicative, Monad, Arrow и т. Д.

Основные операции, которые мне нужны для обеспечения класса абстракции функции, - это приложение и композиция. Это звучит знакомо - например Applicative (<*>), Monad (>>=)и Arrow (>>>)все функции композиции. Однако типы, которые реализуют абстракцию функции в моем случае, будут содержать некоторую структуру данных, которая представляет функцию, но которая не (и не может содержать) функцию, и которая может представлять только некоторый ограниченный набор функций.

Как я упоминал в объяснении кода, иногда я могу определить только один элемент относительно другого, потому что ни один элемент в «объединенном» кластере не имеет точного значения. Я хочу получить представление об этой функции, которая в общем случае будет состоять из нескольких предоставленных функций (переход к общему предку в дереве объединения / поиска) и нескольких обратных функций (переход к другой функции). вещь).

Простой случай - когда исходные «функции» ограничены «функциями» с целочисленным смещением, я хочу, чтобы составной результат представлял собой «функцию» с целочисленным смещением - добавление смещений компонента. Это большая часть того, почему функция композиции должна быть в классе, а также в функции приложения.

Это означает , что я не могу обеспечить операции pure, returnили arrдля моих типов, поэтому я не могу использовать Applicative, Monadили Arrow.

Это не провал этих типов - это несоответствие абстракций. Абстракция, которую я хочу, имеет простую чистую функцию. Например, нет побочных эффектов, и нет необходимости создавать удобную запись для упорядочения и составления функций, отличных от стандарта (.), Который применяется ко всем функциям.

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

Steve314
источник
2
Считай меня сумасшедшим, но когда я думаю о классе типов, который ты описываешь, он предназначен для применения, создания и т. Д., Я думаю о аппликативных функторах, которые являются функциями. Возможно, вы думаете об этом классе?
Джимми Хоффа,
1
Я не думаю, что Applicativeэто совершенно правильно - для этого требуется обернуть значения, а также функции, тогда как я хочу только обернуть функции, а обернутые функции действительно являются функциями, тогда как мои обернутые функции обычно не будут (в в наиболее общем случае это AST, описывающие функции). Где <*>имеет тип f (a -> b) -> f a -> f b, я хочу оператор приложения с типом g a b -> a -> bгде aи bуказать домен и кодомен обернутой функции, но то, что внутри обертки (не обязательно), не является реальной функцией. На Стрелках - возможно, я посмотрю.
Steve314
3
если вы хотите инвертировать, разве это не подразумевает группу?
JK.
1
@jk. Замечательно, понимая, что есть много вещей, которые нужно прочитать об инверсиях функций, которые могут привести ОП к поиску того, что он ищет. Вот несколько интересных прочтений по теме. Но обратная функция Google для haskell дает много любопытного контента для чтения. Возможно, он просто хочет Data.Group
Джимми Хоффа
2
@ Steve314 Я думал, что функции с композицией являются моноидальной категорией. Они являются моноидами, если домен и кодомен всегда одинаковы.
Тим Сегин,

Ответы:

14

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

категории

Если у вас есть простая концепция функции, которая имеет индивидуальность и состав, чем у вас есть категория.

class Category c where
  id :: c a a
  (.) :: c b c -> c a b -> c a c

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

Стрелы

Если ваши функции имеют представление о продуктах и ​​могут вводить произвольные функции, тогда стрелки для вас

 class Arrow a where
   arr :: (b -> c) -> a b c
   first :: a b c -> a (b, d) (c, d)
   second :: a b c -> a (d, b) (d, c)

ArrowApply имеет понятие приложения, которое выглядит важным для того, что вы хотите.

аппликативных

Заявители имеют ваше представление о приложении, я использовал их в AST для представления приложения функции.

class Functor f => Applicative f where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f b -> f c

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

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

Даниэль Гратцер
источник
Категория, кажется, не хватает приложения - ($). Стрелки на первый взгляд кажутся огромным излишним, но все же ArrowApplyзвучат многообещающе - если мне не нужно ничего предоставлять, я не могу, это может быть хорошо. +1 на данный момент, с дополнительной проверкой, чтобы сделать.
Steve314
3
@ Steve314 Категории не имеют приложения, но у монад нет универсального способа их запуска, это не значит, что они бесполезны
Даниэль Гратцер
Есть общая причина, почему я не могу использовать Applicativeили Arrow(или Monad) - я не могу обернуть обычную функцию (в общем), потому что значения моего типа представляют функцию, но представлены данными, и не будут поддерживать произвольные функции, если если был способ перевести. Это означает, что я не могу предоставить pure, arrили returnдля случаев. Кстати - эти классы полезны, но я не могу использовать их для этой конкретной цели. Arrowне «массовое излишество» - это было ложное впечатление, когда я в последний раз пытался читать газету, когда не был готов ее понять.
Steve314
@ Steve314 Идея предоставления монадного интерфейса для создания данных - это то, для чего используются свободные монады, ознакомьтесь с ними
Даниэль Гратцер,
Я смотрел видео с Haskell Exchange 2013 - Andres Löh определенно объясняет это хорошо, хотя мне все еще, вероятно, нужно снова посмотреть его, поиграть с техникой и т. Д. Я не уверен, что здесь это необходимо. Моя цель - получить абстракцию функции, используя представление, которое не является функцией (но имеет функцию интерпретатора). Мне не нужна абстракция побочных эффектов, и мне не нужна чистая запись для операций секвенирования. Как только эта функциональная абстракция используется, приложения и композиции будут выполняться по одному в алгоритме в другой библиотеке.
Steve314
2

Как вы указали, основная проблема с использованием Applicative заключается в том, что нет разумного определения для pure. Следовательно, Applyбыл изобретен. По крайней мере, это мое понимание этого.

К сожалению, у меня нет примеров под рукой примеров Apply, которых также нет Applicative. Утверждается, что это правда IntMap, но я понятия не имею, почему. Точно так же я не знаю, допускает ли ваш пример - смещение целых чисел - Applyэкземпляр.

user185657
источник
это больше похоже на комментарий, см. Как ответить
Гнат
Сожалею. Это более или менее мой первый ответ.
user185657
Как вы предлагаете мне улучшить ответ?
user185657
рассмотрите возможность редактирования, чтобы помочь читателям увидеть, как ваш ответ отвечает на заданный вопрос: «Почему нет класса типов для функций? Это« просто потому, что его нет »или« потому что он не так полезен, как вы думаете »? Или, может быть, есть фундаментальная проблема с идеей? "
комнат
1
Я надеюсь, что это лучше
user185657
1

Помимо упомянутых Category, Arrowи Applicative:

Я также обнаружил Data.Lambda, Конал Эллиотт:

Некоторые функциональные классы, имеющие лямбда-подобную конструкцию

Выглядит интересно, конечно, но сложно понять без примеров ...

Примеры

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

Идея ТВ-библиотеки состоит в том, чтобы отображать значения Haskell (включая функции) в материальной форме.

Чтобы следовать правилу StackOverflow о том, чтобы не публиковать пустые сообщения, я скопирую несколько битов ниже, которые должны дать представление об этих вещах:

Первый пример гласит:

apples, bananas :: CInput Int
apples  = iTitle "apples"  defaultIn
bananas = iTitle "bananas" defaultIn

shoppingO :: COutput (Int -> Int -> Int)
shoppingO = oTitle "shopping list" $
            oLambda apples (oLambda bananas total)

shopping :: CTV (Int -> Int -> Int)
shopping = tv shoppingO (+)

который дает при запуске как runIO shopping(см. там для большего количества комментариев, графических интерфейсов и других примеров):

shopping list: apples: 8
bananas: 5
total: 13
imz - Иван Захарящев
источник
как это решает вопрос? см. Как ответить
комнат
@gnat Я думал, что определения в Data.Lambdaдают классы для функциональных вещей (о которых спрашивали) ... Я не был уверен, как эти вещи использовать. Я изучил это немного. Вероятно, они не предоставляют абстракцию для применения функции.
imz - Иван Захарящев