Современные функциональные языки

=KRoN=>>>Дык, прямая дорога в функциональные языки.
Mishka>>Это как? Lisp просто человеку тоже объснить очень трудно.

=KRoN=>Э... Лисп - не единственный функциональный язык!

=KRoN=>Вот то ли дело, например, Haskell:

module Main where
factorial n =

[/html_font]
Ради интереса попробуй объснить связь этой строчки с последующими школьнику. Неявно здест есть заплетение рекурсии через переменные. Кроме этой сложности - есть еще одна - рекурсия. Здесь проблемы даже не в понимании выражения чего-то через само себя, а пунктик выхода из рекурсии.

module Main where
  if n > 1
    then n * (factorial n-1)
    else 1
main = do
  show (factorial 30000)

Я уж не говорю про 0!

=KRoN=>Впрочем, O'Caml тоже хорош:
[html_font color=blue]

let rec fib n =
  if n<2 then 1 else fib(n-1)+fib(n-2);;

=KRoN=>А скорость у последнего кода! На уровне лучших компиляторов C++!

Да и примеры с этими рекурсивными функциями на Паскаля очень изящно ложаться. А на Алгол 68 - сказка
Впрочем, O'Caml тоже хорош:

proc f( int n )
begin
if ( n = 0 )
then 1
else n * f( n - 1 )
fi
end
[/code]

Mishka>Ради интереса попробуй объснить связь этой строчки с последующими школьнику. Неявно здест есть заплетение рекурсии через переменные. Кроме этой сложности - есть еще одна - рекурсия.

Всё же, рекурсия изначально более интуитивна, чем переменные

Mishka>Я уж не говорю про 0!

А 0 не натуральное число И под классическое определение факториала 0! уже не подгонишь. Всё равно, что квадратный корень на счётных палочках учить

Mishka>

Mishka>
Mishka>procf( int n )
Mishka>begin
Mishka>  if ( n = 0 )
Mishka>  then 1
Mishka>  else n * f( n - 1 )
Mishka>  fi
Mishka>end
Mishka>

int f(int n) { return n>1 ? n*f(n-1) : 1; }



Впрочем, меня вот что умиляет в Haskell'е:

fact n = if n > 1 then n * fact(n-1) else 1

main = do print(fact 1000)

✂

4023872600770937735437024339230039857193748642107146325437999104299385123
9862902059204420848696940480047998861019719605863166687299480855890132382
9669944590997424504087073759918823627727188732519779505950995276120874975
4624970436014182780946464962910563938874378864873371191810458257836478499
7701247663288983595573543251318532395846307555740911426241747434934755342
8646576611667797396668820291207379143853719588249808126867838374559731746
1360853795345242215865932019280908782973084313928444032812315586110369768
0135730421616874760967587134831202547858932076716913244842623613141250878
0208000261683151027341827977704784635868170164365024153691398281264810213
0927612448963599287051149649754199093422215668325720808213331861168115536
1583654698404670897560290095053761647584772842188967964624494516076535340
8198901385442487984959953319101723355556602139450399736280750137837615307
1277619268490343526252000158885351473316117021039681759215109077880193931
7811419454525722386554146106289218796022383897147608850627686296714667469
7562911234082439208160153780889893964518263243671616762179168909779911903
7540312746222899880051954444142820121873617459926429565817466283029555702
9902432415318161721046583203678690611726015878352075151628422554026517048
3304226143974286933061690897968482590125458327168226458066526769958652682
2728070757813918581788896522081643483448259932660433676601769996128318607
8838615027946595513115655203609398818061213855860030143569452722420634463
1797460594682573103790084024432438465657245014402821885252470935190620929
0231364932734975655139587205596542287497740114133469627154228458623773875
3823048386568897646192738381490014076731044664025989949022222176590433990
1886018566526485061799702356193897017860040811889729918311021171229845901
6419210688843871218556461249607987229085192968193723886426148396573822911
2312502418664935314397013742853192664987533721894069428143411852015801412
3344828015051399694290153483077644569099073152433278288269864602789864321
1390835062170950025973898635542771967428222487575867657523442202075736305
6949882508796892816275384886339690995982628095612145099487170124451646126
0379029309120889086942028510640182154399457156805941872748998094254742173
5824010636774045957417851608292301353580818400969963725242305608559037006
2427124341690900415369010593398383577793941097002775347200000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000

