Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > LISP > Комбинатор Y

Автор: entrix 25.4.2010, 18:09

Такая вот тема.

Попался в поле зрения так называемый комбинатор Y (подробности тут http://www.wikiznanie.ru/ru-wz/index.php/Комбинатор_неподвижной_точки)

Так вот, как работает, например, вот такая комбинация для вычисления длины списка

(код на scheme)

Код


 (define Y-list
  (lambda (l)
    ((lambda (le)
       (le le l))
     (lambda (le l)
       (if (null? l)
           0
           (+ 1 (le le (cdr l))))))))

Понять не сложно, но вот как работает такой код.

Код


 (define Y
  (lambda (le)
    ((lambda (f)
       (le (lambda (x) ((f f) x))))
     (lambda (f)
       (le (lambda (x) ((f f) x)))))))

Я до конца понять не смог.
Можно ли использовать это определение y-комбинатора для вычисления факториала или длины списка,

Например,

Код


  (define listing
  (lambda (le)
    (if (null? l)
    0
      (+ 1 (le (cdr l))))))

зависает в рекурсии.

Автор: k0rvin 25.4.2010, 20:55

Цитата

К...одвижной точки)
Из проекта Викизнание

- Такой статьи (пока) не существует -

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

Вы можете 1) дать правильную ссылку, 2) переписать код в более понятной форме?

Добавлено через 2 минуты и 14 секунд

Цитата(entrix @ 25.4.2010, 18:09)

Можно ли использовать это определение y-комбинатора для вычисления факториала или длины списка

кстати, зачем?

P.S. статью про точку сам нашел (http://www.wikiznanie.ru/ru-wz/index.php/%D0%9A%D0%BE%D0%BC%D0%B1%D0%B8%D0%BD%D0%B0%D1%82%D0%BE%D1%80_%D0%BD%D0%B5%D0%BF%D0%BE%D0%B4%D0%B2%D0%B8%D0%B6%D0%BD%D0%BE%D0%B9_%D1%82%D0%BE%D1%87%D0%BA%D0%B8)

Автор: Ryukzak 25.4.2010, 21:09

Цитата(entrix @ 25.4.2010, 18:09

)

Можно ли использовать это определение y-комбинатора для вычисления факториала или длины списка,

Можно, когда-то давно считал так факториал, что бы понять как именно это работает. (на листочке)

Вообще очень хорошо это описано вот тут: http://www.cl.cam.ac.uk/~lp15/papers/Notes/Founds-FP.pdf
4.3 Usage of Y

Вроде бы где-то видел и перевод.

Цитата

Могу конечно жестоко ошибать, но вроде rec в ML языках и есть это самый комбинатор. И вполне себе читаемо.

Автор: k0rvin 25.4.2010, 21:51

Цитата(Ryukzak @ 25.4.2010, 21:09)

Могу конечно жестоко ошибать, но вроде rec в ML языках и есть это самый комбинатор. И вполне себе читаемо.

не знаком с ML вообще, Вы имете в виду этот rec (Ocaml):

Код


let rec foldl fn x ys = match ys with
    []    -> x
  | y::ys -> folfl fn (fn x y) ys ;;

без которого нельзя было бы определить рекурсивную функцию?

Автор: Ryukzak 25.4.2010, 22:39

Цитата(k0rvin @ 25.4.2010, 21:51

)

Без подсветки
1:
2:
3:
let rec foldl fn x ys = match ys with
[] -> x
| y::ys -> folfl fn (fn x y) ys ;;

без которого нельзя было бы определить рекурсивную функцию?

Именно его. (Ocaml тоже относится к ML семейству)

Автор: adejneka 27.4.2010, 06:07

Цитата(entrix @ 25.4.2010, 18:09)

Можно ли использовать это определение y-комбинатора для вычисления факториала или длины списка,

Код


(define list-length
  (Y (lambda (len) (lambda (x) (if (null? x) 0 (+ 1 (len (cdr x))))))))

;;;---------------------------
> (list-length '())
0
> (list-length '(a))
1
> (list-length '(a b))
2

Автор: qweqwe 27.4.2010, 12:55

Цитата(Ryukzak @ 25.4.2010, 21:09

)

Могу конечно жестоко ошибать, но вроде rec в ML языках и есть это самый комбинатор. И вполне себе читаемо.

вы есть жестоко ошибать
rec в ML языках, это ключевое слово, служащее цели упрощения вывода типов smile