基本アルゴリズム

Haskell

プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10

http://blog.livedoor.jp/dankogai/archives/50957658.html

というわけで勉強のために最初の方のを書いてみた。
といってもあまりにも有名すぎて、自分で考えて書いているというよりはどこかで見た記憶をそのまま写しているだけな気も。
このアルゴリズムをリストで実装しても…ってやつも入ってるけど、まあ練習ということで。

import Data.List

-- 1. ユークリッドの互除法(Euclidean algorithm)
gcd' m 0             = m
gcd' m n | m >= n    = gcd' n (m `mod` n)
         | otherwise = gcd' n m

-- 2. エラトステネスの篩(the Sieve of Eratosthenes)
sieve (x:xs) = x : sieve [i|i<-xs,i`mod`x/=0]

-- 3. 二分探索(Binary Search)
member' [] n             = False
member' [x] n            = x == n
member' xs n | n == x    = True
             | n < x     = member' l n
             | otherwise = member' r n
           where (l,x:r) = splitAt (length xs `div` 2) xs

-- 4. ニュートン法(Newton's method)
sqrt' q a | abs (q-a^2) < 0.001 = a
          | otherwise           = sqrt' q $ a-(a^2-q)/(2*a)

-- 5. クイックソート(Quick Sort)
qsort []     = []
qsort (x:xs) = qsort l ++ [x] ++ qsort r
 where (l,r) = partition (<x) xs

-- 6. マージソート(Merge Sort)
merge xs []                     = xs
merge [] ys                     = ys
merge (x:xs) (y:ys) | x < y     = x : merge xs (y:ys)
                    | otherwise = y : merge (x:xs) ys
msort xs | length xs < 2 = xs
         | otherwise     = msort l `merge` msort r
             where (l,r) = splitAt (length xs `div` 2) xs

main = do 
  print $ gcd' 1029 1071
  print $ take 9 $ sieve [2..]
  print $ member' [1,3,5,7,9] 9
  print $ member' [1,3,5,7,9] 8
  print $ sqrt' 3 1
  print $ qsort [5,1,3,4,2]
  print $ msort [5,1,3,4,2]