LINUX.ORG.RU

Каррирование, теория категорий

 ,


0

1

Доброе время суток. Меня терзают два вопроса.

1) В категории Hask объектами, как известно, являются классы, а морфизмами - функции. Как в таком случае нарисовать граф для каррированной функции, скажем, A->B->C? Безумные умения: http://ompldr.org/vZG5hMw Сам склоняюсь к варианту 1, prove me wrong.

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

P.S. В теории категорий и хаскелле совсем новичок, сильно с грязью не мешайте.


Ответ на: комментарий от anonymous

1) Раз возникли вопросы с терминологией, перефразирую как можно более тупо: как с помощью кружавчиков и стрелок изобразить функцию >1 аргумента? Функция одного аргумента A->B (или же не каррированная функция, отображающая кортеж во что-нибудь, что одно и то же) выглядит просто как стрелка из A в B. Как будет выглядеть A->B->C?

2) Вопрос общий, касается скорее православности.

dmfd ()

2)

Можно с помощью трансформеров, но через newtype. Когда перестанет устраивать - сделаешь свою собственную. Остальная часть программы ничего не заметит.

Macil ★★★★★ ()
Ответ на: комментарий от dmfd

Каррированная функция, видимо, выглядит так: (a -> b) -> c

Я угадал или ваши графы значат что-то иное, недели типы в haskell?

delete83 ★★ ()
Ответ на: комментарий от dmfd

И правда, фигня какая-то. Имеем функцию a -> b -> c
Фиксируем первый аргумент (обозначим, как переменную one): b' -> c'

Штрих, потому что тип второго аргумента и возвращаемого значения в общем случае изменится. one тут не участвует.

delete83 ★★ ()
Ответ на: комментарий от delete83

потому что тип второго аргумента и возвращаемого значения в общем случае изменится

При частичном применении типы оставшихся аргументов не меняются, либо я неправильно понял пост.

dmfd ()
Ответ на: комментарий от dmfd

В общем случае ты не можешь сказать, какой тип примет функция после частичного применения.

Пример:

mySum :: (Num a) => a -> a -> a
mySum x y = x + y
После частичного применения получим:
mySum4 :: (Integral a) => a -> a
mySum4 y = 4 + y
Но
myTup :: a -> b -> (a, b)
myTup x y = (x, y)
после частичного применения даст
myTup4 :: b -> (Int, b)
myTup4 y = (4, y)
С типом последней функции не уверен.

delete83 ★★ ()
Ответ на: комментарий от dmfd

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

delete83 ★★ ()

Ответ на первый вопрос, по-видимому, как-то должен быть связан с cartesian closed categories.

anonymous ()
Ответ на: комментарий от anonymous

как-то должен быть связан с cartesian closed categories

closed. не обязательно cartesian

jtootf ★★★★★ ()

Сам склоняюсь к варианту 1

правильно делаешь. рекомендую взять розеттский камень и открыть его на разделе о замкнутых категориях

Как будет лучше

совсем новичок

лучше будет попробовать самостоятельно реализовать оба варианта

jtootf ★★★★★ ()

В категории Hask объектами, как известно, являются классы, а морфизмами - функции.

Нет. Объектами являются ТИПЫ.

Как в таком случае нарисовать граф для каррированной функции

Что это? И какое отношение это имеет к категориям?

Как будет лучше, запилить для них свою монаду, или воспользоваться трансформерами?

Зависит от степени специфичности.

Miguel ★★★★★ ()
Ответ на: комментарий от Miguel

Нет. Объектами являются ТИПЫ.

Точно, оговорился.

dmfd ()
Ответ на: комментарий от delete83

Согласен, в случае полиморфизма всё сложнее. Просто я молчаливо подразумевал, что мы рассматриваем типы с кайндом *, которые составляют категорию Hask. Если я не ошибаюсь, полиморфная функция таким типом не является.

dmfd ()
Ответ на: комментарий от jtootf

замкнутых категориях

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

dmfd ()
Ответ на: комментарий от dmfd

Как будет выглядеть A->B->C?

a → (b → c), то есть a → (c ^ b) (или a → hom(b, c), или a → [b → c], в зависимости от обозначений), где c ^ b это экспоненциал (объект ─ [1], [2], то есть тип ─ [3]). В Set ([4], [5]) это будет пространство функций ([6]). Так что коммутативная диаграмма будет выглядеть так:

    a   c ^ b
    ∙ → ∙

Можно позволить себе вольность и рисовать её так:

        b
    a   ∙
    ∙ → ↓
        ∙
        c

Либо в виде струнной диаграммы ([7], [8], [9], [10]):

       a
       ∙
       ↓
       f
     ↙   ↖
    ∙     ∙
    c     b

[1] http://en.wikipedia.org/wiki/Exponential_object

[2] http://ncatlab.org/nlab/show/exponential object

[3] http://en.wikipedia.org/wiki/Function_type

[4] http://en.wikipedia.org/wiki/Category_of_sets

[5] http://ncatlab.org/nlab/show/set

[6] http://en.wikipedia.org/wiki/Function_space

[7] http://en.wikipedia.org/wiki/String_diagram

[8] http://reperiendi.wordpress.com/2009/01/24/syntactic-string-diagrams

[9] http://math.ucr.edu/home/baez/qg-fall2006/index.html#computation

[10] http://math.ucr.edu/home/baez/qg-winter2007/index.html#computation

Некоторые ссылки по ссылкам тоже подойдут (литература по двум последним, например).

quasimoto ★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.