blog.PanicBlanket.com

「入門Haskell―はじめて学ぶ関数型言語」　p.78 より。

(3) unlines，unwords を intersperse を使って定義しなさい。また使わずに定義しなさい。

まずは使う方から。

myUnlines = (concat . intersperse "\n")

myUnwords = (concat . intersperse " ")

結果。

*Main> myUnlines ["abc","def","ghi"]
"abc\ndef\nghi"
*Main> myUnwords ["abc","def","ghi"]
"abc def ghi"

OK……とおもったら，unlines は一番最後にも改行文字が付くのか。

*Main> unlines ["abc","def","ghi"]
"abc\ndef\nghi\n"

そしたらこうか。あんまりきれいじゃないなぁ。

myUnlines [] = ""
myUnlines list = (concat . intersperse "\n") list ++ "\n"

*Main> myUnlines ["abc","def","ghi"]
"abc\ndef\nghi\n"

OK。

intersperse を使わないほう。これは似たようなことを前（cf. id:takatoh:20060413）にやった。

myUnlines2 [] = ""
myUnlines2 (x:xs) = x ++ "\n" ++ myUnlines2 xs

myUnwords2 [] = ""
myUnwords2 (x:[]) = x
myUnwords2 (x:xs) = x ++ " " ++ myUnwords2 xs

結果。

*Main> myUnlines2 ["abc","def","ghi"]
"abc\ndef\nghi\n"
*Main> myUnwords2 ["abc","def","ghi"]
"abc def ghi"

こっちはすんなりOK。

id:a-san さんの両替するのに何通りあるか？に刺激されて，両替の組み合わせを列挙する enumChange をつくってみた。Maybe の扱いでちょっと苦労したよ。

　cf. http://d.hatena.ne.jp/a-san/20060508#p1

enumChange coins amount = map peel (cc amount 0)
    where
        cc amount kindsOfCoins
            | amount == 0 = [Just []]
            | (amount < 0) = [Nothing] | kindsOfCoins >= length coins = [Nothing]
            | otherwise =
                filterN ((cc amount (kindsOfCoins + 1)) ++
                       (divide faceOfCoin (cc (amount - faceOfCoins) kindsOfCoins)))
            where
                faceOfCoin = coins !! kindsOfCoins

divide a = map divide'
    where
        divide' x = case x of
            Just m -> Just (a:m)
            Nothing -> Nothing

filterN list = filter (\x -> x /= Nothing) list

peel x = case x of
             Just m -> m
             Nothing -> error "`Nothing' is found."

実行。

*Main> enumChange [10,5,1] 10
[[1,1,1,1,1,1,1,1,1,1],[5,1,1,1,1,1],[5,5],[10]]
*Main> length $ enumChange [10,5,1] 10
4

countChange は id:a-san さんのもの。

