November 12th, 2007

with Cat The Cat

Что хотел написать.

Сперва - про комибинаторы и сложность.

Если мы начнем переводить программу на лямбда-исчислении в комбинаторное, то только SK-базис приведет к экспоненциальному количеству комбинаторов.

SK+BC-базис (моежт, езе какой комбинатор, давно читал) дает всего квадратичное размножение.

Идеальным, насколько я понимаю, является использование суперкомбинаторов, вытаскиваемых из текста программы с помощью лямбда-лифтинга.

Теперь про алгебраические типы данных и case.

При создании АТД создаются и функции-деконструкторы. Точнее, конструктор АТД представляет собой функцию, принимающую на вход столько функций, сколько вариантов в АТД. При этом количество аргументов функции, соответствующей i-му варианту АТД соответствует количеству аргументов i-го конструктора.

С тем же самым списком:
data List a =
        Nil             -- func_Nil           = \f _ -> f
    |   Cons a (List a) -- func_Cons a list_a = \_ f -> f a list_a
Соответственно, case ничем не отличается от обычного применения функции к аргументам. Вся сложность в его реализации состоит в группировке вложенных сравнений с образцом.

Это используется в STG - Spineless Tagless G-machine, - реализации ленивых вычислений в ghc. На вход конструктора приходит набор функций (на стеке), одну из которых он должен вызвать.

PS
Когда набираю тэги, после буквы 'б' кто-то нехороший вставляет запятую и пробел. Ужо я ему!