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

Haskell 99問 (11-20)

Haskell 99問 (11-20)

http://www.haskell.org/haskellwiki/99_questions/11_to_20 より。

問題11 問題10と同じように重複した要素を持つリストから、重複数と代表要素のタプルの一次元のリストにするが、その際に要素が1のものはタプルにせず単体でリストに入れる関数を作れ。(Haskell のリストは要素の型が同じでないといけないので、ユーザ定義の型を定義する必要がある。)

文章で表現しにくいので、Lispによる実行例
* (encode-modified '(a a a a b c c a a d e e e e))
((4 A) B (2 C) (2 A) D (4 E))

Haskell による実行例
P11> encodeModified "aaaabccaadeeee"
[Multiple 4 'a',Single 'b',Multiple 2 'c',Multiple 2 'a',Single 'd',Multiple 4 'e']

解答
import List

data ListItem a = Single a | Multiple Int a
    deriving (Show)

encodeModified :: (Eq a) => [a] -> [ListItem a]
encodeModified = map encodeHelper . encode
    where
        encodeHelper (1,x) = Single x
        encodeHelper (n,x) = Multiple n x

encode :: (Eq a) => [a] -> [(Int, a)]
encode xs = [(length x, head x) | x <- group xs]

問題12 問題11でエンコードしたリストから元のリストへデコードする関数を作れ。

実行例
P12> decodeModified [Multiple 4 'a',Single 'b',Multiple 2 'c',Multiple 2 'a',Single 'd',Multiple 4 'e']
"aaaabccaadeeee"

解答
data ListItems a = Single a | Multiple Int a

decodeModified :: [ListItems a] -> [a]
decodeModified = concatMap decodeHelper
    where
        decodeHelper (Single x) = [x]
        decodeHelper (Multiple n a) = replicate n a

問題13 (意訳し辛かったので直訳)問題11で作った Run-length エンコードを直接に作る関数を作れ。Run-length エンコード法を直接に適用する、つまり、問題9でやったような要素のカウントと要素のタプルを中間的に作成するのではなく、単に数えるだけにする。問題11でやったように、(1, X) のような singleton list は要素のみの X に置き換えて、結果のリストを単純化する。(直接にという意味は解答を見るかぎり List モジュールの関数 group を使わないでという意味らしい。)

実行例
P13> encodeDirect "aaaabccaadeeee"
[Multiple 4 'a',Single 'b',Multiple 2 'c',Multiple 2 'a',Single 'd',Multiple 4 'e']

解答
data ListItem a = Single a | Multiple Int a
    deriving (Show)

encode' :: Eq a => [a] -> [(Int,a)]
encode' = foldr helper []
    where
      helper x [] = [(1,x)]
      helper x (y:ys)
        | x == snd y   = (1+fst y,x):ys
        | otherwise    = (1,x):y:ys

encodeDirect :: Eq a => [a] -> [ListItem a]
encodeDirect = map encodeHelper . encode'
    where
      encodeHelper (1,x) = Single x
      encodeHelper (n,x) = Multiple n x

問題14 リストの要素をそれぞれふたつずつに増やす関数を作成せよ。

実行例
> dupli [1, 2, 3]
[1,1,2,2,3,3]

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

問題15 リストのそれぞれの要素の個数を n 倍にする関数を作成せよ。

実行例
> repli "abc" 3
"aaabbbccc"

解答
repli :: [a] -> Int -> [a]
repli xs n = concatMap (replicate n) xs

問題16 リストのN番めごとの要素を削除する関数を作成せよ。

実行例
Main> dropEvery "abcdefghik" 3
"abdeghk"

解答
dropEvery :: [a] -> Int -> [a]
dropEvery list count = helper list count count
where helper [] _ _ = []
helper (x:xs) count 1 = helper xs count count
helper (x:xs) count n = x : (helper xs count (n - 1))

問題17 リストを n 番めの要素の前後に分割する関数を作成せよ。

実行例
Main> split "abcdefghik" 3
("abc", "defghik")

解答
split :: [a] -> Int -> ([a],[a])
split xs n = (take n xs, drop n xs)

問題18 リストの m 番めの要素から n 番めの要素までの部分リストを取り出す関数を作成せよ。

実行例
Main> slice ['a','b','c','d','e','f','g','h','i','k'] 3 7
"cdefg"

解答
slice xs (i+1) k = take (k-i) $ drop i xs

問題19 リストを n 個の要素分左にローテートする関数を作れ。(負数の場合は右にローテートさせる。)

実行例
*Main> rotate ['a','b','c','d','e','f','g','h'] 3
"defghabc"

*Main> rotate ['a','b','c','d','e','f','g','h'] (-2)
"ghabcdef"

解答
rotate :: [a] -> Int -> [a]
rotate [] _ = []
rotate l 0 = l
rotate (x:xs) (n+1) = rotate (xs ++ [x]) n
rotate l n = rotate l (length l + n)

問題20 リストの n 番めの要素を削除する関数を作れ。

実行例
*Main> removeAt 1 "abcd"
('b',"acd")

解答
removeAt :: [a] -> Int -> (a,[a])
removeAt xs k = case back of
        [] -> error "removeAt: index too large"
        x:rest -> (x, front ++ rest)
  where (front, back) = splitAt k xs
by tnomura9 | 2009-08-13 07:40 | Haskell | Comments(0)
<< Haskell 99問 (21... Haskell 99問 (1-10) >>