описания чего?

назначение этих функций понятно по названию

Ну ладно

++

Опять же, берёте любую задачу поиска(вычисления) чего-то в цикле и решаете с помощью свёртки

BFS, DFS, A*, ватева

http://www.cs.nott.ac.uk/~pszgmh/fold.pdf и вот пейпер в тему, забыл совсем

"A tutorial on the universality and expressiveness of fold"

Conal Elliott’s: "Folds and unfolds all around us" и вот

Есть две программы:

Программа 1:

main :: IO ()
main = interact f

f :: String -> String
f s = s

Программа 2:

main :: IO ()
main = interact f

f :: String -> String
f s = reverse (reverse s)

Эти программы ведут себя по-разному - первая программа выводит вводимые строчки по мере поступления, а вторая после окончания ввода.

Но ведь функции f абсолютно эквивалентны на конечных строках.

Получается, то, что я внутри функции f два раза реверснул строку, имеет сайд-эффекты?
И, получается, что в теории можно реализовать любую интерактивную программу внутри f :: String -> String?

Наверное, это связано с ленивостью, но ведь порядок вычисления не должен влиять на результат.

Почему эта функция всё ещё чистая?
Вызовы двух таких функций нельзя поменять местами, так как это поменяет поведение, и т.д.
Это же всё ломает!
По-моему такое невозможно построить на лямбда-термах и на чистых функциях.

В общем, мои вопросы такие:
* Как это устроено с точки зрения лямбда-термов? Внутри получаемого аргумента-терма используются какие-то нечистые функции, или как такое поведение стало возможным?
* Видимо, я чего-то не понимаю. Где я не прав / неправильно смотрю на происходящее? Может, у кого-то тоже был такой "шок", а потом вы поняли, как к этому нужно относиться?

Буду благодарен любым ответам / пояснениям

f — функция чистая, а вот interact — нет.

interact :: (String -> String) -> IO ()

Вот её тип, где собственно IO и появляется и interact на вход принимает лишь чистые функции.

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

В случае с двумя вариантами f выше, это выполняется.

И именно в interact будет меняться порядок потребления ввода.

Я правильно понимаю, что:

С точки зрения Haskell, было бы вполне легальным такое устройство программы, при котором она выглядит как
processEvents :: [InputAction] -> [OutputAction]
Где оба списка лениво вычисляются и за счёт этого происходит взаимодействие?

Скажем, первым элементом списка-результата ставим requireRandom, после чего из списка-аргумента первым элементом берём сгенерированное число, как-будто оно всегда там лежало, и так далее.
processEvents input = [requireRandom, "Случайное число: " ++ head input]

Такое теоретически вполне можно было бы реализовать?

когда-то так и было реализовано

Ого