VPF::Комбинатор Y - Форум программистов

entrix

Дата 25.4.2010, 18:09 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 25.4.2010

Репутация: нет
Всего: нет

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

Попался в поле зрения так называемый комбинатор 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))))))

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

Это сообщение отредактировал(а) entrix - 25.4.2010, 21:16

k0rvin

Дата 25.4.2010, 20:55 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 442
Регистрация: 24.1.2010

Репутация: нет
Всего: 5

Цитата

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

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

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

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

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

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

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

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

P.S. статью про точку сам нашел (Комбинатор неподвижной точки)

--------------------

“Object-oriented design is the roman numerals of computing.” — Rob Pike
All software sucks

Ryukzak

Дата 25.4.2010, 21:09 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 40
Регистрация: 12.9.2006

Репутация: нет
Всего: 1

Цитата(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 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 442
Регистрация: 24.1.2010

Репутация: нет
Всего: 5

Цитата(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 ;;

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

Это сообщение отредактировал(а) k0rvin - 25.4.2010, 21:53

--------------------

“Object-oriented design is the roman numerals of computing.” — Rob Pike
All software sucks

Ryukzak

Дата 25.4.2010, 22:39 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 40
Регистрация: 12.9.2006

Репутация: нет
Всего: 1

Цитата(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 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 105
Регистрация: 8.7.2005
Где: Москва, Россия

Репутация: 9
Всего: 11

Цитата(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 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 55
Регистрация: 31.1.2007

Репутация: нет
Всего: 0

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

)

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

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

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| LISP \| Следующая тема »