Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 82
Спасибо, интересно было посмотреть.
Да, действительно «Haskel» никто не угадал, добавте к «Haskel» еще одну 'l'. (:
А если серьезно, то, наверное, большенство отгадало, haskell единственный чисто функциональный язык в списке.
Да, действительно «Haskel» никто не угадал, добавте к «Haskel» еще одну 'l'. (:
А если серьезно, то, наверное, большенство отгадало, haskell единственный чисто функциональный язык в списке.
А теперь давайте проанализируем, почему же получились такие результаты? Наверное дело не совсем в «функциональности» языка, а в его «многословности». На java часто поступают жалобы из-за ее verbose style, что мы и увидели на графе — слегка запутанная семантика. А структурированность ассемблера не так уж удивительна, ведь операторов в нем не так уж и много и они часто используются. Судя по всему подобные графы — это репрезентация какой-то что ли поэтичности :) как в примере с «Анчаром» Пушкина. Следовательно, языки с наиболее красивыми графами — более поэтичны и душа поет, когда на них пишешь :)
Да, угадать было несложно, Хаскель немногословен и функционален. Но есть маленькое но.
Это немножко не тот quick sort, что у остальных языков.
Его можно почти прямо переписать на другие языки, если там есть лямбды, выглядеть будет пострашнее, но всё равно.
К сожалению, быстрого алгоритма и при этом красивого я не видел.
qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qosrt (filter (>= x) xs)
Это немножко не тот quick sort, что у остальных языков.
Его можно почти прямо переписать на другие языки, если там есть лямбды, выглядеть будет пострашнее, но всё равно.
К сожалению, быстрого алгоритма и при этом красивого я не видел.
Переносы убрались (как их в коде проставить?)
qsort [] = []
qsort (x:xs) = qsort (filter (<x) xs) ++ [x] ++ qsort (filter (>= x) xs)
Наверное такой вариант будет лучше и быстрее. Не знаю. Но на глаз памяти он меньше должен есть :)
quicksort x =
quicksort' x []
where
quicksort' [] y = y
quicksort' [x] y = x:y
quicksort' (x:xs) y = part xs [] [x] []
where
part [] l e g = quicksort' l (e ++ (quicksort' g y))
part (z:zs) l e g
| z > x = part zs l e (z:g)
| z < x = part zs (z:l) e g
| z == x = part zs l (z:e) g
Жаль нет C#… Хотелось бы увидеть его на общем фоне (думаю будет что-то типа Java).
Да, у него абсолютно такой же граф получился
Думаете при использовании лямбда выражений будет тоже самое?
Думаю граф будет не очень ужасным
public static IEnumerable<double> s(IEnumerable<double> arr)
{
if(arr.Count()<=1)
return arr;
var c = arr.First();
var sMin = arr.Where(x => x < c);
var sMax = arr.Where(x => x > c);
return s(sMin).Union(new []{c}).Union(s(sMax));
}Думаю граф будет не очень ужасным
Это рабочий пример?
Вот его граф, не так уж и хорош, как на Хаскеле :)
Вот его граф, не так уж и хорош, как на Хаскеле :)
Или чуть более изящно, но думаю граф не изменится.
public static IEnumerable<double> s(IEnumerable<double> arr){
var c = arr.FirstOrDefault();
return arr.Count() <= 1 ? arr : s(arr.Where(x => x < c)).Union(new[] { c })
.Union(s(arr.Where(x => x > c)));
}Не, граф стал тоже поизящнее :)
Можно его еще немного урезать, но уже читерскими методами:
Таким образром сортировка становится private членом класса, становится нестатической.
К тому-же парсер не далует однобуквенные сочетания — заменяем имя массива.
Ну и вместо удобного var можно использовать double, который добавит только новые связи.
По идеи граф станет не таким кластеризованным (тут видно два кластера — обьявление функции и ее реализация), но число вершин станет меньше.
IEnumerable<double> sort(IEnumerable<double> a){
double c = a.FirstOrDefault();
return a.Count() <= 1 ? a : sort(a.Where(x => x < c)).Union(new[]{ c })
.Union(sort(a.Where(x => x > c)));
}Таким образром сортировка становится private членом класса, становится нестатической.
К тому-же парсер не далует однобуквенные сочетания — заменяем имя массива.
Ну и вместо удобного var можно использовать double, который добавит только новые связи.
По идеи граф станет не таким кластеризованным (тут видно два кластера — обьявление функции и ее реализация), но число вершин станет меньше.
Воо. Таки я ошибся, граф куда лучше явавского.
С Фортрантом не угадал, а насчет Хаскела — был уверен, что он будет первый
Ух, откуда вы все про Хаскел знаете? :)
Ну так тут не просто кодеры собрались, а как по другому без хаскела?
Я про хаскел только название слышал :)
А так — все по старинке, C да C++
А так — все по старинке, C да C++
Ну это вы зря, попробуйте хаскел, lisp, SICP почитайте, мозги очень будут вам благодарны
lisp изучал и даже писал что-то на нем давным давно. Из других языков изучаю более востребованные на мой взгляд — из .net, java, ActionScript и т.п.
А для вникания в Хаскел, лисп и SICP нужно гораздо больше времени, чем для простых языков. А времени всегда не хватает
А для вникания в Хаскел, лисп и SICP нужно гораздо больше времени, чем для простых языков. А времени всегда не хватает
Угадал оба! Но скорее не в силу экстрасенсорных способностей, а потому что по невнимательности не заметил ассемблер и алгол :). Ну а с хаскеллом все ясно было с самого начала.
а брейнфак не учавствовал по причине явного преимущества — отсутствии слов?
Хаскелл однозначно рулит… Последние месяца три разбираюсь, и все больше начинаю влюбляться.
Однако, все еще немного дергает из-за плотности упаковки информации в коде. Монады, стрелки, list comprehentions… Это все просто такие крутые способы запихнуть максимум алгоритма в минимум кода. Изучать язык надо поаккуратней и подольше.
Однако, все еще немного дергает из-за плотности упаковки информации в коде. Монады, стрелки, list comprehentions… Это все просто такие крутые способы запихнуть максимум алгоритма в минимум кода. Изучать язык надо поаккуратней и подольше.
Посмотрите язык K :) Причем это вполне коммерческий язык
Да ну его в болото! Во-первых, пропиетарный, во-вторых, еще более редкий, чем даже сравнительно маргинальный Хаскелл.
Хотя вот про Гуй на Вики пишут, что очень круто и просто пишется. Сие есть истина, не знаешь?
Хотя вот про Гуй на Вики пишут, что очень круто и просто пишется. Сие есть истина, не знаешь?
Не сказал бы что более редкий, он (точнее Q + Kdb) имхо более востребован чем Хаскел. Хотя и там и там проектов кот наплакал.
А Гуй на нем не представляю как нарисовать… для кнопочек и прочих окон там разве чтото есть?
А Гуй на нем не представляю как нарисовать… для кнопочек и прочих окон там разве чтото есть?
Даже не знаю, как вообще можно сравнивать промышленную потребность в таких редких языках по России :-) Но на слуху вроде больше Хаскелл.
Из функциональных здесь я только по Erlang вакансии встречал.
Из функциональных здесь я только по Erlang вакансии встречал.
Я знаю как минимум 1 коммерческий проект выполненный на K в России, т.е. с этим проектом я лично знаком. Есть большие подозрение что помимо него были другие, но конечно очень мало. На Erlang'е проектов гораздо больше. K берут из-за того что на нем офигительно быстро можно считать всякие OLAP, а Erlang потому что он не то что железобетонный, он вообще нерушим, что важно для приложений с 5ю девятками. А Haskell ничем таким, кроме самого языка, не засветился :( Но сам язык отличный, спору нет.
Да, примером я его указал не как язык круче или еще что. А как пример минимума кода
Странно, что вы Perl упустили? довольно лаконично:
Почему-же, я вполне ожидал увидеть Haskell или ocaml. Выразительная сила этих языков вполне себе хороша.
Модифицировал функцию для PHP, сделав ее более лаконичной:
… что, однако, не повлияло, как мне показалось, на красивость графа:
function mine_quicksort($seq) {
$length = count($seq);
if ($length == 0) {
return $seq;
}
$x = $y = array();
$k = array_shift($seq);
$x = array_filter($seq, create_function('$s', 'return $s <= '.$k.';'));
$y = array_diff($seq, $x);
return array_merge(mine_quicksort($x), array($k), mine_quicksort($y));
}… что, однако, не повлияло, как мне показалось, на красивость графа:
Зачем модифицировать функцию на PHP если Like most PHP sorting functions, sort() uses an implementation of Quicksort?
Так что на PHP граф будет эквивалентен Haskell.
Так что на PHP граф будет эквивалентен Haskell.
Переработал исходник на PHP и получил вот это:
Теперь граф выглядит так:
function mine_quicksort($seq) {
$f = array('count', 'array_shift', 'array_filter', 'create_function', 'array_diff', 'array_merge', 'mine_quicksort');
$l = $f[0]($seq);
$r = $seq;
if ($l != 0) {
$x = $y = array();
$k = $f[1]($seq);
$x = $f[2]($seq, $f[3]('$s', 'return $s <= '.$k.';'));
$y = $f[4]($seq, $x);
$r = $f[5]($f[6]($x), array($k), $f[6]($y));
}
return $r;
}Теперь граф выглядит так:
Подсмотрел, что нахваливаемый всеми Haskell добивается такого графа за счет того, что программа уважаемого автора (точнее GraphViz) не учитывает в качестве слов последовательности меньшие по длине, чем 2 буквы. Соответственно, модифицировал исходник и получил вот что:
Правда, получился уже какой-то ассемблер.
Вот результат:
function q($s) {
$f = array('count', 'array_shift', 'array_filter', 'create_function', 'array_diff', 'array_merge');
$l = $f[0]($s);
$r = $s;
if ($l != 0) {
$x = $y = $m = array();
$k = $f[1]($s);
$x = $f[2]($s, $f[3]('$s', 'return $s <= '.$k.';'));
$y = $f[4]($s, $x);
$m[] = $k;
$r = $f[5](q($x), $m, q($y));
}
return $r;
}Правда, получился уже какой-то ассемблер.
Вот результат:
Переделал реализацию заново, с минимальным использованием функций PHP.
Заранее предупреждаю: это чисто спортивный интерес, реализовывать quicksort на PHP (да еще и так!) не нужно!
Получилась вообще какая-то вакханалия…
Ну и результат:
Заранее предупреждаю: это чисто спортивный интерес, реализовывать quicksort на PHP (да еще и так!) не нужно!
Получилась вообще какая-то вакханалия…
function q($s) {
$l = count($s);
$r = $s;
if ($l != 0) {
$x = $y = $r = array();
$d = $f = 0;
$k = $s[0];
for($i=1; $i < $l; $i++) {
if($s[$i] <= $k) {
$x[] = $s[$i];
$d++;
} else {
$y[] = $s[$i];
$f++;
}
}
$a = q($x);
$b = q($y);
for($i=0;$i<$d;$i++){
$r[] = $a[$i];
}
$r[] = $k;
for($i=0;$i<$f;$i++){
$r[] = $b[$i];
}
}
return $r;
}Ну и результат:
Кстати, хотелось бы выступить в защиту Фортрана!
На той странице — это единственная нерекурсивная реализация алгоритма. Отсюда и сложность!
На той странице — это единственная нерекурсивная реализация алгоритма. Отсюда и сложность!
а в руби сортировка делается не по методу quick? тогда будет выглядеть аналогично хаскелю
не пойму, почему в одних случаях использовали готовые qsort, а в других шаманили сортировку вручную?
не пойму, почему в одних случаях использовали готовые qsort, а в других шаманили сортировку вручную?
Так и знал, что Хаскель всех уделает. %)
Clean тоже был бы на высоте.
Clean тоже был бы на высоте.
интереснее все таки смотреть на что-нибудь типа CFG/DFG, ибо программист читающий программу в первую очередь интересуется именно тем, как идёт управление и текут данные, а не то как часто слово then стоит рядом со словом if
Раньше писями мерялись, теперь красотой графов ;)
интересно было-бы эрланг посмотреть. ))
Scala нумбер уан:
Ну и второй вариант в Haskell-стиле с pattern matching
Можно сделать и нумбер 3 — примерно как Java/C.
def sort(xs: Array[Int]): Array[Int] =
if (xs.length <= 1) xs
else {
val pivot = xs(xs.length / 2)
Array.concat(
sort(xs filter (pivot >)),
xs filter (pivot ==),
sort(xs filter (pivot <)))
}
Ну и второй вариант в Haskell-стиле с pattern matching
def qsort(xs: List[Int]): List[Int] = {
xs match {
case List() => xs
case _ => qsort(for(x <- xs.tail if x < xs.head) yield x) ::: List(xs.head) ::: qsort(for(x <- xs.tail if x >= xs.head) yield x)
}
}
Можно сделать и нумбер 3 — примерно как Java/C.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Программистская графофилия и языки программирования