Ну вот интересное про ФП:

http://clean.cs.ru.nl/contents/Addison__Wesley_book/body_addison__wesley_book.html

(Reply to this) (Thread)

Я видел http://lj.rossia.org/users/scholar/4555.html .

В РЕФАЛе (пока ничего не знаю), писали, списки не односторонние.

(Reply to this) (Parent) (Thread)

А что нужно, кстати?

Если практически полезный и популярный, но функциональный язык, то Haskell, скорее всего. Не обязательно же по Душкину.

(Reply to this) (Parent) (Thread)

Скорее интереса (самообразования, раз уж работаю программистом) ради.

А что, в Хаскеле легко подсчитать количество вершин дерева?

В общем, из-за Душкина я плохо понимаю синтаксис, но о возможностях языка он вряд ли врёт.

(Reply to this) (Parent) (Thread)

Мне кажется, что для расширения кругозора лучше всего почитать Филд,Харрисон "Функциональное программирование".
В Хаскелле - легко ;). Хаскелл более популярный язык. И в нем больше функциональных наворотов - функции высшего порядка, например. Но и в Рефале есть интересные возможности, которых нет в Хаскелле.

(Reply to this) (Parent) (Thread)

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

(Reply to this) (Parent) (Thread)

Мне вот не пришлось изучать основные вещи по этой книге (когда начал читать, про многое уже знал, что это и зачем), но в целом мне она показалась вполне хорошей.

(Reply to this) (Parent)

Дипломатичное умолчание о том, что же надо читать, не укрепляет желание разобраться-таки с языком:)

(Reply to this) (Parent)

Может и из-за Душкина Хаскел мне уже не понравился.

Распечатаю теперь "классическую книжку Гурина и Романенко" про РЕФАЛ.

(Reply to this) (Parent) (Thread)

Эээ... в книжке слишком формально изложен Рефал+. А основные концепции Рефала (что лучше и нужно сначала изучить) там спрятаны под наворотами Рефала+.
Еесли начинать изучать Рефал, то лучше начать с чего-нибудь от сюда.

(Reply to this) (Parent) (Thread)

Спасибо. Вероятно, это наиболее полезный комментарий.

(Reply to this) (Parent)

P.S. По поводу Рефала рекомендую посмотреть на реализации Рефал 5 и Рефал+ (или на одну их них - лучше на последнюю ;) ).

(Reply to this) (Parent) (Thread)

Да, я же не диссертацию по истории языка пишу, я и собирался на последнее работающее смотреть.

(Reply to this) (Parent)

Ну зависит от того, конечно, как дерево определить. Если так:

data Tree a = E | N (Tree a) a (Tree a)  

То число содержащихся в нем значений -

n_leafs E = 0    
n_leafs (Tree l _ r) = n_leafs l + 1 + n_leafs r

PS: Но imho Haskell куда проще идет после ML, поскольку идейно он является чем-то вроде ML++ (при довольно сильно перелопаченном синтаксисе, но сохранившем основные понятия)

(Reply to this) (Parent) (Thread)

По Haskell в принципе старое, но довольно внятное введение - Gentle Introduction to Haskell

(Reply to this) (Parent)

Да, это я несколько расчувствовался от конструкций Душкина.

На самом деле он тоже несложные деревья ввёл (тоже бинарные, а не просто деревья), да и без пустого дерева.

data Tree a = Leaf a
| Branch (Tree a) (Tree a)

Тоже пишется:
cnt (Leaf x) = 1
cnt (Branch x y) = cnt x + cnt y

Он же этот вопрос в связи с монадами поднимает.

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

Но и тогда тоже можно написать что-то типа:
xxmultisum (Leaf x,(s,i)) = (s+x*i,i+1)
xxmultisum (Branch x y,(s,i)) = xxmultisum (y, xxmultisum(x,s,i) )
multisum (Leaf x) = x
multisum (Branch x y) = xxmultisum(Branch x y, 0, 1)

Да, проблемы особой нет.

Буду считать, что для моей неокрепшей души Душкин слишком душен.

