人気ブログランキング | 話題のタグを見る

Haskell 99問 (1-10)

Haskell 99問より、1ー10問。Haskell のプログラミングがアルゴリズムそのものを記述するという雰囲気がわかる。したがって、プログラミングがどこかパズル風になるのが面白い。

http://www.haskell.org/haskellwiki/99_questions/1_to_10 から引用。

第1問 リストの最後の要素を取得する関数を作れ。

解答
mylast :: [a] -> a
mylast [x] = x
mylast (x:xs) = mylast xs

第2問 リストの最後から2番目の要素を取得する関数を作れ。

解答
last1 :: [a] -> a
last1 [x,_] = x
last1 (x:xs) = last1 xs

第3問 リストの n 番目の要素を取得する関数を作れ。

解答
elementAt :: [a] -> Int -> a
elementAt (x:_) 0 = x
elementAt (_:xs) n = elementAt xs (n-1)

第4問 リストの要素数を取得する関数を作れ。

解答
myLength :: [a] -> Int
myLength [] = 0
myLength (x:xs) = 1 + myLength xs

第5問 リストの要素を逆順にしたリストを作る関数を作れ。

解答
myReverse :: [a] -> [a]
myReverse = foldl (flip (:)) []

第6問 リストが回文(例:たけやぶやけた)であるかどうかを判別する関数を作れ。

解答
isPalindrome :: (Eq a) => [a] -> Bool
isPalindrome xs = xs == reverse xs

第7問 階層構造のリストを一次元リストに変換する関数を作れ。ただし、Haskell ではリストの要素は同じ型でなければならないので、['a',['b','c']] のようなリストは型エラーとなる。階層構造のリストの型を定義する必要がある。

実行例
*Main> flatten (Elem 5)
[5]
*Main> flatten (List [Elem 1, List [Elem 2, List [Elem 3, Elem 4], Elem 5]])
[1,2,3,4,5]
*Main> flatten (List [])
[]

解答
data NestedList a = Elem a | List [NestedList a]

flatten :: NestedList a -> [a]
flatten (Elem x) = [x]
flatten (List x) = concatMap flatten x

第8問 リストから重複した要素を取り除く関数を作れ。

実行例
*Main> compress ['a','a','a','a','b','c','c','a','a','d','e','e','e','e']
['a','b','c','a','d','e']

解答
import Data.List
compress :: (Eq a) => [a] -> [a]
compress = map head . group

第9問 リストの重複した要素をサブリストにまとめる関数を作れ。

実行例
*Main> pack ['a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', 'a', 'd', 'e', 'e', 'e', 'e']
["aaaa","b","cc","aa","d","eeee"]

解答
pack :: (Eq a) => [a] -> [[a]]
pack (x:xs) = let (first, rest) = span (==x) xs
                in (x:first) : pack rest
pack [] = []

第10問 リストの重複した要素を調べ、(重複数、代表要素)のタプルを要素とする関数を作れ。

実行例
encode "aaaabccaadeeee"
[(4,'a'),(1,'b'),(2,'c'),(2,'a'),(1,'d'),(4,'e')]

解答
import Data.List
encode :: (Eq a) => [a] -> [(Int,a)]
encode xs = map (\x -> (length x, head x)) (group xs)
by tnomura9 | 2009-08-13 00:04 | Haskell | Comments(0)
<< Haskell 99問 (11... クイックソート >>