Haskell H99 Question 17
H99のQuestion 17
http://www.haskell.org/haskellwiki/99_questions/11_to_20
全然わからなかったので答え見ました。
模範解答
http://www.haskell.org/haskellwiki/99_questions/Solutions/17
split :: [a] -> Int -> ([a], [a]) split [] _ = ([], []) split l@(x : xs) n | n > 0 = (x : ys, zs) | otherwise = ([], l) where (ys,zs) = split xs (n - 1)
例によって実際にやってみます。
split “abcde” 3
とすると、
1. split “abcde” 3 ==> n > 0 なので、 ( ‘a’ : ys, zs) where (ys, zs) = split “bcde” 2 2. split “bcde” 2 ==> n > 0 なので、 ( ‘b’ : ys, zs) where (ys, zs) = split “cde” 1 3. split “cde” 1 ==> n > 0 なので、 ( ‘c’ : ys, zs) where (ys, zs) = split “de” 0 4. split “de” 0 ==> otherwiseなので、 ([], “de”) 5. 3に戻って ( ‘c’ : ys, zs) where (ys, zs) = ([], “de”) ==> ( ‘c’ : [], “de”) 6. 2 に戻って ( ‘b’ : ys, zs) where (ys, zs) = ( “c”, “de”) ==> ( ‘b’ : “c” , “de”) 7. 1に戻って ( ‘a’ : ys, zs) where (ys, zs) = ( “bc”, “de”) ==> ( ‘a’ : “bc”, “de”) ==> ( “abc”, “de”)
うん、できてる。
whereとか、let…inとか使うと展開がわからなくなってしまいますね。。難しいです。
すごいHaskellたのしく学ぼう 第4章 再帰の練習 その2
第4章の続き。
前の:
http://ugnom.hatenablog.com/entry/2013/12/30/131136
再帰の練習です。
take
ある配列の最初の第一引数の数だけ取り出す。ついでに、最後から指定数だけ取るのも作ってみました。
take' :: Int -> [a] -> [a] take' n (x:xs) | n <= 0 = [] | otherwise = x : take' (n-1) xs takeLast :: Int -> [a] -> [a] takeLast _ [] = [] takeLast n l@(x:xs) | n >= length l = x : takeLast n xs | otherwise = takeLast n xs
takeLastのほうは別にlentghを使わなくてもできたのではないかと思うのですが、ちょっと思いつきませんでした。。
特に解説はいらないと思います。単純なパターンマッチングと場合分けです。
reverse
リストを受け取って反転させたリストを返す。
reverse' :: [a] -> [a] reverse' [] = [] reverse' (x:xs) = reverse' xs ++ [x]
(++)は文字列を連結させる関数。
Prelude> :i ++ (++) :: [a] -> [a] -> [a] -- Defined in `GHC.Base' Prelude> "asd" ++ "123" "asd123"
zip
zipは受け取った2つのリストをタプルのリストとして返します。その他の仕様として、返すリストの長さは短い方にそろいます。
zip' :: [a] -> [b] -> [(a,b)] zip' [] _ = [] zip' _ [] = [] zip' (x:xs) (y:ys) = (x, y) : zip' xs ys
2−3行目で、短い方のリストに長さを合わせるようにします。短い方が空になり次第終わり。
4行目で、タプルを作ります。
続く。
すごいH本の勉強始めます。
記録がてら、参考になった場所や練習問題などの自分の解答を載せていきます。
特に例題などは本のコードをなるべく見ずに自分で書いてみてから答え合わせ、という方式にします。
今4章が終わって5章のあたりですが、まだ復習程度のトピックばかりなのでそこまで困ってません。
評判のいい本なので、結構後半読み進めていくのが今から楽しみです。
すごいHaskellたのしく学ぼう 第4章 再帰の練習
すごいH本の4章で再帰の練習のページがあります。
答えをなるべく見ずに自分で実装してみる。
maximum関数の実装
maximum' :: (Ord a) => [a] -> a maximum' [] = error "empty list" maximum' [x] = x maximum' (x:xs) = max x (maximum' xs)
空リストの挙動の記載を忘れていたので、後から追加。(無いとパターンマッチングできませんというエラーがでます。)
max関数は(Ord a) => a -> a -> aなので、リストの形にするために再帰を使って最後から値を繰り上げていきます。
[3, 5, 2]の場合、以下の通りに順次計算できます。
maximum’ (3:[5,2]) ==> max 3 (maximum’ [5,2]) ==> max 3 (maximum' (5:[2])) ==> max 3 (max 5 (maximum [2])) ==> max 3 (max 5 2) ==> max 3 5 ==> 5
replicate関数の実装
replicate' :: Int -> a -> [a] replicate' n x | n <= 0 = [] | otherwise = x : replicate' (n-1) x
単純な形。
replicate’関数をnが0になるまで再帰で呼び続けます。
ちなみにこれの制限をなくしたのがrepeat関数の実装ですね。
repeat' :: a -> [a] repeat' a = a : repeat' a
遅延評価のおかげで表示に必要な計算のみを順次行うので、固まらずに延々と値を吐き出し続けます。
*Main> repeat' 'a' “aaaaaaaaaaaaaaaaaaa.....aa^CaaaaaaaaaaaaaInterrupted.
Haskell H99 Question 16
http://www.haskell.org/haskellwiki/99_questions/11_to_20
Haskell H99 Question 16
日本語訳
リストのN番目の要素を取り除きなさい。 Example in Haskell: *Main> dropEvery "abcdefghik" 3 "abdeghk"
あまりコメントはないかな。
1から始めてnまでいったら飛ばしてもう一回はじめから。
dropEvery :: [x] -> Int -> [x] dropEvery xs n = dropHelper xs n 1 where dropHelper [] _ _ = [] dropHelper (x:xs) n m | n == m = dropHelper xs n 1 | otherwise = x : dropHelper xs n (m+1)
模範解答
http://www.haskell.org/haskellwiki/99_questions/Solutions/16
面白かった模範解答。
dropEvery' :: [x] -> Int -> [x] dropEvery' xs n = [ i | (i, k) <- (zip xs [1,2..]), (mod k n) /= 0 ]
この解答かっこいいっすねー。
zip関数は、二つのリストを引数にして、その二つをあわせたタプルのリストを返すというもの。
Prelude> :t zip zip :: [a] -> [b] -> [(a, b)] Prelude> zip "abcd" [1,2,3,4] [('a',1),('b',2),('c',3),('d',4)]
タプルの2番目の要素を条件にして最終的に取り出す1番目の要素をピックアップするという形。
Haskell H99 Question 15
http://www.haskell.org/haskellwiki/99_questions/11_to_20
Problem 15
日本語訳
与えられた数字の回数だけリストの各要素を複製しなさい。
> repli "abc" 3
"aaabbbccc"
repli :: [a] -> Int -> [a] repli xs y = concatMap (\x -> replicate y x) xs repli' xs y = xs >>= (\x -> replicate y x)
replicateを使ってdupliと同じことをしました。
ついでにListモナドの練習も、dupliで作成したものと同じ形で練習として作成。
模範解答
http://www.haskell.org/haskellwiki/99_questions/Solutions/15
repli :: [a] -> Int -> [a] repli xs n = concatMap (take n . repeat) xs
repeat関数とtake関数を使っています。
repeatは、引数で取ったaの無限リストを作るようですね。すごい関数だな。
こんな関数をサポートできるのは遅延評価がしっかりサポートされているHaskellだけなんでしょうね。
*Main> :t repeat repeat :: a -> [a]
takeは、自然数nとリストを引数にして、リストの最初のn要素だけだけを取り出したリストを返します。
これを合成するとあるaの無限配列からn分だけを取り出したリストを取得できます。
*Main> :t \n -> take n . repeat \x -> take n . repeat :: Int -> a -> [a] *Main> (\n -> take n . repeat) 3 'a' "aaa"
Haskell H99 Question 14
http://www.haskell.org/haskellwiki/99_questions/11_to_20
H99 Question 14
日本語訳
リストの要素を重複させなさい。
> dupli [1, 2, 3]
[1,1,2,2,3,3]
これは簡単ですね。
dupli :: [a] -> [a] dupli = concatMap (\x -> ([x,x])) dupli' [] = [] dupli' (x:xs) = x:x:(dupli xs)
模範解答もこんな感じでした。
concatMap便利。Question 12で書いたとおり、中のリスト同士を連結させて、中の要素を外のリストの要素にしてしまうという形。
concatMapを使わないバージョンも作ってみました。すべての要素に対して二個同じものを戻りのリストに入れます。
模範解答
http://www.haskell.org/haskellwiki/99_questions/Solutions/12
面白いのはListモナドを使っているものでしょうか。
dupli xs = xs >>= (\x -> [x,x])
ラムダ式のところは、a -> m a (但し mは[])で、それをすべての引数の要素にapplyするという感じ。基本的な挙動はconcatMapと同じなんですね。
戻りは当然[] aとなります。