(Reply to this) (Parent) (Thread)

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

(Reply to this) (Parent) (Thread)

Как уже должно было быть ясным из моих комментариев по поводу вериг для Цепепе (чтобы в безумных тестах он стал якобы медленнее), я вообще не понимаю концепции программирования без "побочных эффектов".

Это уже не программа, а одиночное вычисление. Такие программы должны компилироваться в ?вывод? ответа и всё. (Ну, интерпретация — другое дело, но тогда и сравнивать надо не с Цепепе, а с интерактивной работой в Mathematica-е, например.)

Так что без монад мне, как я понял, Хаскел мне совсем неинтересен.

Мне удобно, когда сначала формально дают синтаксис (который я не вполне понимаю) с кратким описанием, а потом на примерах и теорией разъясняют, что к чему. А у Душкина что-то типа "погружения": нет логической последовательности. И такое ощущение, что и у самого Хаскела что-то похожее (с ленивыми вычислениями и рекурсией):)

(Reply to this) (Parent) (Thread)

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

Я про ML упоминал вполне серьезно - ML + Clean + Haskell - действительно очень сильно отличаются от привычных языков (и вовсе не только тем, что "функциональные") - там, например, система типов очень непривычная (а она для понимания критически важна). Шаблоны программирования совсем другие. То есть языки не сильно сложные, но изучение к синтаксису (он, кстати, очень простой) и семантике не сводится даже на половину.

А монады требуют понимания как минимум классов типов (точнее - классов конструкторов типов), и определенного опыта писания того же самого без них (ввод-вывод в Haskell без монад не пишется, а остальное все спокойно - и как раз понимать, что именно инкапсулируется в этот класс очень полезно).

(Reply to this) (Parent) (Thread)

Ну, сейчас я склонен поизучать РЕФАЛ, а там уж посмотрим.

Но наибольшее, на что рассчитываю — считать какую-нибудь ерунду в качестве хобби. Если бы мне деньги за это платили, то что сказали бы, то и изучал бы (я сейчас программирую на Дельфах, впервые я запустил среду в первый день работы там же, где и сейчас работаю). Забавно, что в этом есть некое невезение: с Дельфами не наблюдается обилия хотя бы отдалённо "шикарных" предложений по работе. И если бы мне надо было программировать на Цепепе (какие-то знания и навыки у меня были и в Паскале, и в Си), то я наверняка уже сменил бы работу:) Правда, я изначально трудоустраивался как специалист по криптографии.

Кстати, как насчёт введения с клавиатуры параметров тестов на случай адекватной оптимизации?

Не думаю, что это сильно изменит результаты ужасного теста с комплексными числами или ?годичной? давности теста с сортировкой, только если в Яве (там, вроде бы, наиболее агрессивная оптимизация, или нет?).

(Reply to this) (Parent)

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

Кроме "побочных эффектов" есть аргументы и результаты. И зачастую этого достаточно. И она многое дает. Например, ленивые вычисления в Haskell'е.
Разбираясь с Haskell'ем или Рефалом, я уверен, Вы и в этой концепции разберетесь.

(Reply to this) (Parent) (Thread)

Так ввод-вывод же через монады в Хаскеле? А монады неудобные. Я об этом.

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

(Reply to this) (Parent)

У Haskell'я (по-моему немаленькому опыту использованя) есть два (наверное больше, но смотря на эти примеры вспомнилось два) интересных свойства.

Во-первых, если программа скомпилировалась (Haskell смог проверить и вывести все типы), то она (с очень большой вероятностью) работает правильно. Это некий аналог физического принципа размерностей - если размерность сходится, то формула близка к истине (ну, иногда константу нужно добавить ;)).

И во-вторых, чем программа короче, тем она понятней и лучше. Например, в multisum использовать монады не нужны, т.к. программа станет длиннее. А говоря об этом примере, я бы написал так:
tree2List :: Tree a -> [a] -- сравните с исходной cnt ;)
tree2List (Leaf x) = [x]
tree2List (Branch x y) = (tree2List x)++(tree2List y)
Потом все функции реализуются в одну сточку:
cnt = sum . tree2List
multisum = sum . zipWith (*) [1..] . tree2List

