Haskell – ページ 10 – blog.PanicBlanket.com

練習問題

今日は目先を変えて練習問題をやろう。
「入門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]
[]

型クラス

昨日（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) => の部分も引数にした関数の都合で現れたものだけど，これは別のエントリで改めて書くことにしよう。
今日はこれくらいで。

詳解・id:nobsunさん版 tr

ちょっと大げさか。

　cf. OSS WEB|ossz|oneline|2006-04-28

tr :: [Char] -> [Char] -> (String -> String)
tr set1 set2 = map trans
  where
    trans = foldl (flip $ uncurry add) id (zip set1 set2)
    add k v s q | k == q = v
                | otherwise = s q

これがちゃんと動くことは試してみればすぐにわかる。けど，どうやって動くのかがわかんないぞ。
というわけで，細かく見ていくことにしよう。想定する読者は1週間後の自分。

まずは tr の引数から。定義には書かれていないけど3つの引数をとる。= の右側の map がとるはずの2つの引数のうちひとつしか書いてないから，もうひとつの引数が隠れているのがわかる。これを str としよう。
それからもうひとつ，trans のなかで set1，set2 が使われてるから，この２つは trans の引数だと考えることもできる。さらに str のうちの１文字を引数に取るはずだから trans は３つの引数をとる関数ということになる。
これらを明示的に書いてやるとこうなる。

tr set1 set2 str = map (trans set1 set2) str
  where
    trans set1 set2 c = foldl (fllip $ uncurry add) id (zip set1 set2) c
    add k v s q | k == q = v
                | otherwise = s q

つぎは add。これが実際の文字の変換を行う関数だろう。引数を４つとって，うち３つめは何らかの関数。
で，問題は trans の中身。ここがわからない。foldl は引数を３つとる関数だけど，ここでは４つとっているように見える。なぜだ，おかしい。

わかんないから，それぞれの関数の型を順に追ってみることにしよう。ghci で関数の型を確認できるように wehre 節をなくして次のように書き換える。

tr set1 set2 = map (trans set1 set2)
trans set1 set c = foldl (flip $ uncurry add) id (zip set1 set2) c
add k v s q | k == q = v
            | otherwise = s q

それじゃいってみよう。まずは trans。

trans :: (Eq b) => [b] -> [b] -> b -> b

思った通り３引数。
つぎはその中身のほうを少しずつ確かめてみよう。foldl の第１引数と思われる filp $ uncurry add の中を少しずつ。
add

add :: (Eq a) => a -> t -> (a -> t) -> a -> t

uncurry add

uncurry add :: (Eq a) => (a, b) -> (a -> b) -> a -> b

add の第１，第２引数をひとつのタプルにまとめている。t が b に変わってるけどこれは型変数の名前が変わっただけだから気にしない。
つぎ，flip $ uncurry add

flip $ uncurry add :: (Eq a) => (a -> b) -> (a, b) -> a -> b

第１引数と第２引数を入れ替えてるだけだな。
つぎは foldl (flip $ uncurry add) ……のまえに foldl を確認。

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

ほーらおかしい。第１引数の関数は (a -> b -> a) じゃなきゃいけないのに (flip $ uncurry add) は(a -> b) -> (a, b) -> a -> b だ。なのに実際に確かめてみると

foldl (flip $ uncurry add) :: (Eq a) => (a -> b) -> [(a, b)] -> a -> b

なぜだ。(flip $ uncurry add) の型 (a -> b) -> (a, b) -> a -> b とfoldlの第１引数の型 (a -> b -> a) を眺めながら考える。

……考える。

……まだ眺める。

……一晩寝る。

あー！！そうか，カリー化だ。３引数の関数に引数を１つ与えると２引数の関数が得られる。もう１つ引数を与えれば１引数の関数を得る。
つまり flip $ uncurry add を３引数の関数じゃなく，２引数をとって１引数の関数を返す関数だと考えればいい。型式で書くとこう。

flip $ uncurry add :: (Eq a) => (a -> b) -> (a, b) -> (a -> b)

これなら foldl の第１引数の型と対応するじゃないか。

(a -> b) -> (a, b) -> (a -> b)
   |          |          |
   |          |          |  (a -> b) と a ，(a, b) と b が対応する
   |          |          |
   a     ->   b    ->    a

この対応にしたがって foldl の型を書き換えてみると

foldl :: ((a -> b) -> (a, b) -> (a -> b)) -> (a -> b) -> [(a, b)] -> (a -> b)

これに (a -> b) -> (a, b) -> (a -> b) である (flip $ uncurry add) を与えて得られる関数の型は

(a -> b) -> [(a, b)] -> (a -> b)

上で書いた foldl (flip $ uncurry add) の型と一致する（一番右の a -> b を括弧でくくってやればいい）。つまり，この関数は「 (a -> b) である関数と [(a,b)] －－(a,b)であるタプルのリスト－－を引数にとって (a -> b) である関数」を返すってことだ。

ここまでくればあとは簡単だ。
実際の引数を見てみると，第１引数には id，第２引数には zip で得られるタプルのリストとなっている。id の型は (a -> a) だけど，これは a と b がおなじ型だと考えればいい。set1 と set2 は両方とも文字列で，こっちも a と b がおなじになるから問題はない。でもってその結果は（bをaに置き換えて書けば） (a -> a) である関数，となる。
結局，foldl (flip $ uncurry add) id (zip set1 set2) は「文字を引数にとって，適切に変換した文字を返す関数」ってことになる。どう変換するかは関数自体が知っている－－(zip set1 set2)がいわば変換テーブルになっている。これが trans の実体って訳だ。