*Main> length $ enumChange [500,100,50,10,5,1] 100
159
*Main> countChange [500,100,50,10,5,1] 100
159
*Main> length $ enumChange [50,25,10,5,1] 100
292
*Main> countChange [50,25,10,5,1] 100
292
*Main> enumChange [500,100,50,10,5,1] 100
[[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[5,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[5,
5,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1],[5,5,5,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[5,5,5,5,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
（以下略）

いけてるみたいだな。

以下，自分用のメモ。

• cc は両替したコインの組み合わせのリストを返す。
• amount == 0 ならうまくいった組み合わせなので，リストの終端としての空リストを返す。
• (amont < 0)，kindsOfCoins >= length coins のときはその組み合わせがうまくいかないときなので Nothing。
• (cc amount (kindsOfCoins + 1)) は kindsOfCoins のコインを１枚も使わない場合の組み合わせ。返ってくるリストには Nothing が混じっているから filterN で取り除いてやる。
• (divide …) は kindsOfCoins のコインを１枚以上使う場合の組み合わせ。これは kindsOfCoins のコインを０枚以上使って (amount – faceOfCoin) を両替する場合の組み合わせのそれぞれに，kindsOfCoins を１枚追加して求めている。
• cc の返すリストは Maybe [a] のリストだから peel で Maybe をはずす。

追記：
Data.Maybe に catMaybes という関数があった。わざわざ peel を作んなくてもよかったのか。
GHCi で使うなら :module Data.Maybe，プログラムで使うなら import Data.Maybe しておく。

Prelude Data.Maybe> :type catMaybes
catMaybes :: [Maybe a] -> [a]
Prelude Data.Maybe> catMaybes [Just 1, Just 2, Just 3]
[1,2,3]

Nothing は無視してくれるみたいだ。

Prelude Data.Maybe> catMaybes [Just 1, Nothing, Just 3]
[1,3]

ってことは filterN もいらないのか……orz

id:hyuki さんのを見て。

　cf. http://sicp.g.hatena.ne.jp/hyuki/20060512/pascal

といっても Scheme はよくわからんので Ruby版（id:rubyco:20060429:pascal）を見ながら書いた。

combination n k | k == 1 = 1
                | k == n = 1
                | otherwise = (combination (n-1) k) + (combination (n-1) (k-1))

line n = map (combination n) [1..n]

pascalTriangle = do mapM putStrLn (map (show . line) [1..10])

実行。

*Main> pascalTriangle
[1]
[1,1]
[1,2,1]
[1,3,3,1]
[1,4,6,4,1]
[1,5,10,10,5,1]
[1,6,15,20,15,6,1]
[1,7,21,35,35,21,7,1]
[1,8,28,56,70,56,28,8,1]
[1,9,36,84,126,126,84,36,9,1]

「入門Haskell―はじめて学ぶ関数型言語」　p.73 より。
①は面倒なだけなのでパス。

②foldr の定義を書きなさい。

foldr は後ろから引数の関数を適用するんだからこうだろう

myFoldr f a x:[] = f x a
myFoldr f a (x:xs) = f x (myFoldr f a xs)

実行。

*Main> myFoldr (++) "d" ["a","b","c"]
"abcd"
*Main> foldr (++) "d" ["a","b","c"]
"abcd"

OK。ちゃんとできてるな。

③reverse は，リストを逆転させる関数です。たとえば reverse [1,2,3] は [3,2,1] になります。この reverse を定義しなさい。

myReverse [] = []
myReverse (x:xs) = myReverse xs ++ [x]

*Main> myReverse "abcde"
"edcba"

こちらもOK。

２つの関数を f と g とすれば f . g と単純に行くのは g の引数が１つの場合だけ。２つ以上の引数をとる場合にはちょっと複雑になる。次のような関数で確かめてみる。

f a = a:[]

g a = a:[]
g2 a b = a:b:[]
g3 a b c = a:b:c:[]

まずは簡単な f と g

*Main> :t f . g
f . g :: a -> [[a]]

引数を２つとる g2 に対して同じようにやると

*Main> :t (f . g2)
(f . g2) :: a -> [a -> [a]]

こんな型になって２つの引数をうまく追い出せない。

*Main> (f . g2) 1 2

<interactive>:1:0:
    Couldn't match `[a -> [a]]' against `t -> t1'
      Expected type: [a -> [a]]
      Inferred type: t -> t1
    Probable cause: `(f . g2)' is applied to too many arguments in the call
        ((f . g2) 1 2)
    In the definition of `it': it = (f . g2) 1 2

追い出してやるには，関数合成を２段階にする。

*Main> :t ((f .) . g2)
((f .) . g2) :: a -> a -> [[a]]
*Main> ((f .) . g2) 1 2
[[1,2]]

引数が３つの場合には３段階。

*Main> :t (((f .) .) . g3)
(((f .) .) . g3) :: a -> a -> a -> [[a]]
*Main> (((f .) .) . g3) 1 2 3
[[1,2,3]]

逆に１つ目の関数のほうが複数引数の時は単純に合成できる。

*Main> :t g3 . f
g3 . f :: a -> [a] -> [a] -> [[a]]

ただし，引数のほうがややこしい。上の例で行くと１つ目の引数は f の引数，２つ目以降が g3 の２番目３番目の引数となる。こうすればわかりやすい。

g3 (f a) b c

実行。

*Main> (g3 . f) 1 [2] [3]
[[1],[2],[3]]

じゃあ，引数が３つと２つならどうだ。

*Main> :t (g3 .) . g2
(g3 .) . g2 :: a -> a -> [a] -> [a] -> [[a]]
*Main> ((g3 .) . g2) 1 2 [3] [4]
[[1,2],[3],[4]]

ああ，ややこしい。

今日は目先を変えて練習問題をやろう。
「入門Haskell―はじめて学ぶ関数型言語」　p.72 より。

①前ページの実装から，takeとdropに大きな値や負の値が入った場合の対処をしなさい。

前ページの実装とはこれ。Prelude の関数とかぶってはいけないので名前は変えてある。

mytake 0 _ = []
mytake n (x:xs) = x : mytake (n-1) xs

mydrop 0 xs = xs
mydrop n (x:xs) = mydrop (n-1) xs

mytake に大きな値を入れるとリストそのもの，負の値を入れると空リストが返るようにする。逆に mydrop に大きな値を入れると空リスト，負の値を入れるとリストそのものが返るようにする。

mytake _ [] = []
mytake 0 _ = []
mytake n (x:xs) | n < 0 = []
               | otherwise = x : mytake (n-1) xs

mydrop _ [] = []
mydrop 0 xs = xs
mydrop n (x:xs) | n < 0 = x:xs
                | otherwise = mydrop (n-1) xs 

もっとすっきり書けそうだけどまぁいいか。実行結果。

*Main> mytake 10 [0,1,2,3,4,5]
[0,1,2,3,4,5]
*Main> mytake (-2) [0,1,2,3,4,5]
[]
*Main> mydrop 10 [0,1,2,3,4,5]
[]
*Main> mydrop (-2) [0,1,2,3,4,5]
[0,1,2,3,4,5]

ふたつめ。

②take と drop を同時に実行する splitAt :: Int -> [a] -> ([a], [a]) があります。たとえば
splitAt 2 [1,2,3,4] — ([1,2], [3,4])
のように，結果のタプルの第１要素が take ，第２要素が drop になります。この splitAt を定義しなさい。また，take と drop を splitAt を使って定義し直しなさい。

まずは splitAt のほうから（名前は変えてある）。

mysplitAt _ [] = ([], [])
mysplitAt n xs = ((take n xs), (drop n xs))

結果。

*Main> mysplitAt 2 [1,2,3,4]
([1,2],[3,4])

よし。じゃ，これを使って mytake と mydrop を定義し直すと

mytake n xs = fst $ mysplitAt n xs

mydrop n xs = snd $ mysplitAt n xs

結果は

*Main> mytake 3 [1,2,3,4,5]
[1,2,3]
*Main> mydrop 3 [1,2,3,4,5]
[4,5]

もうひとつ。

③takeWhile は，(a -> Bool) -> [a] -> [a] という型です。takeと似ていますが，決まった数だけとるのではなく，要素を計算し たら真である限りtakeし，一度でも失敗したら残りは返しません。これを定義しなさい。

こんなんでどうかな。

mytakeWhile _ [] = []
mytakeWhile f (x:xs) | f x = x : mytakeWhile f xs
                     | otherwise = []

*Main> mytakeWhile (\x -> x > 0) [3,2,1,0,-1,-2,-3]
[3,2,1]
*Main> mytakeWhile (\x -> x < 0) [3,2,1,0,-1,-2,-3]
[]

今日の一行 – ポイントフリースタイルを参考にして mytake から引数を消してみる。

mytake n xs = fst $ mysplitAt n xs
            ↓
mytake n xs = fst (mysplitAt n xs)
            ↓　関数合成を使って xs を外に追い出す
mytake n xs = (fst . (mysplitAt n)) xs
            ↓　xs を消す
mytake n    = (fst . (mysplitAt n))
            ↓ 関数合成演算子を前置
mytake n    = (.) fst (mysplitAt n)
            ↓　もう一度，関数合成演算子を使って今度は n を追い出す
mytake n    = (((.) fst) . mysplitAt) n
            ↓　n を消す
mytake      = ((.) fst) . mysplitAt

結果。

*Main> mytake 2 [1,2,3,4]
[1,2]

おお！うまくいった！すごいな。
ポイントは関数合成とその演算子を前置するところだな。

んー，待てよ。単純にこうやったらどうだ？

mytake = fst . mysplitAt

*Main> :l mysplitAt.hs
Compiling Main             ( mysplitAt.hs, interpreted )

mysplitAt.hs:25:20:
    Couldn't match `(a, b)' against `t -> t1'
      Expected type: (a, b)
      Inferred type: t -> t1
      Expected type: Int -> (a, b)
      Inferred type: Int -> [a1] -> ([a1], [a1])
    In the second argument of `(.)', namely `mysplitAt'
Failed, modules loaded: none.

だめか。
そうか， (.) fst が関数を引数にとる関数で，これと mysplitAt を合成すると，mysplitAt の引数が外に追い出されるんだ。つまりこう。

mytake n xs = (((.) fst) . mysplitAt) n xs

で，引数が消える，と。

今日もメモ程度。

値の大小関係を表すには Ord クラス。「入門Haskell」によればOrd クラスの定義は次のようである，らしい。

class Eq a => Ord a where
  (>) :: a -> a -> Bool
  (<) :: a -> a -> Bool
  (>=) :: a -> a -> Bool
  (<=) :: a -> a -> Bool
  compare :: a -> a -> Ordering
  max :: a -> a -> a
  min :: a -> a -> a

大小関係を判定するには等しいか否かを判定できなければならない，というわけで Eq a => Ord a となっている。このとき，Eq は Ord のスーパークラスであるといい，逆に Ord は Eq のサブクラスであるという。
関数の型のときにでてきた context みたいなものか。

ところで，Ord クラスのインスタンスに Bool も含まれてるんだけど，これってどんなときに使うんだろう。

Prelude> True < False
False
Prelude> True > False
True

True は False より大きいとか言われても，何それ。

昨日（id:takatoh:20060506:type）の最後にあげた関数の型

Prelude> :type map (\x -> x * 2)
map (\x -> x * 2) :: (Num a) => [a] -> [a]

の中に現れる (Num a) => という部分は，a が Num クラスのインスタンスでなければならないことを表している。つまりこの場合には，引数に 2 を掛けるという関数なのだから，引数は 2 と掛け算ができる型でなければならない。それが Num クラスのインスタンス，というわけだ。
この，型変数 a に対するいわば制約をコンテキスト（context）という。

型クラスというのは，いくつかの型に共通する性質をまとめたもの，というふうに理解したらいいだろうか。
たとえば，「一致するか否かを比較判定できる」という性質は Eq クラスにまとめられているけど，この性質は 文字（Char）や数値（Int，Float）などに共通する。このとき，Char や Int を Eq クラスのインスタンスという。というか，Char や Int は Eq クラスのインスタンスとして定義されている。

クラスに定義されている関数をメソッドといい，Eq クラスには比較のためのメソッド (==) と (/=) が定義されている。

Prelude> :type (==)
(==) :: (Eq a) => a -> a -> Bool
Prelude> :type (/=)
(/=) :: (Eq a) => a -> a -> Bool

Eq クラスのインスタンスである型ならこのメソッドを適用できる。

Prelude> 'a' == 'a'
True
Prelude> 100 == 200
False
Prelude> 1.24 /= 1.25
True

リストでも大丈夫みたいだ。

Prelude> [1,2,3] == [1,2,3]
True

代表的なクラスをいくつか。

Eq　Num　Show　Read　Ord

ところで，ふだん Ruby をメインに使っている俺としては，このクラスとインスタンスの関係にはちょっと違和感がある。
Haskell でいう Char とか Int とかの型（type）が Ruby ではクラスであって，その具体的な値（”abc” とか 10 とか）をインスタンスという。Haskell のクラスに当たるものは Ruby には……ないよな。あえて言えばスーパークラスか？……それも違うな。
逆に Ruby のインスタンスに当たるものは Haskell ではなんと言うんだろう。

連休前は仕事がつまってこのblogの更新もままならないほどのGW進行だったというのに，いざ休みになってみると一転，だらけモードで逆の意味でGW進行になってしまった。なんてこった。
気を取り直していこう。まずはこの間（id:takatoh:20060429:tr）はまった関数の型から。

Haskell の関数には型がある。簡単に言うとどんな型の引数をとってどんな型の値を返すか，というのが関数の型。
GHCi では :type コマンドで確認できる。たとえば length は何かのリストを引数にとってその長さ（Int型）を返す。

Prelude> :type length
length :: [a] -> Int

この表記を型式（かたしき）という。
[a] は「何かのリスト」を表していて，その「何か」はChar でも Int でもそのほかの何でもいい。とにかくリストならいいわけだ。
これを多相型（polymorphic type）といい，表記に使われている a を型変数（type variable）という。

Prelude> :type zip
zip :: [a] -> [b] -> [(a, b)]

型変数に a と b が使われているのは，一般に違う型であることを表している。おなじ型でもかまわない。
関数を引数にとる高階関数はこんな風に表される。

Prelude> :type map
map :: (a -> b) -> [a] -> [b]

(a -> b) が引数の関数を表している。

さて，ここからがこの間のキモに関わる部分。型式のなかに -> という記号が使われているが，これは

• 型に関する二項演算子で
• 右結合

だ。つまり，map は

map :: (a -> b) -> ([a] -> [b])

とも解釈できる。この意味するところは，「(a -> b) である関数を一つ引数にとって，([a] -> [b])である関数を返す」関数だということ。実際にやってみると

Prelude> :type map (\x -> x * 2)
map (\x -> x * 2) :: (Num a) => [a] -> [a]

引数にした関数の都合で両方とも a になってしまったが，ちゃんと「リスト（[a]）を引数にとってリスト（[a]）を返す」関数になっている。

それと， (Num a) => の部分も引数にした関数の都合で現れたものだけど，これは別のエントリで改めて書くことにしよう。
今日はこれくらいで。