у меня есть такая функция
iter :: Int -> (a -> a) -> a -> a
iter n f a = f (f ... (f a) .. )
как я могу определить такую функцию в нетипизированном лямбда-исчислении?
любой намек/помощь будут оценены.
Итерационная функция в лямбда-исчислении
Ответы (2)
Числа не существуют как таковые в чистом лямбда-исчислении. Вы должны разработать представление для чисел (и показать, что они действительно ведут себя как числа). Основная идея заключается в том, что вы можете определить числа так, чтобы они были именно функцией итерации, которая вам нужна: n будет лямбда-термом, который при задании функции f вычисляет n-ю итерацию f.
Это идея, известная как церковное кодирование.
person
gasche
schedule
26.04.2011
Спасибо за ваш ответ, вы абсолютно правы, я понял это позже, это дало бы представление цифр Чёрча в лямбда-исчислении.
- person dinsim; 26.04.2011
person
schedule
Я разработал и реализовал диалект Лиспа, строго типизированный с неявными типами, где функция iter может быть записана с использованием y-comb следующим образом:
(let ((p (fn u (fn v (v ((u u) v))))) (Y (p p)) (iter (Y (fn (lazy iter) (fn (n f a) ((eqw n 0) a (iter (subw n 1) f (f a)))))))) (iter 3 (fn x (mulw x x)) 2)), а также как: ((label iter (fn (n f a) ((eqw n 0) a (iter (subw n 1) f (f a))))) 3 (fn x (mulw x x)) 2)
- person Taoufik Dachraoui; 12.03.2020
используя функцию iter, мы можем построить циклическую структуру следующим образом:
((label iter (fn (n f a) ((eqw n 0) a (iter (subw n 1) f (f a))))) 3 (fn x (set (cdr x) (cons x nil))) (cons nil nil))
- person Taoufik Dachraoui; 12.03.2020
...? (Я знаю, что вы думаете, это значит, но именно в этом и заключается ваша проблема.) - person Eli Barzilay schedule 25.04.2011