✂

=KRoN=>>Дык, прямая дорога в функциональные языки.
Mishka>Это как? Lisp просто человеку тоже объснить очень трудно.

Э... Лисп - не единственный функциональный язык!

Вот то ли дело, например, Haskell:

module Main where

factorial n =
  if n > 1
    then n * (factorial n-1)
    else 1

main = do
  show (factorial 30000)

[/html_font]

Впрочем, O'Caml тоже хорош:
[html_font size=+0]

let rec fib n =
  if n<2 then 1 else fib(n-1)+fib(n-2);;

А скорость у последнего кода! На уровне лучших компиляторов C++!

Крон, ты действительно считаешь, что всем проще понять рекурсию, чем переменные?..

Не всем

Человеку, далёкому от программирования, по-моему, не сложно

Что-то до тонкостей - по-моему, проблему выхода из рекурсии объяснить даже проще, чем, например, глобальные/локальные переменные, побочне эффекты от изменения переменной и т.п.

Гы. Хрен там с рекурсией. Я от Haskell'а просто в угаре

fibz = 1 : 1 : [ x+y | (x,y) <- zip fibz (tail fibz)]


Создаём список чиел Фибоначчи. Первые два элемента заданы явно, следующий определён как список попарных сумм элементов двух списков, один из которых этот же список чисел, другой - он же, но с отброшенным элементом. Сложно в объяснении, но просто на деле: [1, 1, fib(2)+fib(1), fib(3)+fib(2), ...]

В общем, одна такая строчка.

Как это ни парадоксально, но я ещё не знаю, как посмотреть i-й элемент списка, так что пишу тупо:

get 1 (x:) = x
get n (:xs) = get (n-1) xs

Т.е. get для первого элемента списка - равен первому элементу списка, для всех остальных индексов - это get от n-1 от хвоста списка.

В результате fib(2500) = 131709....4751875 (525 цифр!) вычисляется за какие-то доли секунды, я даже измерить не могу Напомню, что на VC7, при рекурсивном вычислении, fib(40) считается почти 4 секунды Понятно, что fib(2500) на нём посчитать вообще в лоб не выйдет, т.к. придётся писать библиотеку для работы с числами большой разрядности

В общем, я хренею

Быструю сортировку я уже приводил. Хотя только сейчас до меня дошла вся изящность решения:
[blue]
qsort [] = []
qsort (x:xs) = qsort[y|y<-xs,y>=x] ++ [x] ++ qsort[y|y<-xs,y<x]
[/blue]
— для пустого списка - результат пустой
— для списка - берём рекурсивно отсортированные элементы, которые больше или равны первому элементу списка, добавляем к списку сам первый элемент списка, и в конце - рекурсивно отсортированные элементы, которые меньше нашего первого элемента

fact 1 = 1
fact n = n * fact (n-1)
main = print [ fact x | x <- qsort [1,3,9,23,8,1,5,9]]

Вывести факторалы от элементов отсортированного по убыванию списка

Супер!

The Evolution of a Haskell Programmer
(на примере вычисления факториала )



Iterative Haskell programmer
(former Pascal programmer)

1. fac n = result (for init next done)
2.         where init = (0,1)
3.               next   (i,m) = (i+1, m * (i+1))
4.               done   (i,_) = i==n
5.               result (_,m) = m
6.  
7. for i n d = until d n i

Можно скромный вопрос. А что вааще понимается под функциональными языками?

---

я всего лишь сис./сет. админ...

Языки, где вся программа описывается набором функций. Наиболее коротко - языки, где нет операций присваивания и нет переменных в классическом понимании этого слова. В отличе от "обычных" - императивных. Программа - это не набор последовательных действий/циклов/переходов, а набор условных/безусловных вызовов функций, как в математике.

