新年おめでとうございます。本年もボチボチとよろしくおつきあいいただける僕としてもうれしいです。

6.8 (1) 負でない整数に対する累乗演算子を定義せよ。またその定義で2^3を簡約せよ

(#) :: Int -> Int -> Int
m # 0 = 1
m # (n + 1) = m * (m # n)

(Prelude.^)とバッティングするので(#)にしてます。

 2#3
 = 2*(2#2)
 = 2*2*(2#1) 
 = 2*2*2*(2#0) 
 = 2*2*2*1
 = 8

ところで、僕の解答ですが括弧がないです。一見したときは正しいと思ったのですがこの間違いは大きい気がします。結果の8は同じですが、問題の意図からすれば零点といってもいいくらい。

2^3
2∗(2^2)
2∗(2∗(2^1))
2∗(2∗(2∗(2^0)))
2∗(2∗(2∗1))
8

6.8 (2) length[1,2,3]、drop 3 [1,2,3,4,5]、init [1,2,3]を簡約せよ

  length [1,2,3]
= 1+(length [2,3])
= 1+(1+(length [3]))
= 1+(1+(1+(length[])
= 1+(1+(1+0))
= 3

  drop 3 [1,2,3,4,5]
= drop 2 [2,3,4,5]
= drop 1 [3,4,5] 
= drop 0 [4,5] 
= [4,5]

  init [1,2,3]
= 1:init [2,3]
= 1:2:init [3]
= 1:2:[]
= [1,2]

6.8 (3) 標準ライブラリの定義を見ないで次ぎのライブラリ関数を再帰を使って定義せよ

3.1 リストのすべてがTrueであるか検査するand::[Boot] -> Bool

and'::[Bool] -> Bool
and' [] = True
and' (x:xs) = if x == True then and' xs else False

空のリストの時はTrue,Falseっていうのは悩みましたがまあ「決め」の問題なので標準と同じTrueにしました。解答は

and (b:bs) = b && and bs

まあ、こういう書き方のほうが簡潔だし"らしい"のでしょうね。こういうのスッと出てくるようになりたいものです。

3.2 リストのリストをとり要素であるリストを連結するconcat::[[a]] -> [a]

concat'::[[a]] -> [a]
concat' (xs:[]) = xs ++ []
concat' (xs:xss) = xs ++ concat' xss

これも中途半端。"concat' (xs:[])"があるなら、"concat' ([]:xs)"も書かなきゃ。xsが[]なら書かなくとも良いと思ったのですが...
解答はもっとシンプル。

concat [] = []

3.3 指定された要素をn個もつリストを生成するreplicate::Int -> a -> [a]

replicate' :: Int -> a -> [a]
replicate' 0 _ = []
-- replicate' n a = a : replicate' (n-1) a
replicate' (n+1) a = a : replicate' n a

n + kのパターンがスッっとでてこない。どうしてもreplicate' n a= replicate' (n - 1) aとなってしまいがちです。五章の訳注(3)によれば使用不可になる可能性があるみたいですが、その場合どうするのでしょうか？

3.4 空でないリストのn番目の要素を取り出す(!!)::[a] -> a

(##)::[a] -> Int -> a
(x:_) ##   0  = x
(x:xs)##(n+1) = xs ## n

3.5 リストの要素に含まれるか検査するelem::Eq a => a -> [a] -> Bool

elem'::Eq a => a -> [a] -> Bool
elem' e [] = False
elem' e (e':es) = if e == e' then True else elem' e es

化石プログラマの僕はどうしてもifを使いたくなります。これからはなるべくifを使わないで考えるようにしないと。解答は

elem x (y : ys) | x == y
                | otherwise = elem x ys

6.8 (4) 関数mergeを再帰を用いて定義せよ。ただしinsertやisortなど整列されたリストを処理する関数は利用してはならない

merge':: Ord a => [a] -> [a] -> [a]
merge' xs [] = xs
merge' xs (y:ys) = merge' m' ys
      where m' = [x'|x'<-xs,x'<=y] ++ [y] ++ [y'|y'<-xs,y<y']

第一章で紹介されていたqsortのパクリ版。ysから要素を一つずつ取り出して、xsの要素に追加。ysの要素がなくなれば終了です。xsが整列されていない場合正しく動作しませんが、一応お題ではxs,ysのリストはソート済みということなのでクリア。

merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys) = if x <= y then
                        x:merge xs (y:ys) 
                      else
                        y:merge (x:xs) ys

模範解答では、xs,ys両方ソートされていないとうまくいきませんが、僕の解答はxsのみソートされていれば良いので多少優位かも。計算量もたぶん同程度ですから正答とします。

6.8 (5) 関数mergeを使ってマージソートを実行する関数msortを再帰を用いて定義せよ

halve' ::[a] -> ([a],[a])
halve' [] = ([],[])
halve' xs = (take n xs,drop n xs)
    where n = (length xs) `div` 2

msort' ::Ord a => [a] -> [a]
msort' []　= []
msort' [x] = [x]
msort' [x,y] = if x <= y then [x,y] else [y,x]
msort' xs = merge' (msort'　(fst　(halve' xs))) (msort' (snd　(halve' xs)))

これは、ヒントの"halveを使え"のおかげですぐにできた。細部は微妙に違いますが問題ないでしょ。

6.8 (6) 五段階の行程を使って以下のライブラリ関数を定義せよ

6.1 要素の和を計算するsum

sum' :: Num a => [a] -> a
sum' [] = 0
sum' (x:xs) = x + sum' xs

解答ではステップ５でfoldrを使っています。が、一応順を追って進めていますのでまだ説明のなされていないfoldrはなくても良いことにします。（が、実際にはチラとも思い浮かびませんでした）

6.2 リストの先頭からn個の要素を取り出すtake

take' :: Int -> [a] -> [a]
take' _ [] = []
take' 0 xs = []
take' (n+1) (x:xs) = x : take' n xs

パタンマッチの"take' 0 xs = []"はワイルドカードを使うべきでした。が、逆に解答の"take (n+1)[] = []"もワイルドカードにすべきじゃないのかと思いましたがどうなんでしょうか？深い意味でもあるのかどうか...

6.3 空でないリストの末尾を取り出すlast

last' ::[a] -> a
last' [a] = a
last' (x:xs) = last' xs

ここでも、最後をワイルドカードにしていません。なんか詰めの甘い自分。