tr 全体ではさらに簡単。trans を str の頭から順に適用しているだけだ。

ふー。やっと解読したって感じだな。なんか，関数は値を返すものだというのがしみこんでいて，「関数を返す関数」というのに頭が回らない。なんだか「関数を返す関数」を自在に使えるようになることが関数言語使いになるってことなのかと思った。

ところで，話は変わるけど。

あれっ．これだめだ．tr “aaa” “xyz” “abracadabra” は tr “a” “z” “abracadabra” と同じじゃなきゃいけないのに．．．

これはそういうものなんだろうか。俺のPCに入ってる tr コマンドでは ‘a’ は ‘x’ に変換される。

>echo abracadabra | tr aaa xyz
xbrxkxdxbrx

このコマンド，Windows には付いてないからどこからか手に入れたもののはず。よく覚えてないけど GNU だか Cygwin だったかじゃなかったかなぁ。

tr

tr コマンドもどき。文字列中の文字を置き換える。

import Data.List

tr _ _ [] = []
tr str1 str2 (c:cs) = (tr' str1 str2 c):(tr str1 str2 cs)
  where tr' str1 str2 c = case (elemIndex c str1) of
                            Just n  -> str2 !! n
                            Nothing -> c

キモは elemIndex の返り値。elemIndex は文字列 str1 中の文字 c のインデックス（0から始まる）を返す関数だけど，返り値の型が Int じゃなくて Maybe Int なので，case で場合分けをしている。はじめこの返り値の型に気づかなくて悩んでしまった。こういうのは真っ先に確認すべきだな。

*Main> :type elemIndex
elemIndex :: (Eq a) => a -> [a] -> Maybe Int

結果。

*Main> tr "ab" "AB" "banana"
"BAnAnA"

ところで，引数に文字列を３つとるのはいいけどその名前が str1，str2 っていうのは我ながらどうかと思う。こういうのってセンスが問われるよなぁ。

追記：
再帰じゃなくて map を使うようにした。ついでに引数の名前を短く。

import Data.List

tr _ _ [] = []
tr s1 s2 str = map (tr' s1 s2) str
  where tr' s1 s2 c = case (elemIndex c s1) of
                        Just n  -> s2 !! n
                        Nothing -> c

さらに追記：
tr’ の引数を省略。ちょっとすっきりした。こうやって where 節で局所定義された関数から外側の関数の引数を直接参照できるのっておもしろいねぇ。

import Data.List

tr _ _ [] = []
tr s1 s2 str = map tr' str
  where tr' c = case (elemIndex c s1) of
                  Just n  -> s2 !! n
                  Nothing -> c

*Main> tr "ab" "AB" "banana"
"BAnAnA"

インデントスタイル（またはレイアウトシステム）

「入門Haskell」ではインデントスタイルについては，必要なときにその都度，といった感じでまとまった説明がなかった。

moiの頭の中 – 3.5 Functions(その3)

Haskellはコードを構築するのに「レイアウト」と呼ばれるシステムを用いる（プログラミング言語Pythonは似たシステムを用いている）。レイアウトシステムは、CやJavaのような他の言語が必要とする明示的なセミコロンや中括弧なしでコードを書くことができる。

moiの頭の中 – 3.5 Functions(その4)

レイアウトについての一般的な規則は、let、doそしてofキーワードの位置の次に開き中括弧が挿入され、次の命令が現れる桁位置が記憶されることである。それ以降、セミコロンが同じ量を字下する全ての行の前に追加される。次の行を字下げしないなら、閉じ中括弧が追加される。

つまり，let，do，of のあとに続く語とそれに続く行の先頭をそろえろってことだな。こんな風に。

f x = case x of 1 -> "one"
                2 -> "two"
                3 -> "three"
                _ -> "many"

中括弧やセミコロンが云々というのは，上のコードがこんな風に解釈されるってことか。

f x = case x of {1 -> "one";
                 2 -> "two";
                 3 -> "three";
                 _ -> "many"}

ようするに見やすく書けば問題なさそうだ。

ところで，if ～ then ～ else や where 節については書いてないがどうなんだろう。
まずはif ～ then ～ else から。いままで then，else は if よりも下げて書いてたけどおなじインデントでも大丈夫。

f x = if x > 0
      then "Positive"
      else "Negative or Zero"

*Main> f 0
"Negative or Zero"

if よりも前にあっても大丈夫のようだ。

f x = if x > 0
    then "Positive"
  else "Negative or Zero"

*Main> f 2
"Positive"

なら where 節は？

f x = map g x
  where g 0 = 1
        g 1 = 0

*Main> f [1,0,0,1,1,1]
[0,1,1,0,0,0]

こっち（↓）がダメなのは，関数（g）定義の先頭があってないからだろうな。

f x = map g x
  where g 0 = 1
      g 1 = 0

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

ind.hs:14:8: parse error on input `g'

ついでにガード節。これも大丈夫なんだ。

f x | x < 0 = (-1) * x
  | x > 0 = 1 * x
 | otherwise = 0

*Main> f 3
3
*Main> f 0
0
*Main> f (-2)
2

まとめ。

let，do，of のあと（という中というか）は頭をそろえる。
関数定義の頭はそろえる。
where 節やガード節はそろえなくても大丈夫（だけど見やすいようにそろえる）。

日	月	火	水	木	金	土
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

カテゴリー: Haskell

練習問題

関数の合成

ポイントフリースタイル

練習問題

スーパークラス／サブクラス

型クラス

関数の型

詳解・id:nobsunさん版 tr

tr

インデントスタイル（またはレイアウトシステム）