すごいHaskell四章

Haskellでは命令形言語のように計算をどうやってするかを指定するのではなく、求めるものが何であるかを宣言して計算を行うからです。（52p）

問題の基底部

これ以上分解できなくて解を明示的に（再帰を使わずに）定義しなければならないケース（複数あるかも）（51p）

講義で再帰やったときはあんまり考えてなかったけど、基底部ってものすごく重要だと思う。
ここが再帰定義の起点になるはず。
問題を同じ種類の小さな問題に分解して解いていくなら、一番小さな問題が基底部なのかな。
結果を直接定義するために再帰的定義を使う…まだちょっと良くわからない。

replicate'

数値と要素を受け取って、数値分の要素をもったリストを返す。
自分で書いてみたのが下の。

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

これだと0より小さい値が指定された時に対応できない。あと、[x] ++ じゃなくて、 x : でいい。リストの先頭だから。パターンで対応できない時はガードを使えばいいんだな…。

take'

本の例をそのまま書いちゃうけど、

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

ここでぶったまげることが2つあって、1つはパターンマッチとガードを組み合わせて使ってること。nが0以下の場合を定義するのにガードを使ってる。これって実質ifみたいな感じなんだろうけど…。この使い方、パッと出てこなさそう。
もう1つはガードにotherwiseがないところ。ここでは失敗すると次のパターンに移るようになっている。もし、ガードをのある式が一番下に来てたら、otherwiseがいるはず。

ところで、takeの引数に負の値を指定したら空リストが返ってくるんだけど、負の値は丸括弧で囲まないとだめみたい。

ghci> take -1 [1,2,3]

<interactive>:1:6:
    No instance for (Num (Int -> [a0] -> [a0]))
      arising from a use of `-'
    Possible fix:
      add an instance declaration for (Num (Int -> [a0] -> [a0]))
    In the expression: take - 1 [1, 2, 3]
    In an equation for `it': it = take - 1 [1, 2, 3]

<interactive>:1:7:
    No instance for (Num ([t0] -> Int -> [a0] -> [a0]))
      arising from the literal `1'
    Possible fix:
      add an instance declaration for (Num ([t0] -> Int -> [a0] -> [a0]))
    In the expression: 1
    In the second argument of `(-)', namely `1 [1, 2, 3]'
    In the expression: take - 1 [1, 2, 3]

ghci> take (-1) [1,2,3]
[]

repeat'

引数にとった要素の無限リストを作る。

repeat' :: a -> [a]
repeat' x = x : repeat' x

基底部がない再帰定義で無限リストを作ってる。

zip'

2つのリストを取って、それぞれの要素を順にペアにしたリストを返す。
片方のリストが空になったら終了。

なんか　リストの要素を1つチェック→残りを再帰　のパターンが多い。

クイックソート

ピボット以外の値をピボット以下か大きいかに分けて、それぞれをクイックソート。
本の定義：

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) = 
    let smallerOrEqual = [a | a <- xs, a <= x]
        larger = [a | a <- xs, a > x]
    in  quicksort smallerOrEqual ++ [x] ++ quicksort larger

これ、2つに分ける時にリスト内包を使ってるのが鮮やかすぎる。こうすれば ++ で連結していけば基底部の空リストも普通に繋げられるし。そこでletを使って、直で式を評価してるのもすごい。どうやったらこんなのすぐ出てくるようになるんだろう。
書き換えだとこんなのしか思いつかない。

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
    quicksort smallerOrEqual ++ [x] ++ quicksort larger
    where smallerOrEqual = filter (x >= ) xs
          larger         = filter (x <)   xs

smallerOrEqualとlargerの名前をつけて、定義を分けるのはやっぱり良い気がする。

ところで、

filter (x >= ) xs

は、

filter ( <= x) xs

と書いても動くっぽい。何が言いたいかというと、<= に与える引数は前に置いても後ろに置いてもいいってこと。

この章意外と短かった。