#scala #haskell #f#
Пока занимаюсь повторением Python и С, и все никак не дойдут руки до Haskell. А вопрос
не покидает голову уже долгое время) Может как то вкратце можно на него ответить?
Ответы
Ответ 1
Трагедия современных программистов заключается в том, что, изучив школьную математику, и приступая к программированию, они пытаются понять, почему запись x = x + 1 имеет смысл. Когда они это понимают, им сложно научиться мыслить «как раньше». Дмитрий Сошников говорит, что в это время в них умирает функциональный программист. Тем не менее, вспомнить можно, и это не так трудно. Попробуйте решить любое уравнение на бумаге и вы сделаете это в функциональном стиле. Попробуйте вычислить факториал. Вы увидите, что вам не нужна переменная-аккумулятор. Примером переменной-аккумулятора являются классические счёты, и там действительно возникает такое понятие, как состояние. Функциональная запись настолько привычна, что она присутствует во всех императивных языках, кроме некоторых эзотерических. Посмотрите на присваивание g = a * b + c * d + e * f; и скажите, в каком порядке будут выполняться умножения в правой части? Сначала a * b, в конце e * f, или наоборот? a * b и c * d это операнды оператора +, и в таких языках, как C и C++ порядок вычисления операндов не определён. Благодаря этому, компилятор может оптимизировать код. Например, если где-то выше c * d уже вычислили, и значение переменных не поменялось, можно подставить готовое произведение. То, что порядок вычисления не определён, свидетельствует о функциональном стиле. Это он и есть. Если вы захотите вычислить выражение императивно, вам придётся разбить его шаги, или писать на языках Fort или PostScript. Наконец, ещё один способ, «почуствовать» вкус функционального стиля, это записывать вычисления в Excel. Например, не пользуясь функцией SIN сделайте лист для расчёта синусов. Это занимательное задание. Здесь тоже вы определяете только зависимости между ячейками, но не определяете, в каком порядке они вычисляются. Excel, конечно, не Тьюринг-полный вычислитель, тем не менее, он позволяет решить многие практические задачи.Ответ 2
Циклы Для реализации циклических алгоритмов, как вы совершенно верно заметили, в функциональном программировании используется рекурсия. Например: map f [] = [] map f (x:xs) = f x : map f xs Функция map проходит по всему списку и преобразовывает каждый элемент с помощью функции f. Довольно просто. На практике, однако, рекурсия непосредственно используется редко. Как правило функциональные программы выражают циклические операции через уже существующие библиотечные примитивы, такие как функция map приведённая выше. Что-то в таком роде: numbers = [1,2,3,4,5] strings = show <$> numbers Здесь оператор <$> - это псевдоним функции map (стандартный в Haskell), так что выражение show <$> numbers читается как "применить функцию show к каждому элементу списка numbers". Для более сложных случаев существуют более общие аналоги, такие как fold, for, mapM и т.п. Самые простейшие реализованы с помощью рекурсии, а более сложные строятся на простейших. Мутация "Мутацией" в функциональном программировании (и вообще в программировании) называется изменение содержимого ячейки памяти. В языке Haskell мутация в принципе возможна (см. ниже), но на практике её стараются избегать, прибегая к ней лишь в самых крайних случаях. Вместо непосредственного изменения данных, в функциональном программировании принято создавать новые структуры на основе старых. Например: replaceFirst (x:xs) newX = newX : xs Функция replaceFirst "заменяет" первый элемент списка на новый: xs = [1,2,3,4] ys = replaceFirst xs 42 -- Теперь ys = [42,2,3,4] (внимательный читатель заметит, что функция replaceFirst неприменима к пустому списку, но это не относится к текущей дискуссии) Логически операцию replaceFirst xs 42 можно понимать как "заменить первый элемент списка xs на 42", но на практике происходит не совсем это. На самом деле старый список xs жив и здоров, а список ys - это совершенно новый список. Теперь у нас есть выбор: мы можем выкинуть список xs за ненадобностью, чтобы сборщик мусора его потом удалил, или мы можем оставить его "про запас", на будущее. Такой подход открывает очень широкие возможности. Например, нам ничего не стоит хранить историю изменений - или просто для учёта, или с целью вернуться назад во времени, или ещё для чего. Более интересная возможность - распараллеливание программы. Если мы уверены, что старые данные никогда не изменятся, то нет смысла городить семафоры и прочую синхронизацию - можно просто запустить программы параллельно, и всё! - компилятор гарантирует, что они никогда не будут мешать друг другу модифицируя общие данные. Синхронизация данных - краеугольный камень параллельного программирования и основной источник багов. Если вы в этом сомневаетесь, поищите "defensive copy". Q: Вы что же, хотите сказать, что при каждом изменении надо выделять целую новую структуру данных?! Эдак же никакой памяти не напасёшься! Нет, не нужно. Для того, чтобы этого не происходило, в функциональном программировании используются специальные структуры данных, называемые по-английски "persistent data structures". Это такие структуры данных, в которых каждое следующее обновление построено на основе предыдущей версии. Самый простой пример - односвязный список. Представьте себе список: каждый элемент содержит ссылку (указатель) на предыдущий, а самый последний - ссылку на "конец". Как-то так: (1) --> (2) --> (3) --> (4) --> (end) В примере с replaceFirst (см. выше) этот список у меня назывался xs: (1) --> (2) --> (3) --> (4) --> (end) xs _/ Когда я вызвал функцию replaceFirst, она взяла "хвост" списка (начиная с двойки) и присоединила к нему новую "голову" 42. Этот "новый" список я назвал ys: ys _ \ (42)_ \ (1) --> (2) --> (3) --> (4) --> (end) xs _/ Отсюда видно, что для того, чтобы "заменить" первый элемент списка, вовсе не нужно выделять новый блок памяти. Единственная новая ячейка - это сам новый первый элемент, и всё. Все остальные элементы остались на месте. Более того: если я теперь решу, что список xs мне больше не нужен, то сборщику памяти придётся убирать только число 1, поскольку все остальные элементы списка всё ещё задействованы. Также обратите внимание на то, что такой подход возможен только тогда, когда точно известно, что элементы списка никогда не будут изменены. Только при этом условии я могу рассматривать списки xs и ys как два разных списка, хотя они и занимают частично одну и ту же память. Конечно, односвязный список - это самая простая структура данных. В более сложных случаях используются более сложные структуры - в основном деревья всех видов и размеров. И разумеется, есть ситуации, при которых такой подход всё же менее эффективен, чем непрерывный массив в памяти. Однако в 99% случаев разница в быстродействии совершенно ничтожна и не идёт ни в какое сравнение с повышенной стабильностью и простотой разработки. Для оставшегося 1% случаев, однако, даже Haskell позволяет работать с непрерывными массивами - только делает он это гораздо более безопасным образом (см. ниже) Императивные программы "Императивными" называются программы, выраженные в виде последовательности шагов. Это в противовес "декларативным", которые выражены в виде отношений между частями - функциями и данными. Все примеры, приведённые мной выше - "декларативные". Они все написаны в стиле "xs - это ys, где первый элемент заменён на 42" и т.п. На первый взгляд может показаться, что разницы в принципе нет, но это не так. Главная разница в том, что в императивной программе есть порядок действий, а в декларативной - нет. Я указал, как значение xs связано с ys, но не указал, в каком порядке мне хотелось бы, чтобы эта связь вычислялась. Компилятор разберётся за меня сам. Но это не всегда целесообразно. Хотя "в принципе" любую программу можно выразить и тем и другим способом, иногда чисто с человечксой точки зрения удобнее думать о программе как о функциональных отношениях, а иногда - как о последовательности шагов. Например, рассмотрим ту же игру. Представьте, что у меня есть некий тип данных Game и набор операций к нему: type Game = ... lookForMonsters :: Game -> (Game, Monster) shoot :: Monster -> Game -> (Game, Damage) Обратите внимание, что каждая функция, в дополнение к своему "основному" результату (Monster или Damage), возвращает ещё и "новое", изменённое состояние игры. Это "новое" состояние должно быть передано в следующую функцию, за счёт чего и возникает определенный порядок исполнения этих функций, как-то так: game0 = createGame (game1, monster) = lookForMonsters game0 (game2, damage) = shoot monster game1 message = "Inflicted " ++ show damage ++ " points of damage Поскольку значение game1 необходимо для вызова shoot, но является результатом lookForMonsters, выходит, что lookForMonsters нужно вызвать сначала, а shoot - потом. В этом и есть определение порядка вызовов. Такой стиль, однако, весьма утомителен и создаёт опасность опечаток. Кроме того, обратите внимание на закономерность: все строчки очень похожи друг на друга по форме. Функциональный программист живёт закономерностями. Он их находит и безжалостно обобщает, чтобы сделать свой код более простым и понятным. В данном случае давайте завернём эту закономерность в пару функций, которые я назову bind и return: bind x f = \game -> let (game1, y) = x game in f y game1 return x = \game -> x Не вдавайтесь слишком глубоко в подробности, если это непонятно. Достаточно знать, что функция bind "связывает вместе" две операции над игрой, передавая состояние игры из результата первой операции в аргумент второй; а функция return создаёт операцию, которая игнорирует состояние игры и возвращает какое-то конкретное значение. С помощью этих функций я могу записать мою программу так: program = bind lookForMonsters (\monster -> bind (shoot monster) (\damage -> return ("Inflicted " ++ show damage ++ " points of damage) ) ) (finalGameState, message) = program game0 Можно сделать чуть красивее, поиграв с переводами строк и отступами: program = bind lookForMonsters (\monster -> bind (shoot monster) (\damage -> return ("Inflicted " ++ show damage ++ " points of damage))) Или ещё чуть красивее, если завести оператор >>=, который будет синонимом для bind: x >>= f = bind x f program = lookForMonsters >>= \monster -> shoot monster >>= \damage -> return ("Inflicted " ++ show damage ++ " points of damage) Такая схема определения порядка исполнения называется "монад", и она настолько широко применяется в функциональных языках, что большинство компиляторов предоставляет для неё специальный синтаксический сахар. В Haskell эту программу можно записать так: program = do monster <- lookForMonsters damage <- shoot monster return ("Inflicted " ++ show damage ++ " points of damage) Слово do и стрелки влево <- преобразуются компилятором в последовательные вызовы функции bind. После всех этих преобразований, посмотрите, что у нас получилось: программа выглядит как "обычная" императивная программа на каком-то языке вроде C или Python, и смотрится так, как будто мы "изменяем" состояние игры с каждым шагом. Но на самом деле программа целиком состоит из "чистых" функций без мутации и побочных эффектов. Наша программа принимает изначальное сотояние игры на вход и выдаёт конечное состояние на выходе, и не зависит больше ни от чего. Таким образом мы получили возможность писать программу в виде последовательности шагов, но при этом сохранили все преимущества отсутствия мутации. Обобщение Взгляните ещё раз на программу, записанную мной выше в "хитром" виде: program = do monster <- lookForMonsters damage <- shoot monster return ("Inflicted " ++ show damage ++ " points of damage) Обратите внимание, что в этой программе нигде не упоминается сам тип Game - то есть сама программа в общем-то не в курсе, что она работает с игрой. Всё знание об игре "спрятано" в функции bind и в примитивных операциях lookForMonsters и shoot. Кстати, сами эти операции тоже могут и не быть примитивными - они сами по себе могут быть записаны в таком же стиле, как и моя программа, и основаны на ещё более примитивных операциях. Но это просто к слову. А следующая мысль вот какая: если сама по себе программа не зависит от того, как именно реализована идея "порядка операций" (а именно эту идею реализует функция bind), значит мы можем изменить эту реализацию не трогая при этом саму программу. Наша реализация может быть простой и "игрушечной", как я привёл выше, или, если нам понядобятся какие-то дополнительные возможности, например прерывание при ошибках или журналирование, - мы можем добавить эти возможности в функцию bind, и программа этого не заметит. Эта мысль приводит к идее, что "монады" могут быть разные. Более того, монады можно собирать из блоков с нужной функциональностью, как из кубиков, и при этом писать программы, в которых каждая операция пользуется только теми кубиками, которые ей важны, а остальная программа о них не знает. Ввод-вывод И вот теперь, когда у нас есть понятие "монад", который есть абстрактное выражение порядка операций, приходит следующая мысль: а что если изобрести такой монад, который написан не на самом языке Haskell, а реализован внутри компилятора? И что если организовать этот монад таким образом, что функция bind может творить всякие безобразия, нарушать правила, и вообще быть написана на языке C? Программы, написанные в таком монаде, будут выглядеть совершенно невинно - как последовательность функций, пропущенных через bind, так же, как и примеры выше. Но зато примитивные операции будут для реального ввода-вывода. Вот, например, операция getLine: getLine :: IO String Она производит "побочный эффект" в реальном мире - читает текстовую строку с консоли. Но эта строка "завёрнута" в тип IO. Логически можно это рассматривать как ячейку, в которой находится строка, но "достать" эту строку оттуда никак нельзя. Единственное, что можно с ней сделать - это направить её в качестве параметра в другую функцию с помощью вызова bind. Но вот незадача: в результате этого вызова опять обязательно получится тип IO (возможно не со строкой внутри, а с чем-то другим), и оттуда достать значение опять нельзя. Можно только направить его в третью функцию опять с помощью bind - и так далее. В результате выходит, что как только мы произвели ввод-вывод (т.е. вызвали одну из IO-функций), единственное, что можно сделать с результатом - это произвести ещё ввод-вывод, и ещё, и ещё. Но это как раз ничего страшного, потому что точка входа программы на Haskell - это как раз и есть цепь операций ввода-вывода, скреплённых через bind. Например: main = bind getLine (\name -> bind (putStrLn ("Hello, " ++ name ++ "!")) (\_ -> return 0 ) ) Или то же самое с использованием синтаксиса do: main = do name <- getLine putStrLn ("Hello, " ++ name ++ "!") return 0 Вот таким образом и происходит ввод-вывод в Haskell. Самые примитивные операции, такие как getLine и putStrLn, написаны не на самом Haskell, а на C. Это примерно так же, как вызов CreateProcess в Windows или fork в UNIX реализованы не самой программой, а операционной системой. Самые примитивные примитивы всегда находятся на один уровень ниже, без этого никак. Альтернативный взгляд на эту структуру такой: можно рассматривать программу на Haskell как программу, которая сама по себе ввода-вывода не делает, но зато генерирует программу на другом языке, которая уже делает ввод-вывод. Я не большой фанат такого подхода, но его часто используют при объяснениях. Обратите внимание, что, в принципе, можно абсолютно всю программу на Haskell написать непосредственно в IO, и таким образом пользоваться всеми теми же "благами", что и программа на C или Python. Однако это совершенно убьёт всю идею. Смысл языка Haskell в том, что программы можно писать гораздо более безопасные, выразительные и быстрые, если только отказаться от всяких безобразий типа IO и дать компилятору возможность оптимизировать программу. Поверьте, компилятор (особенно компилятор Haskell) справляется с этим на много порядков лучше нас с вами. Поэтому реальные программы обычно написаны в два слоя: самое ядро программы, где вся логика и все вычисления, написано на "чистых" функциях, и только самая внешняя, очень тонкая оболочка имеет дело с IO. В настоящее время этот принцип, называемый по-английски "functional core, imperative shell", стал широко известен и за пределами функционального программирования - как, впрочем, и многие другие функциональные идеи (например, LINQ, const, then, async, auto и т.п.) "Настоящая" мутация Теперь, когда мы познакомились с монадом IO и узнали, что его примитивы могут творить всякие безобразия, следующее что приходит в голову - что эту лазейку можно использовать в случаях, когда Haskell таки недостаточно быстр, требует слишком много памяти, или не устраивает по каким-то другим причинам. В этих случаях можно написать библиотеку на C и импортировать её в Haskell через IO. Один пример такого подхода - массивы с поддержкой "настоящей" мутации. Эта библиотека предоставляет IO-примитивы для создания, изменения и прочих операций над массивами: main = do arr <- newArray (1,10) 42 writeArray arr 8 5 a <- readArray arr 1 print a Как я уже отметил выше, такие возможности используются только в самых крайних случаях - когда Haskell сам по себе "не дотягивает". Я бы сравнил это с написанием программы на C, но с вкраплениями ассемблера в самых чувствительных местах. Программа получается больше, непонятнее, более хрупкой, и ограничивает возможность оптимизации, так как компилятор не знает, что именно происходит внутри этих примитивов, и потому боится их трогать.Ответ 3
Программировать без переменных - невозможно. Во первых, если мы хотим изменить во всём скрипте одно значение, то нам придётся во всей программе изменять это значение (а в скрипте могут быть тысячи, десятки тысяч строк). Во вторых, если нам нужно использовать знаки действий (+, -, *, :), то без переменных не обойтись.
Комментариев нет:
Отправить комментарий