(Reply to this) (Parent) (Thread)

смог проверить и вывести все типы
Теоретические основы и примеры про вывод типов я прочитал.
работает правильно
Ну это только если с чем-нибудь типа Яваскрипта сравнивать, как мне кажется.

И во-вторых, чем программа короче, тем она понятней и лучше.
Ага. Ещё Перл — отличный пример. Зачем же тогда переменные и типы так сложно называть? Можно же в небольшой программе обходиться одним-двумя символами на идентификатор?

Пример с tree2List не очень гибок, по-моему, ибо предполагает определённый порядок обхода, такой же, как у меня в multisum. Для другого порядка придётся переписать что мой multisum, что tree2List здесь.

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

(Reply to this) (Parent)

> А что, в Хаскеле легко подсчитать количество вершин дерева?

А какие проблемы?


Кстати, можно посмотреть на SML, он попроще Haskell, хотя многие идеи те же.

(Reply to this) (Parent) (Thread)

Да нет проблем, на самом деле, http://lj.rossia.org/users/ppkk/107464.html?thread=441544#t441544 , просто Душкин меня совершенно отвратил, когда с монадами и состояниями это делал четыре страницы. Не могу с тех пор книжку открывать.

(Reply to this) (Parent) (Thread)

Кстати, если не нравятся монады и синтаксис языка кажется сложным, то почему бы не посмотреть на более простые и не до конца функциональные языки? Советую SML, как представителя семейства.

Еще есть лиспы, из них по духу более-менее функционален Scheme --- очень простой язык, можно за день изучить; синтаксис сложным точно не покажется.

(Reply to this) (Parent) (Thread)

Сложным особо не кажется, но у Душкина изложен невнятно.

Синтаксис не понравился.

Я не вижу смысла в программировании в первую очередь "без побочных эффектов": для меня сложность монад неоправданна.

Упомянутые свойства перечисленных языков не вызывают интереса.

Функциональная парадигма у меня не вызывает непонимания.

В РЕФАЛе списки двусторонние (в Scheme-Lisp, как я понимаю, тоже односторонние списки), так что на очереди он.

(Reply to this) (Parent)

Меня ещё ужасно бесят односторонние списки.

(Reply to this) (Parent) (Thread)

Со списками в основном приходится делать map или fold, или что-то подобное. Списки с возможностью обхода в две стороны требуются очень редко. И если требуются, то недолго написать самому.

(Reply to this) (Parent) (Thread)

Я не понимаю разумности данного ограничения.

требуются очень редко
Мне вообще язык этот не требуется. Да и Вы, как я понимаю, не практик.

Неудобства воспринимаю субъективно.

Как-то смущает меня, что вставить элемент в начало или конец — просто, а прочитать — только первый. Сама эта манера писать "x:xs" кажется насилием как "+(a,b)".

(Reply to this) (Parent) (Thread)

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


Так во многих языках. x:xs в Haskell, [H|T] в Prolog, (car . cdr) в лиспах.

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

Вот разумные рассуждения, на мой взгляд:
http://web.onetel.net.uk/~hibou/Doubly%20Linked%20Lists.html

(Reply to this) (Parent) (Thread)

Почитаю.

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

(Reply to this) (Parent)

Ну, anti-pattern так anti-pattern.

С точки зрения устоявшегося Лиспа — наверное, разумные.

О нужности двусвязных списков там не написано по сути, аргументы — какие-то смешные проблемы управления в компиляторе/интерпретаторе Лиспа (что-то там у него, видите ли, меняться должно так, а не иначе), как я понял.

(Reply to this) (Parent)

...евреи обсуждают, что лучше -- haskell или refal. Не стеснялись бы, переходили на иврит.

(Reply to this) (Thread)

РЕФАЛ пишется кириллицей и БОЛЬШИМИ БУКВАМИ!

(Reply to this) (Parent)