Ответ на »сообщение 2137« (Руслан Богатырев)
___________________________

На изменение? А как же там насчет отсутствия побочных эффектов?

Пусть A -- инициатор вызова, а Z -- вызываемая функция, при этом Z локальна по отношению к A. Правильно ли я понимаю, что сначала A вызывает Z с некоторыми параметрами, та меняет контекст, а затем A может еще раз вызвать Z с теми же параметрами, при этом результат будет разный (если выполнение Z зависит от контекста)? Более того, в общем случае если контекст меняется и выполнение Z от него зависит (имеет доступ просто на чтение), то при запуске одной и той же функции с одними и теми же параметрами будет получаться разный результат. Или нет?

Ну да, я же говорю: Common Lisp - гибридный язык. так что при его использовании возможны императивные побочные эффекты.
Кстати, Сергей Перовский, по-иоему, приводил как-то пример closure на Javascript, которая меняет глобальную переменную при каждом вызове. Вот Вам пример плохой идеи...
В чистых ФЯ такое невозможно без специальных плясок с бубном, аналогичных использованию модуля SYSTEM в Обероне для имитации адресной арифметики и оператора GOTO...


Я вообще не понимаю, зачем в лоб было переводить как "ленивые". Ведь их суть -- отложенные вычисления. Зачем какие-то странные ассоциации? Чтобы было как у буржуев? :) Энергичный -- можно еще инициативный, бойкий, деятельный, смелый, а если брать антонимы к "ленивый", то трудолюбивый, работящий, прилежный...

Есть устоявшаяся, а потому привычная терминология. Стоит ли её ломать, придумывая новые названия для старых вещей?


>>> "closure" обычно переводят на русский как "замыкание".
Это конечно интересно, но замыкание чего? Функции?

Какого-нибудь состояния внутри функции.

Ответ на »сообщение 2137« (Руслан Богатырев)
___________________________


"closure" обычно переводят на русский как "замыкание".
Это конечно интересно, но замыкание чего? Функции?


http://www.jdl.co.uk/briefings/closures.html

Ответ на »сообщение 2137« (Руслан Богатырев)
___________________________
На изменение? А как же там насчет отсутствия побочных эффектов?
closures не являются механизмом чистого ФП.
Closures это способ инкапсуляции состояния, точно такой же как и private поля в классе.
В данном случае можете считать что замкнутые в closure переменная это private поле обьекта функции.

Кстати поэтому переменные внутри closures не являются аналогом глобальных переменных. Потому что они как раз таки недоступны глобально, а только функции которая их в себе замкнула.

Ответ на »сообщение 2137« (Руслан Богатырев)
___________________________
Переводить на русский надо смысл а не слово.
В этом плане ленивые - неленивые вычисления правильно было бы переводить как отложенные - немедленные.

Насчет монад. Монады это вообще то тип данных.
Соответственно в строго типизированном языке работать с ними (принимать как параметры) могут только функции которые ожидают именно этот тип.
Это предотвращает передачу данных типа монад в функцию, которая ожидает скажем string
Вот вам и барьер в распространении состояния.
Хотите работать с данными в монаде, передавая их в чистую функцию - извольте сначала их из этого контейнера извлечь.

Ответ на »сообщение 2133« (Geniepro)
___________________________

Хотя, впрочем, это справедливо только для языков со статическим связыванием контекста - таких, как Хаскелл, ML, Scheme. Есть диалекты Лиспа (кажется в Common Lisp) с динамическим связыванием контекста, и, так как Common Lisp - гибридный язык, то вызываемая функция имеет полный доступ к внутреннему контексту вызываемой функции, в том числе и на изменение его...

На изменение? А как же там насчет отсутствия побочных эффектов?

Пусть A -- инициатор вызова, а Z -- вызываемая функция, при этом Z локальна по отношению к A. Правильно ли я понимаю, что сначала A вызывает Z с некоторыми параметрами, та меняет контекст, а затем A может еще раз вызвать Z с теми же параметрами, при этом результат будет разный (если выполнение Z зависит от контекста)? Более того, в общем случае если контекст меняется и выполнение Z от него зависит (имеет доступ просто на чтение), то при запуске одной и той же функции с одними и теми же параметрами будет получаться разный результат. Или нет?

"closure" обычно переводят на русский как "замыкание".
Это конечно интересно, но замыкание чего? Функции?

Обычно используется термин "энергичные вычисления", а не "прямые".

Я вообще не понимаю, зачем в лоб было переводить как "ленивые". Ведь их суть -- отложенные вычисления. Зачем какие-то странные ассоциации? Чтобы было как у буржуев? :) Энергичный -- можно еще инициативный, бойкий, деятельный, смелый, а если брать антонимы к "ленивый", то трудолюбивый, работящий, прилежный...

Вообще, монады упрощённо - это некие контейнеры.

