Haskell и циклы

tail recursion

В классическом ФП циклов не бывает

>а в принципе в этом языке такое понятие как циклы

я от хаскеля очень далёк, но он мне очень напоминает теорию алгоритмов: класс обсчитываемых функсий совпадает с классом рекурсивных функций /тезис Чарча/... страшно ломает стадартное мышление тот факт, что 48+52 на самом деле мона посчитать рекурсивно... т.е. мы не задумываемся о том, что и сами считаем рекурсивно :)

Ломает - не то слово! Читал, что многие функциональные языки позволяют многие вольности (а вдруг и Haskell?)

Нашел пример быстрой сортировки Хоара на haskell:

quickSort ([]) = []

quickSort ([h : t]) = quickSort (n | n t, n <= h) + [h] + quickSort (n | n t, n > h)

Сравнивая с С более-менее с циклами разобрался, но как мышление наизнанку выворачивает!

> .. страшно ломает стадартное мышление ..

нет, наоборот воспитывает мышление большее поддающееся движению, ломает так называемое статическое мышление

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

Вообще да - любой цикл есть притянутая за уши рекурсия.

> Сравнивая с С более-менее с циклами разобрался, но как мышление наизнанку выворачивает!

QuickSort и определяется рекурсивно. Так что, рекурсия для неё - самое то. А вот реализация циклами - исключительно технические издержки и при попытке понять по этим реализациям алгоритм, действительно выворачиват.

>Сравнивая с С более-менее с циклами разобрался, но как мышление наизнанку выворачивает!

Приведи-ка мне пожалуйста итеративный вариант сортировки Хора :) На том же С во всех книгах приводится именно рекурсивный вариант, так что не надо. и ваще: to iterate is human, to recur - divine.

>А вот реализация циклами - исключительно технические издержки и при попытке понять по этим реализациям алгоритм, действительно выворачиват.

а вот обход графа - рекурсивная задача /fix me!!!/. чё-то мне не представляется её решение циклом! т.е. не любую рекурсию мона дотянуть до цикла.

и снова поправте если забрёл не в ту сторону :)

void quickSort (int a[], int l, int r)
{
int i = l;
int j = r;
int x = a[(l + r) / 2];
do
{
while (a[i] < x) i++;
while (x < a[j]) j--;
if (i <= j)
{
int temp = a[i];
a[i++] = a[j];
a[j--] = temp;
}
}
while (i <= j);
if (l < j) quickSort (a, l, j);
if (i < r) quickSort (a, i, r);
}


Рекурсивный, но с циклами. А кто говорил про итеративный?

> чё-то мне не представляется её решение циклом!

Можно искусственно: сгородить собственный цикл. :) Но это из разряда brain fuck. :)

>Но это из разряда brain fuck. :)

это ты про это:

http://www.muppetlabs.com/~breadbox/bf/

?:)

>как их реализовать стандартными средствами языка

Вот хотя бы так:

for :: (foreach a. a,a -> Boolean,a->a) -> (a->IO()) -> IO () 
for (start,cond,inc) code 
  | cond start = code start >> for (inc start,cond,inc) code 
  | otherwise = return ()

И потом:

for (0, \i -> i < 10 , \i -> i+1 ) print

А циклы типа (for i in list) (типа питонских) можно через sequence.

Исправление. "foreach a." должно быть до скобок, и скорее всего вообще не нужно.

> это ты про это:

Не совсем. В общем-то я описАлся :s/собственный цикл/собственный стек/

Brain fuck именно в дословном переводе на русский, который модеры не пропустят :)