гинеколог отечественного веб-дизайна (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
Эээ. Тебя не смущает, что ты разную длину имён переменных выбрал?
Свой вариант?
Вот вариант сортировки пузырьком на массиве - все же это для пузырька более естественно, чем на списках:
import Data.Array
import System.Random

bubbleSort :: Ord e => Array Int e -> Array Int e
bubbleSort a = let (o,size) = bounds a
                   swap a n | (a!n) > (a!(n+1)) = a // [(n,a!(n+1)),(n+1,a!n)]
                   swap a n = a
                   pass a n = foldl swap a [ o .. n ]
               in  foldl pass a $ reverse [ o .. size-1 ]

main = do s <- sequence $ take 10 $ repeat $ randomRIO (0::Int,100)
          let a = listArray (0,length(s)-1) s
              a' = bubbleSort a
          sequence $ map (putStrLn.show) (elems a')

Не уверен, насколько это легко читать, но думаю, что для человека, достаточно вывихнувшего себе хаскелем мозг, это читается не хуже императивного варианта.
instance Monoid Bool where
    mempty = True
    mappend = (&&)
bubbleSort xs = let (sorted,end) = runWriter $ bS xs in if end then sorted else bubbleSort sorted
    where bS (x1:xs@(x2:xt)) | x1 > x2 = tell False >> bS (x2:x1:xt)
                             | otherwise = liftM (x1:) $ bS xs
          bS xs = return xs