Haskell H99 Question 12
http://www.haskell.org/haskellwiki/99_questions/11_to_20
問題１２
問題の日本語訳
連長圧縮のリストを復号しなさい。
問題１１で明示された通りに作られた連長圧縮コードが与えられる。その展開した版を作成しなさい。
data ListItem a = Single a | Multiple Int a deriving (Show) decodeModified :: [ListItem a] -> [a] decodeModified [] = [] -- (1) decodeModified ((Single x):xs) = x : decodeModified xs --(2) decodeModified ((Multiple 1 x):xs) = x : decodeModified xs --(3) decodeModified ((Multiple n x):xs) = x : decodeModified ((Multiple (n-1) x):xs) --(4)
まあまあよくできたと思うけどやっぱり模範解答は全然違うことが書いてありました。（後述）
パターンマッチングというやつはここまでできるんですねー、関心。
(1) 空だったら空のリストを返す。終点
(2) もし先頭要素がSingleだったら、先頭に文字をくっつけて後続に対して再帰
(3) もし先頭要素がMultipleで長さが1だったら(2)と同じ処理
(4) もし先頭要素がMultipleで長さが1以外だったら、先頭に文字をくっつけて長さを減らしてもう一回
模範解答
http://www.haskell.org/haskellwiki/99_questions/Solutions/12
concatMapを使っていますね。確かに結構きれい。
concatMapは、こんなのです。
concatMap :: (a -> [b]) -> [a] -> [b] -- Defined in `GHC.List'
aのリストに第一引数の関数を当てるけど、そのままだと[[b],[b],[b]]みたいになっちゃうから中のかっこを外して[b]にするってやつだな。
ちょっと試しに使ってみる。
まず非リストな何かを取ってリストを返す関数を適当に作ってみて、
naturalNumberTill n = naturalNumberTill' 1 n where naturalNumberTill' x n | x > n = [] | otherwise = x : naturalNumberTill' (x+1) n
それを使って実行してみる。
*Main> :t naturalNumberTill naturalNumberTill :: (Num a, Ord a) => a -> [a] *Main> map naturalNumberTill [3,4,5] [[1,2,3],[1,2,3,4],[1,2,3,4,5]] *Main> concatMap naturalNumberTill [3,4,5] [1,2,3,1,2,3,4,1,2,3,4,5]
なるほど。
Haskell H99 Question 32
http://www.haskell.org/haskellwiki/99_questions/31_to_41
Haskellの練習問題H99の32問目。
最大公約数をとのことですが、ユークリッドの互除法を使えとの指示なので、wikipediaで勉強：
アルゴリズム
1. 入力を m, n (m ≧ n) とする。
2. n = 0 なら、 m を出力してアルゴリズムを終了する。
3. m を n で割った余りを新たに n とし、更に 元のnを新たにm とし 2. に戻る。
とりあえず素直にそのまま実装：
myGCD :: Int -> Int -> Int myGCD x y | abs x >= abs y = myGCDin x y | otherwise = myGCDin y x where myGCDin m n | mod m n == 0 = abs n | otherwise = myGCDin m (mod m n)
m >= n でないといけないとのことなので、最初に判定をして、内部の関数に引き渡し、m >= n を前提に残りのアルゴリズムを記述。
何のひねりもありません。
追加で負のケースに対応するため、絶対値での判定に変更（abs）。
模範解答を見てみたら若干違うアルゴリズムを書いていてすっきりしていた。
http://www.haskell.org/haskellwiki/99_questions/Solutions/32
Haskell H99 Question 31
http://www.haskell.org/haskellwiki/99_questions/31_to_41
ある自然数が素数かどうかを求める問題。
まず、素数を求めるロジックを、「初期値が２以上で、初期値までの各自然数で割り切れないこと」、という最も単純なアルゴリズムで解いてみる。
簡単なロジックで
isPrime x |x <= 1 = False |otherwise = calculatePrime 2 where calculatePrime y | x == y = True | mod x y == 0 = False | otherwise = calculatePrime (y+1)
書き方はHaskellっぽいけどなんか冗長なので、次にエラトステネスのふるい風に作ってみる。
ちなみに、
http://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9
エラトステネスのふるい風
calcPrime :: [Int] -> [Int] calcPrime [] = [] calcPrime (x:xs) = x : calcPrime (sift xs) where sift [] = [] sift (y:ys) | mod y x == 0 = sift ys | otherwise = y : (sift ys) prime = calcPrime [2..] isPrime' x = isIncluded prime where isIncluded [] = False isIncluded (y:ys) | x > y = isIncluded ys | x == y = True | otherwise = False
遅くてびっくりした。まあがりがり書いただけだからな。。
でも遅延評価を有効に使えているのでいいかな。
まずcalcPrime関数ではある自然数配列から素数を引っこ抜いてます。
１を与えると変な挙動になりそうだからやめてください。後で直します。
primeは素数の無限配列を返します。
そして、後は単純にisPrime'で調べている自然数が要素より小さくなったら終わり、という感じです。
書き疲れたので模範解答は省略。
Haskell H99 Question 11
http://www.haskell.org/haskellwiki/99_questions/11_to_20
import Data.List data ListItem a = Single a | Multiple Int a deriving (Show) --自分で作った解答 encodeModified :: Eq a => [a] -> [ListItem a] encodeModified xs = map (listToAmount) (group xs) where listToAmount :: Eq a => [a] -> (ListItem a) listToAmount (x:xs) | length (x:xs) > 1 = Multiple (length (x:xs)) x | otherwise = Single x --模範解答 --Question 9 からの引用 encode xs = map (\x -> (length x,head x)) (group xs) encodeModified' :: Eq a => [a] -> [ListItem a] encodeModified' = map encodeHelper . encode where encodeHelper (1,x) = Single x encodeHelper (n,x) = Multiple n x
頑張ってみたのですが、どうしてもdata型を作ることができなかったので答え見ました。。
データ型とか、インスタンスとか型クラスとか、あんまり理解できていないようなので、どこかで勉強しないと。
データ型の宣言
data ListItem a = Single a | Multiple Int a deriving (Show)
ListItemの宣言です。見たらこういうもんかと思いますが、こういう形に自分で作ることはできませんでした。
ListItem aはSingle aかMultiple Int aという形をとるという単純なものですが、型変数に任意の型クラスを適用とすると構文エラーになってしまって断念。
そういうことはできないのかしら。。
derivingとは派生などという意味らしいです。構文については、そのうちしっかり勉強して書きます。
自分で作った解答
encodeModified :: Eq a => [a] -> [ListItem a] encodeModified xs = map (listToAmount) (group xs) where listToAmount :: Eq a => [a] -> (ListItem a) listToAmount (x:xs) | length (x:xs) > 1 = Multiple (length (x:xs)) x | otherwise = Single x
第９問のやり方を参考にして、mapとgroupを使いました。
map用にリストを引数にListItemを返す関数を作り、その中で条件によってSingleかMultipleを返すようにしました。
まあまあいいじゃんと思いましたが、模範解答では関数合成を使用していました。そっちのほうがエレガントに見えますね。
模範解答
--Question 9 からの引用 encode xs = map (\x -> (length x,head x)) (group xs) encodeModified' :: Eq a => [a] -> [ListItem a] encodeModified' = map encodeHelper . encode where encodeHelper (1,x) = Single x encodeHelper (n,x) = Multiple n x
以下のように関数が定義されています。
encode :: Eq t => [t] -> [(Int, t)] map encodeHelper :: [(Int, a)] -> [ListItem a] （ちなみに、encodeHelper :: (Int, a) -> ListItem a）
これにより、encode の戻り値をそのままmap encodeHelperにつなげることができますね。
Haskellの練習問題に使っているサイト
Haskellをやったりやらなかったりしてしばらくたちますが、本格的に勉強を始めようと思ってこのサイトの練習問題を始めました。
http://www.haskell.org/haskellwiki/H-99:_Ninety-Nine_Haskell_Problems
とりあえず自分で考えてみてわからなかったらすぐ写経する、というスタイルでやってます。
自分で作った解答や模範解答で難しそうなところを解読するためのメモとしてブログを使いたいと思います。
Haskell H99 Question 10
http://www.haskell.org/haskellwiki/99_questions/1_to_10
10問目
9問目をまねて自分で作ってみた。
encode :: (Eq a, Num b) => [a] -> [(b, a)] encode [] = [] encode (x:xs) = (number, x) : encode rest where getSeqNum (x:[]) = (1, []) getSeqNum (x:y:xs) | x==y = let (n,r) = getSeqNum (y:xs) in (1+n, r) | otherwise = (1, y:xs) (number, rest) = getSeqNum (x:xs)
基本的な考え方は同じで、大きい再帰で一つの文字列の続くブロックを、小さい再帰でここの文字の評価を行い大きい再帰に返す、という形。
模範解答（ずいぶん簡単な書き方があるようです。。）
import Data.List encode' xs = map (\x -> (length x,head x)) (group xs)
mapは(a->b) -> [a] -> [b]なので、"a型を取ってb型を返す関数"と、"a型のリスト"を取って、"b型のリスト"を返します。
簡単に想像できる通り、内部では、引数のリストの要素一つ一つに引数の関数を当てた結果をリストとして返します。
ここではmapに、xを取ってxの長さとxの頭文字のtupleを返す関数が入っているので、たとえば、"aaa"にこの関数を使うと、こうなります。
Prelude> (\x -> (length x, head x) )("aaa")
(3,'a')
そしてmapの第２引数に使われているgroupは、どうも問題９とまったく同じ動きをするようですね。
※groupはData.Listにいるようなのでimportします。
Prelude> :m Data.List Prelude Data.List> group "aaasssdddfff" ["aaa","sss","ddd","fff"]
合わせると、あらかじめ同じ文字に分割しておいた"文字列のリスト"に上述の関数をあてることによって正解が得られるようになっています。
H99の9問目の回答解説
http://www.haskell.org/haskellwiki/99_questions/Solutions
の9問目。
答え丸写しですが、こういう書き方かっこいいですよね。
まさにHaskell書いてるって感じします。
pack :: (Eq a) => [a] -> [[a]] pack [] = [] pack (x:xs) = (x:first) : pack rest where getReps [] = ([], []) getReps (y:ys) | y==x = let (f,r) = getReps ys in (y:f,r) | otherwise = ([], (y:ys)) (first, rest) = getReps xs
内部で2つ再帰が起こっています。
一つは3行目の部分で、restに対してpackを当てているところ
2つ目はgetReps関数の中でです。
例：[1,1,2]として、ステップ実行をしていってみます。
1. pack (x:xs) = (x:first) : pack rest x:xsは、1と[1,2]に分かれます。 2. firstとrestについて、getRepsにxsを当てた結果なので、 (first, rest) = getReps [1,2] = getReps (1:[2]) = (y==x)なので (f, r) = getReps [2] in (1:f, r) = (otherwise)なので (f, r) = ([], 2:[]) in (1:f, r) = 1:[], 2:[] 3. firstとrestが取れたので、１の右辺に戻す pack (x:xs) = (1:1:[]) : pack 2:[] = (読みやすく） [1,1]: (pack [2]) 4. pack [2]を解く (first, rest) = getReps [] = ([], []) pack 2:[] = (2:first) : pack rest = (2:[]) : pack [] = (2:[]):[] 5. 全部合わせると pack [1,1,2] = [1,1]:[2]:[] = [[1,1],[2]]
できた！すごい！
