гинеколог отечественного веб-дизайна (ao_mmm) wrote,
гинеколог отечественного веб-дизайна
ao_mmm

Опять об сортировку...

Преимущество программирования на языке Haskell по сравнению с императивными языками принято иллюстрировать примерами кода реализации алгоритма быстрой сортировки. Дескать, вот вам программа на Хаскеле:

qsort [] = []  
qsort (x:xs) = qsort [y | y <- xs, y < x ] ++ [x] ++ qsort [y | y <- xs, y >= x]


А вот, дескать, то же самое на C:

void qsort(int *ds, int *de, int *ss){
    int vl = *ds, *now = ds + 1, *inl = ss, *ing = ss + (de - ds);
    if(de <= ds + 1) return;
    for(; now != de; ++now){
        if(*now <= vl) *inl++ = *now;
        else *ing-- = *now;
    }
    *++inl = vl;
    qsort(ds, ds + (inl - ss), ss);
    qsort(ds + (inl - ss), de, inl + 1);
}


«Видите! Все видите? Насколько на хаскеле меньше кода? Насколько он понятней?» — говорят те, кто приводят эти примеры. И они правы, но не до конца. Во-первых, быструю сортировку «по-хаскеловски» можно написать и на императивном языке. Во-вторых, давайте возьмём не быструю сортировку, а какую-нибудь медленную. Например, пузырьковую.

//Пузырьковая сортировка на PHP
function bubbleSort(array $list) {

    do {

        $isChanged = false;

        for ($i = 0, $size = count($list); $i < ($size - 1); $i++) {

            if ($list[$i] > $list[$i + 1]) {

                $temp = $list[$i + 1];
                $list[$i + 1] = $list[$i];
                $list[$i] = $temp;

                $isChanged = true;
            }
        }

    } while (!$isChanged);

    return $list;
}


А теперь функциональщина:

--- Пузырьковая сортировка на Haskellе
    bubblesort list = bs list [] False 
        where bs []      list' needRepeat = if needRepeat then bubblesort list' else list'                                                                                                                                                                  
              bs [x]     list' needRepeat = bs [] (list' ++ [x]) needRepeat                              
              bs (x1:xs) list' needRepeat = 
                  if x1 > x2 then bs ([x1] ++ tail xs) (list' ++ [x2]) True
                             else bs (xs)              (list' ++ [x1]) needRepeat
                  where x2 = head xs


Как видно, ни по количеству кода, ни по понятности, в этом случае выигрыша нет.
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 4 comments