Что хотел написать.
Сперва - про комибинаторы и сложность.
Если мы начнем переводить программу на лямбда-исчислении в комбинаторное, то только 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
Когда набираю тэги, после буквы 'б' кто-то нехороший вставляет запятую и пробел. Ужо я ему!
Если мы начнем переводить программу на лямбда-исчислении в комбинаторное, то только 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
Когда набираю тэги, после буквы 'б' кто-то нехороший вставляет запятую и пробел. Ужо я ему!