Haskell Code Fragment

About this

へんてこコード集。ある意味Haskellの一番面白いところかも知れず…

クイックソート

短い。とにかく短い。短いけどしっかりクイックソートしてる。 でも、計算量の係数が大きそうな予感。 (2004/8/13 追：どひゃー、コード間違えてた…こっそり修正)

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

各種ソート

クイックソートばかり有名なソートin Haskell。 他のソートはどうなのよ?

バブルソート

イマイチ。

bubbleSort [] = []
bubbleSort ls = head $ drop (length ls) $ iterate f ls where
  f [x] = [x]
  f (x:y:ys) | x <= y    = x:f (y:ys)
             | otherwise = y:f (x:ys)

挿入ソート

バブルソートよりはマシっぽい。 insertがData.Listにあるから短い短い。

insSort = foldr insert []

選択ソート

まずまず。というかまぁ、元のアルゴリズムが単純なんだけど。

selectSort = unfoldr f where
  f [] = Nothing
  f ls = let m = minimum ls in Just (m,delete m ls)

ヒープソート

うーん…苦しい。苦しいぞ。 葉っぱから突っ込むことが出来ないから、 根っこから場所を指定して突っ込む。 根っこから一個づつ引っ張るのもちょっとだけ工夫。 ヒープの配列上作成は…Haskellらしくないからいいや。

data BTree a = Node a (BTree a) (BTree a) | Leaf

heapSort ls = heapToList $ foldl insHeap Leaf $ zip [1..] ls

insHeap hp (pos,n) = inner n posl hp where
  inner n [] Leaf = Node n Leaf Leaf
  inner n (0:ps) (Node a l r)
    | n < a     = Node n (inner a ps l) r
    | otherwise = Node a (inner n ps l) r
  inner n (1:ps) (Node a l r)
    | n < a     = Node n l (inner a ps r)
    | otherwise = Node a l (inner n ps r)

  posl = tail $ reverse $ map (`mod`2) $ takeWhile (/=0) $ iterate (`div`2) pos

heapToList Leaf = []
heapToList (Node a l r) = a:heapToList (inner l r) where
  inner Leaf Leaf = Leaf
  inner l Leaf = l
  inner Leaf r = r
  inner l@(Node a la ra) r@(Node b lb rb)
    | a < b     = Node a (inner la ra) r
    | otherwise = Node b l (inner lb rb)

マージソート

まぁまぁ。(でもないか…ちょっと長い)

mergeSort = f . map (\x -> [x]) where
  f [x] = x
  f ls = f $ map merge $ slice 2 ls

  merge [x] = x
  merge [x,y] = m x y where
    m [] y = y
    m x [] = x
    m xl@(x:xs) yl@(y:ys)
      | x <= y    = x:m xs yl
      | otherwise = y:m xl ys

  slice n = map (take n) . takeWhile (not.null) . iterate (drop n)

フィボナッチ数列

遅延評価パワー炸裂。Haskell勉強してかなり驚いたコード。 しかも計算量はO(n)。

fib = 1:1:zipWith (+) fib (tail fib)

素数(エラトステネスのふるい)

これも驚いたコード。 簡潔なのにちゃんとふるいしてる。 しかも、最初にふるいのサイズを決めなくて良いので、 他の言語での実装よりも本質的に優れていると思う。

primes = sieve [2..]
sieve (x:xs) = x:sieve [a | a<-xs, a `mod` x /= 0]

数当てゲーム

コード片ちがうやん。

main = do ans <- randomRIO (1,100)
          interact $ unlines.game ans.map read.words

game :: Int -> [Int] -> [String]
game ans ls = "Please Input Number. (1-100)":gen ls where
  gen (x:xs) | x == ans = ["Collect Answer!"]
             | x  > ans = "Answer is smaller.":gen xs
             | x  < ans = "Answer is bigger." :gen xs