Контейнер должен обеспечивать изолирование (в этом смысле понятно) и возможность перемещения в пространстве. Куда и что там можно перемещать? А может, это просто клеймо? Если не ошибаюсь, в Древней Греции на лбу у рабов выжигали клеймо (вроде как "Верни беглого такому-то"). С монадами, случаем, не так?

Ответ на »сообщение 2135« (Jack Of Shadows)
___________________________
Упс, неполный код.
Добавочка:

-- fold up a list like a tree
treefold f z []      = z
treefold f z [x]    = x
treefold f z (a:b:l) = treefold f z (f a b : pairfold l)
                where pairfold (x:y:rest) = f x y : pairfold rest
                  pairfold l          = l

Ответ на »сообщение 3337« (slava)
___________________________

Hepasort на хаскеле:

data Heap a = Nil | Node a [Heap a]
heapsort :: Ord a => [a] -> [a]
heapsort = flatten_heap . merge_heaps . map heapify

    where heapify x  = Node x []

      merge_heaps :: Ord a => [Heap a] -> Heap a
          merge_heaps = treefold merge_heap Nil

          flatten_heap Nil            = []
          flatten_heap (Node x heaps) = x:flatten_heap (merge_heaps heaps)

          merge_heap Nil                    Nil = Nil
          merge_heap heap@(Node _ _)        Nil = heap
          merge_heap node_a@(Node a heaps_a) node_b@(Node b heaps_b)
                    | a < b    = Node a (node_b : heaps_a)
                    | otherwise = Node b (node_a : heaps_b)

Где вы там узрели сильное усложнение или даже изменение алгоритма я так и не понял.
По существу алгоритм описан один в один как в описании задачи.

Ответ на »сообщение 2127« (Руслан Богатырев)
___________________________

Для очищения ФП от "инопланетных" императивных вещей (обычно связанных с общением ФП с внешним миром) используется такое понятие, как монады (monads).

Кстати, в языке Clean предлагается другой подход - можно обрабатывать объекты-экземпляры специальных "уникальных" (unique) классов, при этом все эти объекты хранятся в одной и той же области памяти, то есть по сути происходит деструктивная обработка этих объектов.
Это позволяет добиться такой же эффективности, как в обычных императивных языках, но при этом побочных эффектов вроде как и нет, потому что это объекты уникальных классов. То есть компилятор гарантирует, что в любой момент времени существует только одна ссылка на такой объект. А значит побочных эффектов другим частям программы не видны...

Ответ на »сообщение 2127« (Руслан Богатырев)
___________________________

Давайте попробуем разобрать модель ФП с позиций императивщика. Представим себе, что перед нами стоит задача реализовать run-time для какого-то ФЯ.
[чик-чик]
Ничего существенного не забыл?
...
1. Функция имеет доступ к контексту вызова внешней функции -- инициатора вызова, причем только на чтение.

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

Хотя, впрочем, это справедливо только для языков со статическим связыванием контекста - таких, как Хаскелл, ML, Scheme. Есть диалекты Лиспа (кажется в Common Lisp) с динамическим связыванием контекста, и, так как Common Lisp - гибридный язык, то вызываемая функция имеет полный доступ к внутреннему контексту вызываемой функции, в том числе и на изменение его...


3. Функция возвращает результат в виде функции или атома/списка.

В современных ФЯ (обычно с системой типов Хиндли-Милнера) функции могут также возвращать кортежи (tuples), которые хранят в себе фиксированное число элементов возможно разных типов. Этим кортежи отличаются от списков, хранящими в себе разное количество элементов одного типа.
В лиспах списки могут хранить объекты разных типов, поэтому нужды в кортежах там нет...

"closure" обычно переводят на русский как "замыкание".
прямые и отложенные (ленивые) вычисления
Обычно используется термин "энергичные вычисления", а не "прямые".

Для очищения ФП от "инопланетных" императивных вещей (обычно связанных с общением ФП с внешним миром) используется такое понятие, как монады (monads). Монады вбирают в себя сугубо последовательные вещи (напр., ввод-вывод), а также изменения в состояниях без использования языковых конструкций с побочными эффектами. Это "свободные экономические зоны" (если кому-то больше нравится -- "гетто"), имеющие жесткие границы (ограничения) с миром чистого ФП.

Вообще, монады упрощённо - это некие контейнеры. Например, списки в Хаскелле - представители монадного класса MonadPlus - то есть тоже монады. Монады сами по себе не являются тюрьмой для императивных эффектов, но, например, ввод/вывод в Хаскелле реализован с использование монад. Именно монада IO является контейнером для императивных побочных явлений, связанных с вводом/выводом, и не даёт расползаться этим побочным эффектам по всей программе. Также монады предлагается использовать как своего рода модули, которые так расхваливают адепты модульного программирования.
Ссылки по теме:
S. Liang, P. Hudak, M. Jones, "Monad Transformers and Modular Interpreters
W. Harrison, S. Kamin, "Modular Compilers Based on Monad Transformer"
J. Gayo, J. Lovelle, C. Dнez, "Language Prototyping using Modular Monadic Semantics"