Haskell その３

おきまりのQuick Sortの例。

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

動かしてみる。

import System

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

main = do
  args <- getArgs
  mapM_ (\a -> putStr (a ++ " ")) (quicksort args)

$ /cygdrive/c/ghc/ghc-6.4.1/bin/ghc qsort.hs
$ ./main.exe 5 4 3 7 9 1 6 0 2 8
0 1 2 3 4 5 6 7 8 9

気になるのは、

[y | y <- xs, y<x]

というところ。
リストの内包表記ですね。
念のため、こんなのを動かしてみる。

import System

lowList (x:xs) =  [y | y <- xs, y<x]
hiList (x:xs)  =  [y | y <- xs, y>=x]

main = do
  args <- getArgs
  mapM_ (\a -> putStr (a ++ " ")) (lowList args)
  putStr "\n"
  mapM_ (\a -> putStr (a ++ " ")) (hiList args)

$  ./main.exe 5 4 3 7 9 1 6 0 2 8
4 3 1 0 2
7 9 6 8

http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/quick-sort.html
こういうの見ると、swapという不純な"How"を必要とするアルゴリズムを教えるより、
先にこのHaskillの例を教えたほうが良い気もしてくる。