Вообще-то, я долгое время считал ФЯ сугубо академической штукой, но последнее время интерес к ним серьёзно растёт. Даже в MS .NET включается Mondrian - в чём-то - наследник Haskell'а.

Говорят, что эффективность прикладного программирования на ФЯ выше, чем на императивных языках с ООП.

Есть, кстати, "гибридные" языки - Ocaml, например, функциональный язык (хотя и не "чистый") с поддержкой ООП.

Но я для себя пока на практике не нахожу применимости для ФЯ и пользуюсь пока классикой, типа Perl'а, хотя в оном, как раз, кое-что и из ФЯ есть. Типа частичной ленивости вычислений, лямбда-функций и т.п.

Вот, кстати, хорошая статья:

Сильные стороны функционального программирования

=KRoN=>Что-то до тонкостей - по-моему, проблему выхода из рекурсии объяснить даже проще, чем, например, глобальные/локальные переменные, побочне эффекты от изменения переменной и т.п.
Область видимости

Mishka>Ради интереса попробуй объснить связь этой строчки с последующими школьнику.
Специально для обучения программированию были Н. Виртом придуманы языки Паскаль и Модула.
Не стоит начинать обучение с Fort или C++!!!

Mishka>>Ради интереса попробуй объснить связь этой строчки с последующими школьнику.
V.B.>Специально для обучения программированию были Н. Виртом придуманы языки Паскаль и Модула.
V.B.>Не стоит начинать обучение с Fort или C++!!!

Вить, а хрен редьки не слаще. Это не настолько очевидные концепции сами по себе. Согласен, что язык может затмить смысл самой концепции, но и без языка здесь трудностей хватает. Я вел информатику в 45 интернате, что в Старом Петергоффе. Это интернат для одареныых детей, мы там много людей для лаборатории находили. И то, не одно занятие и беседа понадобились, чтобы довести до ребят и области видимости, и рекурсию.

Хе... с факториалами - прикольно Но какая разница? ИМХО, не самый наглядный пример. На сях - это тоже не громоздко.

А что ОВерблядь ( ОКамл) уже не юзает гцц?

asoneofus>Хе... с факториалами - прикольно Но какая разница?

Дык, давно известно, что нет "общего" бенчмарка А для общей оценки и факториал сгодится

>На сях - это тоже не громоздко.

Многоразрядные целые? Так это ж опять писать нужно!

Кстати, на Python тоже целые неограниченной длины. Только он в несколько раз медленнее Хаскелла.

Хотя, кроме них в тестах никого с длинными целыми не было.

Или ты о чём вообще?

>А что ОВерблядь ( ОКамл) уже не юзает гцц?

Именно GCC юзает. Тем не менее, получается шустрее зачастую не только GCC, но и MSVC7 (у него оптимизатор помощнее). Что показывает, что типичный исходник на C/C++ - не лучшее, что можно скормить оптимизатору

ComputerMage>Смотрю я на это и у меня смутное ощущение, что Хаскел имеет корни от Пролога [/i]

Там длинная цепочка... Где-то у меня был ОГРОМНЫЙ рисунок с росписью, кого родил Адам, а кто родил Иакова... Ведь, даже на Авиабазе его кидал где-то... :-/

А! Нашёл!

http://airbase.ru/forums/index.php?s=&act=...l=haskell&st=30

На тему Хаскелла смотреть вторую схему.

Увы, прямым потомком Пролога он не является

Balancer>Многоразрядные целые? Так это ж опять писать нужно!

За 20 лет программирования многразрядные целые понадобились мне только один раз - вчера . Надо было найти остаток по модулю 97 для очень длинного целого десятичного числа, записанного как массив символов (в примере - acc). Вот как я это решил:

  int i, mod;
  for (i = 0, mod = 0; acc [i]; i++)
    mod = (((int)acc [i] - (int)'0') + mod * 10) % 97;