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たのしく学ぼう 第４章 再帰の練習 その２

第４章の続き。
前の：
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は受け取った２つのリストをタプルのリストとして返します。
その他の仕様として、返すリストの長さは短い方にそろいます。

zip' :: [a] -> [b] -> [(a,b)]
zip' [] _ = []
zip' _ [] = []
zip' (x:xs) (y:ys) = (x, y) : zip' xs ys

２−３行目で、短い方のリストに長さを合わせるようにします。短い方が空になり次第終わり。
４行目で、タプルを作ります。

続く。

すごいH本の勉強始めます。

記録がてら、参考になった場所や練習問題などの自分の解答を載せていきます。
特に例題などは本のコードをなるべく見ずに自分で書いてみてから答え合わせ、という方式にします。

今４章が終わって５章のあたりですが、まだ復習程度のトピックばかりなのでそこまで困ってません。
評判のいい本なので、結構後半読み進めていくのが今から楽しみです。

すごいHaskellたのしく学ぼう 第４章 再帰の練習

すごいH本の４章で再帰の練習のページがあります。
答えをなるべく見ずに自分で実装してみる。

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が０になるまで再帰で呼び続けます。
ちなみにこれの制限をなくしたのが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"

あまりコメントはないかな。
１から始めて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)]

タプルの２番目の要素を条件にして最終的に取り出す１番目の要素をピックアップするという形。

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となります。