オブジェクトの相互参照 と 関数の相互再帰 (1)

オブジェクトの相互参照

例えば、「人」には「名前」があり、将来一人の「パートナー」を得ることができるとする。生まれたてはパートナーがいない状態。「結婚」によりパートナーを得て、「離婚」によりパートナーを失う。ただし、結婚により相互に参照することが可能だとする。これを示したのが下図。

Python で表現するなら、まずはインスタンス変数と get メソッド、print 文に対応するための __str__() を定義。 (cf. print 文でオブジェクトの情報を表示)

class Person:
    def __init__(self, name):
        self.__name = name
        self.__partner = None

    def getName(self): return self.__name

    def __str__(self):
        return self.__name + "<" + (self.__partner.getName() if self.__partner else "None") + ">"

次に、結婚したとき相互に参照できるよう marry() メソッドを定義。既にパートナーがいるときは何もしないことにする。

class Person …

    def marry(self, partner):
        u""" 結婚 """
        if self.__partner: return
        self.__partner = partner
        partner.marry(self)

離婚したときはパートナーを参照できないようにする。ただし、パートナーがいないときは何もしない。

class Person …

    def divorce(self):
        u""" 離婚 """
        if not self.__partner: return
        partner = self.__partner
        self.__partner = None
        partner.divorce()

動作を確かめる。

tarou  = Person("Tarou")
hanako = Person("Hanako")

# 結婚
tarou.marry(hanako)
print tarou, hanako  #=> Tarou<Hanako> Hanako<Tarou>

# 離婚
hanako.divorce()
print tarou, hanako  #=> Tarou<None> Hanako<None>

コード全体はこちら。

 

相互再帰

Python ではオブジェクトが相互参照している状態と、その後、参照をなくすという変化を自然に記述することができる。ここで自然と感じるのは、自分が考える枠組みがそれに馴染んでいるということに過ぎない。では、これと同様のことを表現するのに Haskell ではどうすればいいのだろう？ ただし、まずはオブジェクトシステムにおけるオブジェクト識別子 (OID) のようなものついて考慮しない。

ところで、「相互参照」から連想するのは「相互再帰」という言葉。これは Haskell の let 式の説明で出てきた。

let 式によってつくられる束縛の集りは、相互再帰的 ( mutually recursive )で、パターン束縛は遅延パターンとして扱われます

(A Gentle Introduction to Haskell: Patterns の let 式 より)

Let 式 は let { d₁ ; ... ; d_n } in e という一般形式を持ち、入れ子でレキシカルスコープで相互再帰的な宣言リスト (このような let は他の言語ではよく letrec と呼ばれる) を持つ。

(Haskell 98 Report: 式 の 3.12 let 式 より)

Haskell に限らず一般的な意味として、相互再帰 - Wikipedia によると、

再帰呼び出しの一種であり、2つの関数が互いを使って定義されているものをいう。

 

相互再帰の例

この例として、Mutual recursion - Wikipedia には、数字が奇数であるか (odd?) 偶数か (even?) 判定する関数が互いを使って定義されている。

function even?(number : Integer)
    if number == 0 then
        return true
    else
        return odd?(abs(number)-1)

function odd?(number : Integer)
    if number == 0 then
        return false
    else
        return even?(abs(number)-1)

0 をベースにして、even? は odd? を、odd? は even? を使って定義しているのがわかる。

(cf. Fun with Functional Dependencies における定義も興味深い。理解できてないんだけど… ^^; )

 

また、A Gentle Introduction to Haskell: Patterns の “4.4 遅延パターン” の例 においても、サーバとクライアントのやりとりを表現した関数が定義されているが、ここでもリクエスト (reqs) とレスポンス (resps) が互いを使って定義されている。

reqs                     = client init resps
resps                    = server reqs

A Gentle Introduction to Haskell: Patterns via kwout

このように、オブジェクトが相互参照している状態は、関数の相互再帰によって表現できそう。

 

相互再帰的な関数 (値) の定義

上記を真似て、Person 型の値を相互再帰的に定義することに。まずは Person 型を定義。その後、let 式において互いを使って値を表現する。

ところで、値を生成するのはデータコンストラクタと呼ばれるが、上記の Person 型を調べればわかるように、

*Main> :t Person
Person :: String -> Partner -> Person

データコンストラクタは関数と似ている。違うのはパターンマッチで利用できるということ。よって、データコンストラクタで値を生成するときに、他の式を参照することは関数の相互再帰と同じと考えても良さげ。

data Person = Person { name    :: String
                     , partner :: Person
                     } 

instance Show Person where
    show (Person n p) = n ++ "{" ++ name p ++ "}"

main = do let tarou  = Person "Tarou"  hanako
              hanako = Person "Hanako" tarou
          print tarou  -- Tarou{Hanako}
          print hanako -- Hanako{Tarou}

tarou は hanako を使って定義し、hanako は tarou を使って定義した。

しかし、これは一見奇妙に思える。なぜなら先ほどの Python の例で、Person クラスのコンストラクタの定義を変更して、パートナーも引数として渡せるようにしたとする。

class Person:
    def __init__(self, name, partner):
        self.__name = name
        self.__partner = partner

このクラスを使って以下のように互いを参照するオブジェクトの生成を試みる。

tarou  = Person("Tarou", hanako)
hanako = Person("Hanako", tarou)

実行した結果は、

NameError: name 'hanako' is not defined

変数 tarou に Person 型のオブジェクトを代入しようとしても、オブジェクトを生成する段階でパートナーである hanako がいないのでエラー。上から下へとプログラムが順次実行され、状態の変化を記述するのが命令型言語の特徴なので、エラーが出て当り前。極めて当然な結果。

しかし、同じ目線で Haskell のコードを見ると、「hanako を定義する前に、tarou の定義で hanako を参照しているからコンパルエラーにならないの？」と思えてしまう。これは、そもそも let 式における定義は順序に意味はなく、何が何を参照して定義しているかを表現しているに過ぎないことによる。

延々と再帰呼出しが続かないよう 適切に Person 型を Show クラスのインスタンスにすれば、print 関数の呼出しも問題なし。もし、Person 型で deriving Show とした場合は出力が無限に続く。 tarou のパートナーは hanakoで、hanako のパートナーは tarou で、tarou のパートナーは… というように。

 

Maybe a 型を使ってパートナーが存在しないことを表現

相互再帰的な定義ができることがわかったので、次は Python と同じように、

1. 最初に値を生成したときはパートナーが存在しない
2. 結婚によりパートナーができる
3. 離婚によりパートナーを失う

という方向へ変更してみる。

パートナーが「いるかいないか」は Maybe a 型を利用。 (cf. Haskell の Maybe a 型と Either a b 型 (1) )

import Data.Maybe

data Person = Person { name :: String
                     , partner :: Partner
                     } deriving Eq
-- パートナー
type Partner = Maybe Person

instance Show Person where
    show (Person n Nothing) = n
    show (Person n p)       = n ++ "{" ++ (name $ fromJust p) ++ "}"

-- 誕生
born n = Person n Nothing

-- 結婚
marry p1 p2 =  (p1 { partner = Just p2 }, p2 { partner = Just p1 })

-- 離婚
divorce (p1,p2) = (p1 { partner = Nothing }, p2 { partner = Nothing })

main = do let tarou  = born "Tarou"
              hanako = born "Hanako"
              m = marry tarou hanako
              d = divorce m
          print m  -- (Tarou{Hanako},Hanako{Tarou})
          print d  -- (Tarou,Hanako)

しかし、これでは値の同値性において、Python がオブジェクトシステムを利用した場合の表現とは異なる。また、状態の変化を模倣しているとも言い難い。 (@_@;

 

関連記事

• オブジェクトの相互参照 と 関数の相互再帰 (2) – Haskell の Data.Unique 型で一意な値を生成

Haskell でリストから特定の要素を抽出する - 再帰的な定義、末尾再帰、filter, elem, partition, intersect

1. リストから特定の要素を抽出したい

例えば、ある村に、村人が 5 人住んでいたとする。

太郎、花子、次郎、三郎、明美

この村には、指名手配されている犯人がいる。指名手配されている犯人のリストは、以下の通り。

花子、三郎、四郎

これより、村にいる犯人を見つけたい。

 

2. 型の定義と、関数の型

最初に、「人」を表す Person 型を定義する。ここでは名前が一致することで、同じ人であるとする。

data Person = P { name :: String } deriving (Show, Eq)

村人のリストを定義。

ps = [P "Tarou", P "Hanako", P "Jiro", P "Saburou", P "Akemi"]

「指名手配されている犯人のリスト」と、「村人のリスト」が与えられたら、一致した人を、リストで返す関数を extract とする。関数の型は次の通り。

extract :: [Person] -> [Person] -> [Person]

 

3. filter 関数を使い、再帰的に定義

Haskell でリストから抽出するには、filter 関数を利用する。

具体的な処理のイメージは、

1. 「指名手配されている犯人のリスト」から、一人ずつ取り出して、
2. 「村人のリスト」と照合し、
3. 一致するものがあれば返す。

リストの要素を順に見ていく処理は、再帰的な定義をする。

1. 最初にパターンマッチにより、指名手配されている犯人のリストを、「先頭の要素」と「それよりも後ろの要素」に分解。
2. 犯人リストの「先頭の要素」と、村人の「先頭の要素」が一致するか調べる。

extract (x:xs) ps = filter (== x) ps …

「先頭よりも後ろの要素」に対して、同じように一致しているか調べる。その結果を、上記の結果と結合して返す。

extract (x:xs) ps = filter (== x) ps ++ extract xs ps

ところで、指名手配されている犯人のリストを、パターンマッチで分解している。そのため、リストを分解しつくし、空リストになった場合を考える必要がある。よって、「指名手配のリストが空なら、一致する人はいない」という定義を加える。

extract []     _  = []

全体を示すと、

extract []     _  = []
extract (x:xs) ps = filter (== x) ps ++ extract xs ps

このような再帰的な定義の仕方を考えると、頭が混乱する。最近、少し慣れてきたかも。

 

4. 末尾再帰呼出しで定義

再帰的に定義できたので、「末尾再帰呼出し」の形に定義を変えてみる。

末尾再帰呼出しの形にするには、次の二つのことが必要。

1. 結果を累積的に保持する役割を持つ引数を追加。
2. 処理の最後で自分自身を呼出す。

最初に、結果を累積的に保持するための引数を、第 2 引数に置く。

extract' (x:xs) acc ps = 

次に、いきなり自分自身を呼出す。

extract' (x:xs) acc ps = extract' …

最初は acc が空だとして、「指名手配されている犯人のリストの先頭要素で、抽出できるか」試す。

extract' (x:xs) acc ps = extract' … (filter (== x) ps) … 

filter 関数で抽出した結果を acc に加える。

extract' (x:xs) acc ps = extract' … (acc ++ (filter (== x) ps)) … 

指名手配されている犯人のリストの残りも、同じように処理すればいいので、引数 acc に追加した結果を、引数に与えて再帰的な呼出しをする。

extract' (x:xs) acc ps = extract' xs (acc ++ (filter (== x) ps)) ps 

ただし、先ほどと同じく、パターンマッチで指名手配されている犯人のリストを分解している。そのため、これが空になった場合についても考えなければいけない。

引数 acc に結果が詰め込まれるはずなので、それをそのまま返す。

extract' []     acc _  = acc

全体を示す。

extract' []     acc _  = acc
extract' (x:xs) acc ps = extract' xs (acc ++ (filter (== x) ps)) ps 

 

関数をラップ

上記で定義した関数を使うには、引数 acc に空リストを与える。

extract' [P "Hanako", P "Saburou", P "Sirou"] [] ps

しかし、毎回、空リストを渡すのは面倒なので、extract’ 関数をラップする関数を定義する。

extract xs ps = extract' xs [] ps
    where
      extract' []     acc _  = acc
      extract' (x:xs) acc ps = extract' xs (acc ++ (filter (== x) ps)) ps 

これで関数のインターフェイスが、最初に定義した関数と同じになった。

末尾再帰呼出すメリットを簡単に言えば、再帰的な関数の呼出しが深くなり過ぎ、スタックオーバーフローしてしまったら、末尾再帰呼出しの形にして正格評価で対処できること。

 

5. 各々の要素が「特定のリストに含まれるか？」検査する方法

「リストの中にある要素が存在するかどうか？」というと、Python の シーケンス型 における `in’ を連想する。

print "Hanako" in ["Tarou", "Hanako", "Jiro"]      #=> True
print "Hanako" not in ["Tarou", "Hanako", "Jiro"]  #=> False

Haskell では elem, notElem 関数に相当する。

*Main> "Hanako" `elem` ["Tarou", "Hanako", "Jiro"]
True
*Main> "Hanako" `notElem` ["Tarou", "Hanako", "Jiro"]
False

問題に戻り、先ほどまでの定義を、

各々の村人を 「指名手配されている犯人のリスト」 から抽出できるか？

に変更。

extract xs ps = filter (\x -> x `elem` xs) ps

部分適用、セクションを利用すると、

extract xs = filter (`elem` xs)

 

抽出ではなく、リストを分割したい場合

抽出ではなく、村人を指名手配されている犯人と、そうでない人に分割したい場合は、Data.List の partition を使う。

import Data.List

extract xs = partition (`elem` xs)

 

6. 共通部分を抽出する方法

村人の集合と指名手配されている人の集合を図に描くと、求めたいのは二つの 集合の共通部分 ということになる。

Data.List には 集合的な操作 として intersect が定義されている。

import Data.List

extract = intersect

つまり、わざわざ自分で関数を定義する必要はなかった。

なぜこれをすぐに連想しなかったのだろう …  パタッ(o_ _)ｏ~†

 

7. Data.Set を利用する

集合の操作をしたいなら、Data.Set モジュールを利用する。

リストと集合の変換は、

fromList  <=>  toList

共通部分 と 差 は、

• intersection
• difference

それぞれ型を見ると、集合の要素が Ord のインスタンスできないといけない。そのため、Person 型に Ord を追加。

import Data.Set

data Person = P { name :: String } deriving (Show, Eq, Ord)

extract xs ps = toList $ xs' `intersection` ps'
    where
      xs' = fromList xs
      ps' = fromList ps

先ほどと同じように、リストを分割したいなら、

extract xs ps = ( toList $ xs' `intersection` ps', 
                  toList $ ps' `difference`   xs' )
    where
      xs' = fromList xs
      ps' = fromList ps

「要素に重複があってはならない」という制約がない限り、partition 使った方が楽かな。

Haskell のリスト定義はなぜあの形？ - 素朴な解釈

cons - Wikipedia via kwout

空リストって何？

以前、「Haskell の cons (コンス) - リストを生成するための演算子 (:)」で、リストの定義とその構造を支えている cons について触れた。

これを書いたことすら忘れかけていた今日この頃、「やさしい Haskell 入門」におけるリストの定義を読んでいたら、また素朴な疑問がわいた。(@_@;)

リストも同様に簡単に定義できます。リストの場合は再帰的になっているのが面白いですね。
data [a]               = [] | a : [a]                  -- more pseudo-code
… []は空リストであり、:はリストの中置構築子です。つまり、 [1,2,3]は1:2:3:[]と同等であるはずです。(:は右結合性をもちます。) [] の型は [a] で、 : の型は a->[a]->[a] です。

(2.4 組み込みの型は特別な型ではない より)

疑問は次の 3 つ。

• 要素が 0 の空リストってどんなイメージ？
• 要素がないのになぜリスト？
• なぜ空リストを想定しないとリストを定義できないの？

全て「空リスト」に関連している。

 

素朴に考える

リストと言われイメージするのは、要素が連なっているもののこと。

最初に、最小のリストについて考える。もし、リストの要件として、「要素が連なっている」ことが必須であるならば、最小の連なりは二つの要素。

これを代数的データ型で定義すると、

data List a = TwoElem a a

二つの要素を持つ List a 型の値を生成するには、

TwoElem 1 2

 

次に、3 つ以上の要素の連なりを表現するには再帰的な定義をする。

data List a = TwoElem a a
            | List (List a) a

3 つの要素を持つ List a 型の値を生成するには、

List (TwoElem 1 2) 3

4 つの要素の場合は、

List (List (TwoElem 1 2) 3) 4

 

見方を変える

ここで、リストを「要素の連なりである」という発想を忘れ、要素を入れる「入れ物」と考えるのであれば、要素が 1つ、要素が 0 の状態を想定したとしても不自然ではない。

data List a = TwoElem a a
            | List (List a) a
            | OneElem a
            | Empty

しかし、この定義は冗長。

なぜなら、リストに要素が一つの状態を表現するのに、

OneElem 1

と書けるけれど、

List Empty 1

で代用できる。よって、データコンストラクタ OneElem は必要ない。

同じように、リストに要素が二つある状態 TwoElem 1 2 は、

List (List Empty 1) 2

で代用できるので、データコンストラクタ TwoElem も不要。

結局残ったのは、

data List a = List (List a) a
            | Empty

上記の定義は、要素をリストの後ろに追加していくと解釈できる。要素をリストの後ろに追加していくことと、前に追加していくことは、リストの構造にとって本質的な意味を持たないので、以下のように定義したとしても同じ意味。

data List a = List a (List a)
            | Empty

以前書いたように、こちらの方が扱いが自然な感じがするので、多分この形になったのではないのかな？

 

関連サイト

• List (computing) - Wikipedia
• Recursive data type – Wikipedia
• Non-empty list - HaskellWiki

関連記事

• Haskell で関数の抽象化 - sum, product から foldl1 → foldl へ
• Python の空リストと再帰

再帰のイメージ

苦手な再帰をもう一度基本的なところから考えてみたい。 (+_+)

何でもイメージを浮かべないと考えることができない性質なので、「再帰的」に問題を解決できそうな雰囲気を感じたら、最近では心にあるイメージを浮べることにしている。再帰という抽象概念を `もの’ として手に触れることができる位置に置き、感触を確かめることによりやっと目の前の霧が少しずつ晴れていく。そんな契機になるように。

 

例

抽象的なイメージを考える前に、最初に次のような簡単な例を考える。

「1 から n までの自然数の合計を求めたい。」

 

考え方

このとき再帰的に関数を定義するなら、自分の場合、次のような手順で考える。

まずは、関数名を適当に `sum1to n’ と名付ける。

そして、 sum1to n を、とりあえず「1 から n までの自然数の合計」であると見なす。 (@_@) じぃ～。ただし、今はそれをどうやって定義すればいいのかわからない。

次に sum1to n なるものがあるとして、そこから見て小さい方へ目を向ける。例えば、sum1to n より一つだけ小さいものは 、

sum1to (n-1)

これは「1 から n-1 までの合計」を表わす。しかし、相変わらず sum1to n の定義はわからないし、当然ながら sum1to (n-1) もどうやって求めるのかわからない。 (+_+) ん～～

しかし、ここで上図を見ると、以下の二つが等しいことがわかる。 (@_@) おっ！

• sum1to n
• sum1to (n-1) に n を足したもの

別の言い方をするなら、sum1to (n-1) に n を足すと、sum1to n になるということ。

sum1to n = sum1to (n-1) + n

 

さて、これで求める定義はできたのだろうか？例えば「1 から 999 までの自然数の合計を求めたい」とする。このとき、上記の定義に当てはめれば、

sum1to 999 = sum1to (999-1) + 999

「sum1to 998 に 999 を足したものが sum1to 999」ということに。言い換えれば「1 ~ 998 の合計に 999 を足したもの」。では、「1 ~ 998 までの合計は？」と言ったら、1 ~ 997 までの合計に 998 を加えたもの。 「1 ~ 997 は？」 … といつまでたってもキリがない。つまり値が定まらない。

 

ところで、求めたいのは「1 から n までの自然数の合計」だった。例えば n が 1 のときはどうだろう？

「1 から 1 までの自然数の合計を求める」

これは考えるまでもなく明らかに 1 。なぜなら、一つのものを合計するのにそれ以上何か操作する必要がないため。そのものの値が求める答えに一致する。ということは、上記で定義した sum1to n = sum1to (n-1) + n を必要とすることなく、次のように定義することができる。

sum1to 1 = 1

これにより、例えば「1 から 2 までの自然数の合計を求める」場合の値が定まる。

sum1to 2 = sum (2-1) + 2
sum1to 2 = sum 1 + 2
sum1to 2 = 1 + 2
sum1to 2 = 3

この操作を 1 から順に繰り返していくことによって 999 まで辿り着けば、「1 から 999 までの自然数の合計」が求まる。

 

「基本コンポーネント」と「拡張する操作」

sum1to n の定義に戻る。

sum1to n = sum1to (n-1) + n

先ほどは、sum1to n が「何から構成されているか」という視点から定義を考えた。これを例えば、次のように書けるとしたら、(もちろん Haskell において文法エラーだけれど)

(sum1to n) - (sum1to (n-1)) =  + n

+ n の意味がより明確になる。つまり、これは sum1to n と sum1to (n-1) の違いが何に由来しているかを示している。上の例の場合、n を足すことにより両者の違いが生じる。また、それは n の値がどのように変化しても、その一つ前の n–1 の状態から、どのように変化すれば n の状態になれるのかを表現している。

ところで、n = 1 のときは上記の式を必要とせず、それのみで存立できる。たとえるなら、`1’ が核となり、それに衣を被せるようにして sum1to n は n ずつ大きく拡張されていく。つまり、sum (n-1) + n は sum1to が一回り大きくなる方法がについて書かれていると見なせる。

 

ここから再帰のイメージとして次のようなものが思い浮かんだ。

先ほどの例で言えば、「基本コンポーネント」に当たるのが `1’ で、これがある操作によってどんどんと拡張していくという構図。基本コンポーネントの周りにある線が拡張する様を表現。ある操作というのは、上の例の場合では n-1 の状態から n へと変化するための方法を表わし、具体的には一つ前の状態に n を加えることに相当する。

このように、中心に「基本コンポーネント」となるものがあり、それを「変化・拡張する操作」という二つのことを考えることによって、再帰的な構造をとらえることができる。

 

関数を定義をするときのポイント

とは言っても、相変わらず上手く関数を定義することができないのだけれど (+_+) 、現時点で重要だと思うポイントは 2 点ある。

1. 定義しようとする関数の意味を予めはっきりとさせておく。
2. 定義しようとしている途中でも、既に定義されていると仮定して、関数の適用をしてしまう。

(1) は、なんとなくぼんやりと関数を定義していると、それが何を表わしているかわからないため、再帰的な適用を考えることができなくなる。定義をする前に「これを適用すると、こういう結果になる」とはっきりとしたイメージを持っておくこと。ただし、定義の内容まで踏み込んで考えておく必要はない。

(2) は (1) が前提とされるが、関数を定義する際、「まだこの関数の定義は終ってないけれど、既に定義されたものと考えて、適用したらこういう結果になるはずだから…」というように、未完のものを既に完成されものと見なして関数を定義していくということ。

素朴にエラトステネスのふるい (2) - オブジェクト指向を手がかりに再帰表現を考える

「素朴にエラトステネスのふるい (1)」の続き。

コードを再掲。Haskell では、

sieve (p:ps) =
  p : sieve [n|n <- ps, n ‘mod‘ p /= 0]

Python だと、

def sieve(L):
    if not L: return []
    else:
        return [L[0]] + sieve([x for x in L[1:] if x % L[0] != 0])

やはり、今日見ても再帰的な表現はどこか理解しきれないと感じる。(+_+) これ以上考えてもらちが開かないので、このままの形で考えるのは諦めた。

 

ふるいの動作

ところで、上記のコードは直接素数を生成するわけではない。`ふるい’ はあくまでも素数を生成するためのツール。「2 からはじまる自然数のリスト」を与えたときに素数のリストが生成される。

main = do print $ take 10 $ sieve [2..]

print sieve(range(2,100))

もし、「1 からはじまる自然数のリスト」を引数に与えたなら、その `ふるい’ の性質上、生成されるのは [1] 。なぜなら、最初の「リストの先頭要素で割り切れる要素をふるいにかける」というところで、1 以降の要素が脱落してしまうため。つまり、上記のコードは `ふるい’ の動作を表現しているということを忘れてはダメ。素数が生成されるのはその結果に過ぎない。

 

ふるいのイメージ

よくわからないときは絵を描くことにしているので、素数を生成するときの `ふるい’ をイメージしてみた …

「このふるいは、近所の量販店で売られているふるいとは違う。小麦粉を `ふるう’ のではなく、「数値のリスト」をふるう。動作も一風変わっていて、数値のリストをザザーっと流し込むと、最初にふるいに落ちた数値がふるいにセットされ、その数値で『割り切れない数値』がふるいを通り抜け、割り切れた数値がふるいに残される。

ある数値のリストをこのふるいにかけたとする。直後、ふるわれた数値が地面に落ちる寸前、同じ種類のふるいを別にもう一つ用意し、落ちていく数値を受けとめる。同種のふるいなので動作も同じ。また落ちてきた先頭の要素がふるいにセットされ、残りの要素に対してふるいをかける基準となる。

手元にふるいが更に何個もあったので、これをどんどん繰り返していたら、最後には落ちていく数値がなくなってしまった。」

 

ふるいのふるまい

この様子を示したの右図。で、このふるいを一つのオブジェクトと見たて、ふるいクラスを作成する。まずはこのふるいに対して何ができるかという視点で。

• 数値のリストをセットする
• ふるいにかける

ここからふるいの内部はどうなっているかと想像すると、

• セットされた数値のリストを持つ
• セットされたリストの先頭要素を持つ

それから、右図のようにふるいをつなげて使っている様子をふるい自身に覚えてもらうことにすると、

• 自分がふるい落とした数値を受けとめるふるいを知っている

そして、各自ふるった後、落ちた数値を受け止めるためのふるいを自分で用意してもらうことに。

 

クラス図

 

実装

class Sieve:
    """ ふるい

    このクラスのオブジェクトが連なって働くことによって
    「エラトステネスのふるい」の振る舞いをする
    
    - 使い方
    1. インスタンスの生成
    2. 値の設定
    3. ふるいにかける
    """
    def __init__(self):
        self.L = []         # ふるいにかける前の数値のリスト
        self.head = None    # ふるいにかける数値のリストの先頭 (ふるいの基準)
        self.tail = None    # Sieve : ふるいにかけた後の数値のリストを保持

    def set(self,L):
        """ ふるいにかける数値のリストを設定 """
        self.L = L
        self.head = L[0]
        return self

    def sieve(self):
        """ ふるいにかける """
        self._sieveByHead()
        if self.tail:
            self.tail.sieve()

    def _sieveByHead(self):
        """ 設定されたリストの要素をその先頭要素で割り、
        割り切れなかったものをふるいから落とし、新たにふるいに設定する

        ※ 設定されたリストの要素が二つ以上ないと tail は None のまま。
        """
        if len(self.L) > 1:
            self.tail = Sieve()
            sieved = [x for x in self.L if x % self.head != 0]
            if sieved:
                self.tail.set(sieved)

    def __str__(self):
        """ ふるいの基準として使われた数値を出力 """
        if not self.head: return ""
        return str(self.head) + ", " + str(self.tail) if self.tail \
            else str(self.head)

s = Sieve().set(range(2,100))
s.sieve()
print s

最初に示したコードと比べるとかなり長くなってしまったが、こちらはイメージしやすい。 ^^ なぜかと言えば、クラス定義で意識するのはオブジェクト単位であり、オブジェクト一つで何ができるかを考えればいいため。sieve メソッドを見ると「自らふるい落とした数値のリストを受けとる`ふるい’」に対して sieve メソッドを呼出している。しかし、メソッドを見ても頭が混乱することはない。単純に `ふるい’ が `ふるい’ に対して 「sieve してくれ」と依頼しているようにしか見えないから。

結局、再帰的な関数において呼出す度に生成される文脈を、オブジェクトというイメージしやすい形に置き換えることにより理解しやすくなった気がする。オブジェクト指向で考えるときの一番基本的な戦略は、「オブジェクトと関わりのあるオブジェクトに対して、どのようにコラボレーションするか？」を問うこと。この方針が `考える範囲を限る’ ということに対して、`オブジェクト‘ という範囲の枠を提供してくれる。

再帰的な関数との違いがもう一つ。それは、やることを分割しているということ。上記のクラスでの実装は、「ふるいにかける動作、ふるう動作、ふるいを連ねる動作、その結果を表示するための動作」を別々にした。そして、それらの動作を `一つのふるい’ というイメージと関連付けて考えた。再帰的な関数では、これを一行で表現する。そうすると、自分の脳みそでは、「一体誰が何をしてその結果どうなったの？」というところで、えっ？(@_@;)？ となってしまう。

 

オブジェクト指向をアナロジーとして用いる

逆に言えば、再帰的な関数を、アナロジーとして上記のような表現とほぼ等価であると見なすことができれば、すんなりと理解できるはず…。明らかな動作の違いは、クラスによる実装では計算が終った時点で計算過程の一部の履歴が残っているのに対して、再帰関数では消えているという点くらいだし。… ということは、えーと、再帰関数である sieve を見たら、次のように見たてればいいということか。

1. 「sieve というメソッドを持つオブジェクト」があると想定。(ふるいに相当)
2. sieve を再帰的に呼出すところは、新しく同種のオブジェクトを生成すると見なす。
3. ただし、そのオブジェクトは最終的に計算の過程を保持することなく、計算の終了とともに消滅して結果 (関数の返り値) のみを残す。
4. 最後に、残された結果を連結。

つまり、関数で呼出された文脈をオブジェクトと見なし、そこで使われているローカル変数をインスタンス変数に見たてるということ。以前より少し理解が進んだような気になれた。 ^^

関連記事

• 素朴にエラトステネスのふるい (3) – Python の実装を Haskell へ

素朴にエラトステネスのふるい (1)

Haskell プログラミング ～ 純粋関数型言語への誘い～ を読んでいたら、「エラトステネスのふるい」 (p15) というのがあった。

sieve (p:ps) =
  p : sieve [n|n <- ps, n ‘mod‘ p /= 0]

Python で真似するなら、

def sieve(L):
    if not L: return []
    else:
        return [L[0]] + sieve([x for x in L[1:] if  x % L[0] != 0])

(ただし、L は有限のリスト)

 

素数

エラトステネスの篩 – Wikipedia によると、

素数判定法の一種で、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。

え～ (@_@;) 、こんなシンプルな表現で素数が得られるとは…。てゆうか「素数」なんて言葉何年ぶりに聞いただろうか。 ^^;

ところで、素数とは、

1とその数自身以外に正の約数がない（つまり1とその数以外のどんな自然数によっても割り切れない）、1 より大きな自然数のこと。

(素数 – Wikipedia より)

 

再帰的な定義

上記 sieve 関数は、定義の中で更に sieve 関数を適用している。苦手な再帰的な表現だ。うーむ。。。 (@_@;)

素数のリストが欲しいときは、2 以上の自然数のリストに関数を適用。これにより素数の無限リストが得られる。

primes = sieve [2..]  (同上より)

Python であれば、range(2,100) などのような有限のリストを sieve 関数に渡す。

 

部分的に考える

どのように動作するか具体的な例で考えてみる。例えば、「2 ~ 11 の自然数のリスト」に sieve 関数を適用した場合は、

sieve [2..11] = 2 : sieve [n|n <- [3..11], n `mod` 2 /= 0]

あ～  (+_+) 、再帰はいきなり見ると目が回るので部分ごとに。

まずは、リスト内包表記から。

[n|n <- [3..11], n `mod` 2 /= 0]

sieve 関数に適用したのは [2..11] のリスト。だから、ここでは「seive に適用したリストの先頭以外の要素」の中で「seive に適用したリストの先頭である 2」 で割り切れない要素をリストにしている。これが `ふるい’ にかける様子の一部を表現。

 

 

その後 `ふるい’ にかけたリストに対して更に sieve 関数を適用。ここが再帰的に関数を適用しているところで、目が回る原因。(@_@;)

sieve [n|n <- [3..11], n `mod` 2 /= 0]

言葉にすれば、

「ふるいにかける方法は、ふるいにかけたものを、更にふるいにかけること」

… と日本語にしたところで、再帰のイメージがしやすくなるわけではないか。 ^^;

 

混乱の原因

再帰の混乱の元は、再帰的に連なる呼出しをイメージしようとすることにある気がする。 (+_+) あくまでも考えるのは、連なる呼出し全体ではなく、そのスナップショット的な表現。例えば、上記のように sieve [2..11] と適用された場合、その適用された文脈でのみ動作を考える。再帰のそのまた先まで考えない。

 

具体的に、sieve[2..11] を定義するのであれば、定義は適用された引数 [2..11] に対してどのような作用をするのか考えるということ。あくまでも、一つ先の再帰を手持のコマで表現する。もう一度、以下を見ると、

sieve [n|n <- [3..11], n `mod` 2 /= 0]

再帰的に適用している対象  (リスト内包表記の中の変数) は、その文脈での「関数の適用対象」を使って表現している。

 

類似したパターン

定義の内容を続けて読んでいくと、次に、上記の再帰的な関数の適用によって生成されるリストと、先頭要素である `2’ をくっつけてリストを作成。ここでも同じく、 sieve の再帰的な適用の先の先は読まない。関数は「自分が欲しいものが既に得られた」と仮定し、「それを使ってどうしたいのか」という視点で考えると考えやすい。

2 : sieve [n|n <- [3..11], n `mod` 2 /= 0]

上記を言葉で表現するなら、

「ふるいにかける方法は、『ふるいにかけるリストの先頭』と『その先頭の要素では割り切れない要素に対して更にふるいをかけた結果』をつなげてリストにする。」

ポイントは、ふるいにかけられることによって「何」が残るのかということ。ここが自分はイメージしにくい。 (+_+) 関数が何を返し、それに対してどうしたいのか。再帰的な定義だと急に動作を想像しにくくなる気がする。

これを考えるには、関数の定義で再帰的に考えなくても明らかな部分に注目。上記の例ではリストの先頭要素である `2’ が手がかりとなる。

ところで、seive 関数の全体を眺めると、次のように再帰的に関数を適用している。

sieve リスト = リストの先頭要素 : sieve リストの先頭要素以外に対するリスト内包表記

こうやってみると全体の形が「n からはじまる数の無限リストを得る」再帰と類似しているのがわかる。

ints :: Int -> [Int]
ints n = n : ints (n+1)

ints 関数の実際の動作を考えると、例えば ints 1 なら、

1 : ints(2)
1 : 2 : ints(3)
1 : 2 : 3 : ints(4)
1 : 2 : 3 : 4 : ints(5)

再帰的に ints が適用されるごとに先頭要素がひねりだされ、前の要素にくっついていくという感じがする。適用されるごとに ints がリストを生長させているようにも見える。

sieve 関数も同様に見たてることができる。 sieve により適用されたリストの先頭がひねりだされ、リストが生長していく。再帰的に sieve 関数に適用されるリストによって、最終的に生成されるリストの内容が決定される。つまり、sieve に適用するリスト内包表記による操作がリストの要素を構成する決め手。このとき、最初にひねりだされるのが、リストの先頭要素である自明な `2’ 。

 

実際に確かめる

しかし、やはり実際に関数が定義と置き換えられていく様子を追ってみないと納得できない。 ^^;

2 : sieve [n|n <- [3..11], n `mod` 2 /= 0]
2 : sieve [3,5,7,9,11]
2 : 3 : sieve [n|n <- [5,7,9,11], n `mod` 3 /= 0]
2 : 3 : sieve [5,7,11]
2 : 3 : 5 : sieve [n|n <- [7,11], n `mod` 5 /= 0]
2 : 3 : 5 : sieve [7,11]
2 : 3 : 5 : 7 : sieve [n|n <- [11], n `mod` 7 /= 0]
2 : 3 : 5 : 7 : sieve [11]
2 : 3 : 5 : 7 : 11 : sieve [n|n <- [], n `mod` 11 /= 0]
2 : 3 : 5 : 7 : 11 : sieve []    -- ここで例外が発生

先ほど ints 関数を見たので、sieve 関数がリストの要素をゾロゾロと生み出しているように見える。 ^^;

ところで、上記では有限のリストに適用したので、例外が発生してしまった。

Prelude> sieve ([2..11])
[2,3,5,7,11*** Exception: :1:4-54: Non-exhaustive patterns in funct
ion sieve

例外が発生しないようにするには take 関数を使うか、

Prelude> take 5 $ sieve [2..]
[2,3,5,7,11]

空のリストに適用したときに空のリストを返すようにしておく。

sieve [] = []

 

Python で実装

さて、最初に Python におけるエラトステネスのふるいの実装例を挙げた。そこでは再帰的な定義をしたが、アルゴリズムとしては素朴な内容となっている。「素朴」である理由は、エラトステネスの篩 – Wikipedia のアルゴリズムの説明の中で、「ステップ 4」の一部の判定を省略しているため。

探索リストの最大値が素数リストの最大値の平方よりも小さい場合、素数リストおよび探索リストに残っている数が素数となる。

この判定をする理由については、「エラトステネスの篩い」の説明、「エラトステネスの篩いの原理」の「２．どの数の倍数を取り除くか」がわかりやすい。しかし、ここではこの判定を省略し、「素朴」に倍数を消す作業をリストの終りまで続けることにした。

 

ループを使って

はじめは、ごく普通に ループを使って実装してみる。

def sieveByHead(L):
    """ 先頭の要素で割り切れない要素のリストを返す """
    result = []
    for e in L[1:]:
        if e % L[0] != 0 :
            result.append(e)
    return result

def sieve(L):
    """ 渡されたリストの中の素数を返す """
    result = [L[0]]
    while L:
        sieved = sieveByHead(L)
        if sieved: result.append(sieved[0])
        L = sieved
    return result

print sieve(range(2,100)) 

 

上記の sieveByHead 関数をリスト内包表記で置きかえるとコンパクトになる。

def sieve(L):
    """ 渡されたリストの中の素数を返す """
    result = [L[0]]
    while L:
        sieved = [x for x in L if x % L[0] != 0]
        if sieved: result.append(sieved[0])
        L = sieved
    return result

 

ジェネレータを使って

最初に挙げた再帰的な表現だと、有限のリストにしか適用することができない。 Haskell のように無限リストを扱うには、ジェネレータで書き直す必要がある。

再掲すると、

def sieve(L):
    if not L: return []
    else:
        return [L[0]] + sieve([x for x in L[1:] if  x % L[0] != 0])

これをジェネレータに変更すると、

def sieve(L):
    head = L.next()
    yield head
    for e in sieve(x for x in L if x % head != 0):
        yield e

ジェネレータは next() の呼出しによって、対象となる要素が一つ先へ進む。ジェネレータを代入する変数 L をリストと見たてるなら、最初の next() の呼出しによって先頭の要素がなくなったとイメージするとわかりやすい。また、リスト内包表記を ジェネレータ式 で置き換えていることにも注意。

上記の関数を使うには、無限リストを生成する関数を定義して、その呼出し結果を sieve 関数に渡す。

def ints(n):
    """ n 以降の自然数の無限リスト """
    while True:
        yield n
        n += 1

primes = sieve(ints(2))
for i in range(10):
    print primes.next()

または、有限のリストであるなら、iter 関数を適用してから呼出す。

print list(sieve(iter(range(2,100))))

 

しかし…

ここまで来ても、再帰的な定義を見ると、やはりどこかイメージしきれないという感じがする。 ^^; 答えが得られた後もスッキリとしない。なぜだろう。 (+_+) 単に慣れていないのか、そもそも根本的にどこか理解の仕方が違うのだろうか？ わかっている人にとってみれば、「何を当り前のことを…」と思うのだろうけれど、その「当り前の考え方」が自分には感覚的に納得しきれないのでこだわってしまう。また、ツールとして再帰を利用することができない。

パタッ(o_ _)ｏ~†

もう一度別の角度からアプローチしていこう…。

Python のジェネレータ (5) - 再帰とジェネレータと Composite

Python のジェネレータ (4) - 無限リスト のつづき

1. 例

例えば、「リストの要素を 2 倍したい」とする。

リスト内包表記や map 関数を使うなら、以下のように書ける。

L = [1,2,3,4,5]

print [x*2 for x in L]
print map(lambda e: e*2, L)

 

2. for ループ

単純に、for ループでリストを走査しながら、要素を2 倍するなら、

def double(L):
    result = []
    for e in L:
        result.append(e*2)
    return result

print double(L)

これをジェネレータで置き換える。

def gDouble(L):
    for e in L:
        yield e * 2

for e in gDouble(L):
    print e

 

3. 再帰

再帰で書くと、

def rDouble(L):
    if not L: return []
    else:
        return [L[0]*2] + rDouble(L[1:])

print rDouble(L)

これをジェネレータで置き換えてみる。ジェネレータは要素をいっぺんに返さず、処理した要素ごとに返すようにする。

def grDouble(L):
    if not L: return
    else:
        yield L[0]*2
        for g in grDouble(L[1:]):
            yield g

for e in grDouble(L):
    print e

ジェネレータを再帰的に呼出すには、再帰的に適用したい部分を for に投入し (next() が呼出されるため)、その要素を yield で返す。渡された引数 L の要素がなければ、何もせず return でジェネレータを終了する。

次のように書き直すこともできる。

def grDouble(L):
    if L:
        yield L[0]*2
        for g in grDouble(L[1:]):
            yield g

 

4. Composite

ジェネレータを再帰的に呼出すことに、何かメリットがあるのだろうか？

ツリー状のノードの要素を走査するためにジェネレータが使われている例 を目にした。これを見ると、Iterator パターン 、Visitor パターン を連想する。

試しに、Composite パターン のオブジェクトに対して、その要素を走査する関数をジェネレータで定義してみる。

Composite パターン - Wikipedia via kwout

class Component:
    pass

class Composite(Component):
    def __init__(self):
        self.components = []
    def add(self, component):
        self.components.append(component)
        return self
    def __iter__(self):
        return iter(self.components)

class Leaf(Component):
    def __init__(self, val):
        self.val = val

def gComposite(composite):
    if isinstance(composite, Leaf):
        yield composite.val
    else:
        for c in composite:
            for g in gComposite(c):
                yield g

c = Composite().add(
        Leaf(100)).add(
        Leaf(200)).add(
        Composite().add(
            Leaf(1000)).add(
            Composite().add(
                Leaf(10000)).add(
            Leaf(2000))).add(
        Leaf(300)))

for e in gComposite(c):
    print e

Composite クラスの __iter__() メソッドの定義については、Python のイテレータ (3) を参照。

Haskell でパスカルの三角形

何か再帰的な問題はないかと思って、一つ思い出した。「確率のはなし」(p.78) の中にでてきた「パスカルの三角形」。高校の数学の授業でちらっと目にした覚えが。(@_@;)

パスカルの三角形 – Wikipedia によると、

この三角形の作り方は単純なルールに基づいている。まず最上段に1を配置する。それより下の行はその位置の右上の数と左上の数の和を配置する。例えば、5段目の左から2番目には、左上の1と右上の3の合計である4が入る。

パスカルの三角形 - Wikipedia via kwout

 

方法を考える

それぞれの段の「数のリスト」を得たいと考えたとき、どうやって実装すればいいのだろうか？まずは、要素の少ないものから並べて順に考えていく。

• 1 → [1]
• 2 → [1,1]
• 3 → [1,2,1]
• 4 → [1,3,3,1]

うーん、、、(@_@;)

上記のように「段数」を表わす数値を渡したら、リストが返ってくる関数の名前を pascal と名付け、とりあえず外観だけを書くと、

pascal :: Int -> [Int]

 

自明な要素

再帰的な定義の必要のない自明なところからはじめる。段数は最初を 0 段と数えることにして、

pascal 0 = [1]
pascal 1 = [1,1]

問題はここから。何をどうやって再帰的な関数の呼出しの構造にするのだろうか… ^^;

 

再帰的な定義

再帰的な構造を考える際のポイントは、「現在 (対象) の構造を、一つ前の構造からどのようにして導くことができるのか？」をチェックすること。例えば、今「1, 4, 6, 4, 1」を見ているとしたら、一つ前の「1, 3, 3, 1」をながめる。

• 1, 3, 3, 1
• 1, 4, 6, 4, 1

「1, 4, 6, 4, 1」 は、1 と 1 で [4, 6, 4]  がサンドイッチにされたリストと見ることができる。そして、[4, 6, 4] は、一つ前の [1, 3, 3, 1] から何らかの操作をすることによって作ることができるリスト。「何らかの操作」というのは、以下の部分に限って言えば、

• [1, 3, 3, 1]
• [4, 6, 4]

i 番目の要素を得るのに、前のリストの i 番目と i+1 番目の要素を足し合わせること。

上記のリスト全体に戻って考えると、4 段目 (一番を 0 段と数えた場合) の i 番目の要素は、 3段目の i-1 番目の要素と i 番目を足したもの。ただし、`1’ でサンドイッチされた部分についてのみの話。

これを一般的に言えば、n 段目の i 番目の要素は、pascal (n-1) の i-1 と i 番目を足したものということ。「ただし」以降の記述は上記と同じ。

あ～、とは言ったものの、これをどうやって実装するのだろう…。頭の中が混乱してきた。(@_@;)

 

Haskell で実装

リストの隣り合った要素を足す関数

一つ一つ別腹で考えることに。名前は、take2sum とでも付けることにして、まずははじめに取り上げた、前の段の要素を足してく関数について考える。

• [1, 1] → [2]
• [1, 2, 1] → [3, 3]
• [1, 3, 3, 1] → [4, 6, 4]

これは特に今回に限ったものでなくて、一般的に数値のリストが与えられたときの話として考えると、例えば、

• [1, 2, 3, 4, 5] → [3, 5, 7, 9]

これの最も単純なケースは、上記に書いたように二つの要素のリストが与えられたとき。つまり、

• [x, y] → [x+y]

要素が一つのリストの場合は、空を返しておくとして、問題は 3 つ以上要素が与えられた場合。しかし、これも単純に

• 先頭の要素を取り出し、残りの要素の先頭と足す。
• 先頭の要素以外は、再帰的に関数を適用。

と考えれば、次のように書ける。

take2sum (x:xs) = (x + head xs) : take2sum xs

 

上記は、二つの要素を与えた場合でも、「要素が一つのとき空を返す」ようにしておけば、

take2sum [1,2]
take2sum (1:2) = (1 + head 2) : take2sum [2]
take2sum (1:2) = 3 : []
take2sum (1:2) = 3

というように計算が進められ、結局、要素が二つの場合の定義を書かなくても済む。

リストの末尾には空リストがあるので、イメージとしては要素が二つのときは 3 つの要素を対象にしているような想像をするのがいいのかもしれない。自分の場合は、最初に理解しやすいように、

take2sum [x,y] = [x+y]

の定義を書いておき、take2sum (x:xs) を定義した後に削除するようにしている。すぐには再帰のイメージができないので… ^^;

 

pascal 関数

次に、上記の関数を利用して pascal 関数を完成させる。n が 1, 2 の場合は先ほど書いたので、3 以上について考えると、

サンドイッチの中身は、一つ前の pascal 関数に、take2sum を適用した結果なので、

pascal n = [1] ++ take2sum (pascal (n-1)) ++ [1]

両端を [1] でサンドイッチし、中身は一つ前の pascal 関数を呼出し、それに先ほどの take2sum 関数を適用。上記によって、これも n = 2 の場合を兼ねることができている。計算の過程を追ってみると、

pascal 1 = [1] ++ take2sum(pascal 0) ++ [1]
pascal 1 = [1] ++ take2sum([1]) ++ [1]
pascal 1 = [1] ++ [] ++ [1]
pascal 1 = [1,1]

 

完成

全体を示す。

pascal :: Int -> [Int]
pascal 0 = [1]
pascal n = [1] ++ take2sum (pascal (n-1)) ++ [1]

take2sum :: Num a => [a] -> [a]
take2sum [x] = []
take2sum (x:xs) = (x + head xs) : take2sum xs

main = print $ pascal 4

実行すると結果は、

[1,4,6,4,1]

 

別解

take2sum 関数のところは、zip とリスト内包表記を使っても書けるので、

pascal :: Int -> [Int]
pascal 0 = [1]
pascal n = [1] ++ take2sum (pascal (n-1)) ++ [1]
    where
      take2sum xs = [x+y | (x,y) <- zip xs (tail xs)]

main = print $ pascal 10

この場合、take2sum の引数に渡される型が pascal 関数の引数の型が指定してあることより、[Int] であるはずなので、関数の型は書かなくてもいいかな。

上記を実行した結果は、

[1,10,45,120,210,252,210,120,45,10,1]

パスカルの三角形 – Wikipedia と見比べてみると、ちゃんと計算できているようだ。 ^^

 

無名関数を使って

take2sum なんて名前を消したければ、無名関数を使って、

pascal :: Int -> [Int]
pascal 0 = [1]
pascal n = [1] ++ 
           (\xs -> [x+y | (x,y) <- zip xs (tail xs)]) (pascal (n-1)) 
           ++ [1]

うーん、これは… (@_@;)

 

Python で実装

せっかくなので Python でも実装してみる。上記のリスト内包表記を使った方を真似すると、

def take2sum(xs):
    return [x+y for x,y in zip(xs, xs[1:])]
    
def pascal(n):
    if n == 0: return [1]
    else:
        return [1] + take2sum(pascal(n-1)) + [1]

print pascal(10)

 

無名関数を使うと、

def pascal(n):
    if n == 0: return [1]
    else:
        return [1] + \
               (lambda xs:[x+y for x,y in zip(xs, xs[1:])])(pascal(n-1)) \
               + [1]

うーん… ^^;

 

Ruby で実装

Haskell, Python と違い、Ruby の zip は相手がいない場合、nil をくっつけるので nil? のチェックが必要。(cf. Python の zip と map の違い)

def take2sum(xs)
  result = []
  xs.zip(xs[1..xs.length-1]) do |ary|
    result << ary[0]+ary[1] unless ary.any?{|e| e.nil?}
  end
  result
end

def pascal(n)
  if n == 0 
    [1]
  else
    [1] + take2sum(pascal(n-1)) + [1]
  end
end

p pascal(10)

Python でネストしたリストから Composite パターンを生成

「Python でリストに対する再帰的な関数の適用」では、ネストしたリストに対して、リストのまま関数を適用した。今回はネストしたリストから Composite パターンとなるようにオブジェクトを生成してみる。 Composite にしておけば、後々の操作がしやすくなるかな。

 

Composite パターン

リストを、オブジェクトを使って次のような構造へ変換する。とりあえず、リスト → オブジェクトへの変換だけなので、要素に相当するクラスは作らない。リストを表わす List クラス、値を表わす Value クラスのみを作成。要素クラスは、List, Value に共通の操作が必要になったときに作成することに。

 

まずは、List と Value クラス。

class List:
    BRACKETS = "<>"

    def __init__(self):
        self.elems = []

    def add(self, elem):
        self.elems.append(elem);
        return self

    def __str__(self):
        return List.BRACKETS[0] + \
               ",".join(str(e) for e in self.elems) + \
               List.BRACKETS[1]

    def __iter__(self):
        return iter(self.elems)

class Value:
    def __init__(self, val):
        self.val = val

    def __str__(self):
        return str(self.val)

( cf. Python のイテレータ, Python のイテレータ (3) )

 

Composite を生成する関数

リストからオブジェクトを生成する関数は、前回の再帰的な関数を真似る。

1. 渡されたリストがリストであれば、要素に対して再帰的に生成関数を適用する。
2. 値であれば、 Value クラスを作成。

def createList(L):
    if isinstance(L, list):
        newList = List()
        for e in L:
            newList.add(createList(e))
        return newList
    else:
        return Value(L)

 

List クラスに要素を追加するメソッドは、最後に自身を返すようにしているので、reduce で書換えることができる。

def createList(L):
    if isinstance(L, list):
        return reduce(lambda a,b: a.add(createList(b)), L, List())
    else:
        return Value(L)

print createList([1,2,[21,22,[231],24,1],2,3,4,5])

上記を実行した結果は、

<1,2,<21,22,<231>,24,1>,2,3,4,5>

Python でリストに対する再帰的な関数の適用

1. リストに対する再帰的な考え方のポイント

リストに対して、再帰的な関数を適用する場合、次の二つの視点を頭に入れておく。

1. 先頭要素と、それ以外の残りのリスト。
2. リストは要素として、リスト、または、値を持つ。

 

2. フラットなリストに対する再帰的な処理

ネストのないフラットなリストに対して適用する関数を考える場合、

1. 先頭要素
2. 先頭要素以外の残りの要素

に分けて考える。先頭要素に適用した場合の処理と、それ以外の要素を含むリストに対して、再帰的に関数を適用するように記述する。

何もしない関数

一気に考えると脳みその容量をオーバーするので段階的に考える。 (+_+)

まず、フラットなリスト L を受けとったら、そのまま返す関数 map1 を考える。

L = [1,2,3,4,5]

ただし、そのまま返すと言っても、関数を再帰的に適用する。

実装を考えるとき、

1. 空のリストが渡されたら、空のリストを返す。
2. リストの先頭要素と、それ以外の残りの要素に再帰的に関数を適用したものを結合する。

def map1(L):
    if L == []:
        return []
    else:
        return [L[0]] + map1(L[1:])

print map1(L)

先頭の要素を取り出した後、後続のリストと結合するため、要素を「要素一つのリスト」にする。

 

関数を適用する関数

次に、リストの各要素に関数を適用する関数に変更する。

引数として要素に適用する関数 f を追加する。

def map1(f,L):
    if L == []:
        return []
    else:
        return [f(L[0])] + map1(f,L[1:])
    
print map1(lambda x: x*2, L)

これで組込みの map 関数のような動作の関数ができた。

 

3. ネストのあるリスト

ネストのあるリスト L の場合を考える。

このとき、リストは Compositeパターン になっていると見なせる。このようなリストに対する関数は、リストと値の場合に分けて考える。リストのときは、その要素に再帰的に関数を適用する。

L = [1,[21,22],3,[41,[421,422],43,44],5]

何もしない関数

リストを受けとったら、何もしないで返す関数 map2 を定義する。

def map2(L):
    if isinstance(L, list):
        if L == []:
            return []
        else:
            return [map2(L[0])] + map2(L[1:])
    else:
        return L

print map2(L)

最初に、対象がリストであるか、値であるか判定をしてから処理を進める。

1. 値であれば、それをそのまま返す。
2. リストの場合は、先ほどのフラットなリストと同じ処理を行う。ただし、今回は、取り出した先頭の要素が値ではなく、リストである可能性もあるので、それに対して再帰的に関数を適用する。

 

関数を適用する関数

上記の関数を、リストの各要素に適用する関数を引数として受けとるように変更する。

def map2(f,L):
    if isinstance(L, list):
        if L == []:
            return []
        else:
            return [map2(f,L[0])] + map2(f,L[1:])
    else:
        return f(L)

print map2(lambda x: x*2, L)

上記を実行した結果、ネストしたリストにも関数が適用されるようになった。

[2, [42, 44], 6, [82, [842, 844], 86, 88], 10]

 

再帰処理において map を使う

map2 関数の再帰処理はごちゃごちゃしている。 (+_+)

リストである場合の処理において、組込みの map 関数を利用して再帰的に関数を適用してみる。一気に変更するとわからなくなるので、まずは何もしない関数 map2b を定義。

def map2b(L):
    if isinstance(L, list):
        result = []
        for e in L:
            result += [map2b(e)]
        return result
    else:
        return L

こちらの方がコードがシンプルで読みやすい。

同じように、要素に関数を適用できるように変更する。

def map2b(f,L):
    if isinstance(L, list):
        result = []
        for e in L:
            result += [map2b(f,e)]
        return result
    else:
        return f(L)

print map2b(lambda x: x*2, L)

折角なので map で書き直してみる。

• cf. Python の map, filter, reduce とリスト内包表記

def map2b(f,L):
    if isinstance(L, list):
        return map(lambda x: map2b(f,x), L)
    else:
        return f(L)

reduce で書くなら、map の部分を以下のように書ける。

return reduce(lambda a,b: a+[map2b(f,b)], L, [])

 

関連記事

• ループと再帰
• 複利の計算

Python のジェネレータ (3) - 数字にコンマを振る

Python のジェネレータ (2) のつづき

1. ジェネレータを使う方法

前回と同じく、ジェネレータを使う例を考える。

• 数字にコンマを振る (via 巡回 - 常山日記)

Python のチュートリアル 5.5.7 レシピ に、moneyfmt() という関数が書かれている。とりあえず、これは横に置いておく。

「数字にコンマを振る」ために、ジェネレータを使うことをイメージする。

1. 数をリストに見たて、末尾から 3 つずつ要素を返すジェネレータを作成。
2. そのジェネレータからリストを生成し、
3. 要素を逆順にして、
4. 最後にコンマで要素をくっつける。

実装。

def gCommaStr(num):
    result = ""
    for i,e in enumerate(reversed(str(num))):
        if not i == 0 and i % 3 == 0:
            yield result
            result = ""
        result = e + result
    yield result

print ",".join(list(reversed([x for x in gCommaStr(1234567890)])))

一応、コンマを打つ位置を可変にしておくと、

def gCommaStr2(num,n):
    result = ""
    for i,e in enumerate(reversed(str(num))):
        if not i == 0 and i % n == 0:
            yield result
            result = ""
        result = e + result
    yield result

print ",".join(list(reversed([x for x in gCommaStr2(1234567890,3)])))

 

2. 再帰を使った方法

リスト操作なので、ついでに再帰の練習もしておこう。

数が小さいときは、

1 --> 1
12 --> 12
123 --> 123

そのまま返す。

コンマがつけられる最小の数値のリストは、

1234 --> 1,234

これが再帰をするときの基本的なコンポーネントになりそうだ。

続きを考えると、

12345 --> 12,345
123456 --> 123,456
1234567 --> 1,234,567
12345678 --> 12,345,678

ぼ～っとながめていると、何となく繰返しになっている構造が見えてくる。 (@_@;) 上記の最後のパターンを見ていたら、 「2,345」 と 「5,678」 というように分割して考えれば、先ほど考えた基本的なコンポーネントが結合した形と見ることができることに気がついた。  「5」  が重複しているが、これは再帰呼出しの後に削除すればいいような感じ。 「12345」 なら、 「12」 と 「2,345」 。 「123456」 なら、 「123」 と 「3,456」 というような部分に分割できると考える。

これで数値が大きくなっても、基本的なコンポーネントとそれ以外の部分に分けて考え、関数を再帰的に適用すればいいような気がしてきた。

さて、実装～ (+_+)

def recCommaStr(L):
    if len(L) <= 3:
        return L
    elif len(L) == 4:
        L.insert(1, ","); return L
    else:
        return recCommaStr(L[:-3])[:-1] + recCommaStr(L[-4:])

num = 1234567890
print "recCommaStr(L): " + "".join(recCommaStr(list(str(num))))

引数 L は、数値を文字列にした後、リストにしたものを渡すようにした。

何も知らずにこのコードを見たら、読む気が失せるけれど ^^; 、わかっていれば再帰的な実装はやり方を素直に実装しているように感じる。

これも同じくコンマが打たれる位置を指定できるように拡張すると、

def recCommaStr2(L,i):
    if len(L) <= i:
        return L
    elif len(L) == i+1:
        L.insert(1, ","); return L
    else:
        return recCommaStr2(L[:-i],i)[:-1] + recCommaStr2(L[-(i+1):],i)

num = 1234567890
print "recCommaStr2(L,i): " + "".join(recCommaStr2(list(str(num)),3))

引数 i がコンマの位置を現わす。

 

3. 割り算で分割する方法

あ～、そうだ。数値を 1000 で割っていけば、コンマの打ちたい分の数値だけ取得できるかぁ。

def divCommaStr(num):
    result = str(num) if num < 1000 else ""
    while num > 1000:
        result = "," + str(num % 1000) + result
        num /= 1000
        if num < 1000:
            result = str(num) + result
    return result

print "divCommaStr(1234567890): " + divCommaStr(1234567890)

あれ？何かややこしい。 (+_+) こういうの考えるの苦手。脳みそ混乱してきた。 パタッ(o_ _)ｏ~†

 

コンマの位置を可変にすると、

def divCommaStr2(num, i):
    assert i > 0
    divNum = 10 ** i
    if num < divNum: return str(num)

    result = ""
    while num > divNum:
        result = "," + str(num % divNum) + result
        num /= divNum
        if num < divNum:
            result = str(num) + result
    return result


print "divCommaStr2(1234567890, 3): " + divCommaStr2(1234567890, 3)

 

4. クラスを使った方法

クラスを使って実装してみる。コンマ付きの数字を表わす CommaStr クラスを作成。コンマを付けるのは、文字列としてオブジェクトの情報を出力するときに、末尾から数値を 3 つ置きに走査する時点でつけることにした。

class CommaStr:
    def __init__(self, num, i):
        self.i = i
        self.nums = str(num)
            
    def __str__(self):
        result = ""
        for i,e in enumerate(reversed(self.nums)):
            if not i == 0 and i % self.i == 0:
                result = e + "," + result
            else:
                result = e + result
        return result

print "CommaStr(1234567890, 3):", CommaStr(1234567890, 3)

これだとクラスを使う意味があまりないなぁ。 ^^; グローバル変数と関数を組み合わせる方法と大差なし。でも、クラスで考えるというのは何となくイメージしやすい。

 

自分の好みとしては、同様にコンマ付きの数字全体を CommaStr クラスで表わし、各数字を Num クラスとする。 Num クラスには、インスタンス変数として数値とコンマをつけることができるフィールドを用意しておく。

実装。

class CommaStr2:
    def __init__(self, num, i):
        self.i = i
        self._createNums(num)

    def _createNums(self, num):
        self.nums = []
        for e in str(num):
            self.nums.append(Num(e))
        self.setComma(",")
            
    def setComma(self, comma):
        for i,e in enumerate(reversed(self.nums)):
            if not i == 0 and i % self.i == 0:
                e.comma = comma

    def __str__(self):
        return "".join(str(x) for x in self.nums)

class Num:
    def __init__(self, num, comma=""):
        self.num = num
        self.comma = comma
    
    def __str__(self):
        return str(self.num) + self.comma

print "CommaStr2(1234567890, 3):", CommaStr2(1234567890, 3)

全体は長くて効率も悪いけれど、全体の構造の見通しがよく、各メソッドはシンプルでええわぁ～。 ^^

Python のジェネレータ (4) - 無限リスト につづく…

Python のジェネレータ (2) - リストの走査

Python のジェネレータ (1) - 動作を試す のつづき

1. ジェネレータをどこで使うのか？

ジェネレータの動作について、何となく雰囲気を理解できた。しかし、どのような目的に使うのか、今一分からない

「あ！これはジェネレータを使うと、問題を解くのが楽だ。」

「ジェネレータを使った方がシンプルに書ける」

ということが分かるようになりたい。

 

イテレータを置き換えるジェネレータ

最初に覚えたことは、

ジェネレータを使うと、イテレータを簡単に作成できる。

ということ。イテレータとは、複数のオブジェクトに対して、要素を一つづつ辿るための手段。よって、ジェネレータは、複数の要素を辿るために利用できる。

例えば、Group クラスが Person クラスに対して責務があるとする。イテレータを自前で実装するには、境界条件を考えながら、イテレータプロトコルに沿うようにする。

• Python のイテレータ

自前で実装したイテレータは、ジェネレータで置き換えることができる。

• Python のイテレータ (3)

イテレータを自前で実装することと比べると、ジェネレータを使った方がシンプルに書ける。

 

2. ジェネレータを使い、リストを走査する例

ジェネレータを使うことができる例を挙げる。

• Pythonのenumerateでハマった - ponkan lab (via 巡回 - 常山日記)

には、「リストの各々の要素に対して、右隣の要素との差をリストとして返す」処理の例が書かれている。

>>> a = [0,1,2,3,4,5] (略)

… 一つ前の要素との差を求めたかった。a[1]とa[0]の差は1といった感じで、a=[0,1,1,1,1,1]になって欲しい。0番目は何もしない。

ジェネレータを使わずに定義するなら、

def sa(ary):
    result = []
    for x in zip(ary[:-1], ary[1:]):
        result.append(x[1] - x[0])
    return result

def sa_wrapper(ary):
    return ary[:1] + sa(ary)
    
print sa_wrapper([0,1,2,3,4,5])

関数 sa をリスト内包表記で置き換えると、

def sa(ary):
    return [b-a for a, b in zip(ary[:-1], ary[1:])]

この問題に対して、ジェネレータを使ってみる。

最初に、ジェネレータを利用したときのイメージを考える。

1. 対象のリストの要素に対して、0 番目と 1 番目の要素から走査するジェネレータを2つ想定する。
2. 各々のジェネレータから要素を順に取り出し、関数 zip でジェネレータ g1 から取り出した値を g2 から引いた値をリストにする。
3. 最後に、元の先頭の要素を求めるリストの先頭にくっつける。

ジェネレータを使わない場合、

ary[:-1], ary[1:]

のようにして部分リストを取得する。この処理をジェネレータで置き換える。

def gen(ary, i):
    u""" リストの i 番目の要素から走査するジェネレータ """
    for e in range(i, len(ary)):
        yield ary[e]

a = [0,1,2,3,4]
print [a[0]] + [a-b for a,b in zip(gen(a,1), gen(a,0))]

 

ジェネレータを使うメリット

ジェネレータは、イテレータのように要素を1つずつ取り出しては処理を行う。そのため、ジェネレータを使うメリットは、

ary[:-1], ary[1:]

のように部分リストを完全に取得する必要がないこと。もし、対象のリストがとても長く、

「要素を検査した結果、すぐに値を返す」

というような処理が含まれる場合、効率的に計算が行われる。

 

3. 再帰的な処理で置き換える

以下、ジェネレータとは関係がない。上記の例を再帰的な処理で置き換えてみる。

1. 空のリストが来たとすると、そのまま返す。
2. 要素が一つの場合も、何もせずにそのまま返す。
3. 要素が二つのときは、2 番目の要素から先頭の要素を引いた値をリストにして返す。
4. 要素が三つ以上のときは、同様に2 番目の要素から先頭の要素を引いた値をリストにしたものと、2 番目以降の要素を再帰的に呼出した結果のリストと結合して返す。

def rec(ary):
    if len(ary) <= 1:
        return ary
    elif len(ary) == 2:
        return [ary[1] - ary[0]]
    else:
        return [ary[1] - ary[0]] + rec(ary[1:])
    
def rec_wrapper(ary):
    if ary == [] or len(ary) == 1: return ary
    return [ary[0]] + rec(ary)

a = [0,1,2,3,4]
print rec_wrapper(a)

先頭の要素を、リストの先頭に持ってくる処理も再帰呼出しの中に含めるように変更する。

def rec2(ary):
    if len(ary) <= 1:
        return ary
    elif len(ary) == 2:
        return [ary[0]] + [ary[1] - ary[0]]
    else:
        return rec2(ary[:-1]) + [ary[-1] - ary[-2]]

print rec2(a)

 

要素を指定できるようにする

上記では、ジェネレータを使って書いたときの柔軟さが失われている。

ジェネレータを使った書き方は、引数 i によって隣接する要素だけではなくて、i 個離れた隣の要素から引いた値のリストを返すことができる。上記の再帰関数も、同じように指定された i だけ隣の要素から引いたリストを返すように変更してみよう。

まずは、具体的な例で考える。例えば、i = 3 で、3 つ隣の要素から各要素を引いた値のリストを得る場合。このとき、リストが返されるために、元になるリストは少なくとも 要素を 4 つ持っていないといけない。 要素が 3 つ以下であれば、何せずに元のリストをそのまま返すとする。逆に 5 つ以上であれば関数を再帰的に適用する。

これを一般的に書くならば、

1. 引数 i + 1 と、リストの大きさが同じ場合、 i 番目の要素から先頭の要素を引いた値をリストにして返す。
2. 引数 i  >= リストの大きさであれば、何せずにそのまま返す。
3. それ以外のときは、再帰的に関数を適用

def rec3(ary,i):
    if len(ary) <= i:
        return ary
    elif len(ary) == i+1:
        return [ary[i] - ary[0]]
    else:
        return [ary[i] - ary[0]] + rec3(ary[1:],i)

def rec_wrapper3(ary,i):
    if len(ary) <= i: return ary
    return [ary[0]] + rec3(ary,i)

print rec_wrapper3(a,1)

同じように関数 rec2 も変更してみる。

def rec4(ary,i):
    if len(ary) <= i:
        return ary
    elif len(ary) == i+1:
        return [ary[0]] + [ary[i] - ary[0]]
    else:
        return rec4(ary[:-1],i) + [ary[-1] - ary[-1-i]]

print rec4(a,1)

シンプルに見えるけど、見直してもすぐに理解できなくなってしまった。 パタッ(o_ _)ｏ~†

 

処理を分割する

上記の定義は複雑すぎる。理由は、処理が適切に分割されていないため。

行なっている処理は、２つに分かれている。

1. リストの各々の要素に対して、右隣の要素との差をリストとして返す。
2. 対象の先頭要素を、結果の先頭に追加する。

予め Haskell で書いてみる。

sa (x:[])   = []
sa (x:y:xs) = y-x : sa (y:xs)

sa_wrapper xs | length xs <= 1 = xs
              | otherwise      = head xs : sa xs

Python で書きなおすと、

def sa(ary):
    if len(ary) <= 1: return []
    else: return [ary[1]-ary[0]] + sa(ary[1:])

def sa_wrapper(ary):
    if len(ary) <= 1: return ary
    else: return ary[:1] + sa(ary)

これで読みやすくなった。

Python のジェネレータ (3) につづく…

ループと再帰

1. 再帰的な考え方は難しい

どこで見たのか失念してしまったが (+_+) 、以下のような主旨を読んだ覚えがある。

構造化プログラミングでは、「順次、反復、分岐」が導入された。この内、「分岐」は「多態」に置き換えることができ、「反復」は再帰により表現することができる。「順次、反復、分岐」というプログラムの基本構造は、別の表現へと解体されていく。

当時、オブジェクト指向にベッタリだった。そのため、「多態」バンザイと思ったが、「再帰」に関しては苦手だった。最近、関数型の言語を触るようになった。「順次」は、モナドで置きかけることができるのかな？

プログラミングの本を読んでいると、

「再帰」

の考え方は重要だと述べられている。プログラミングの勉強をはじめたとき、一番最初につまずいたのが再帰だった。自分は、文系でフィーリング重視の脳みそ。再帰ほど、想像力に負荷をかけるものはない。 (@_@;)

定義しようとしているものを、定義しようとしているもので定義する

という意味も、その感覚も想像出来なかった。

再帰的に定義された関数に、実例を当てはめ、計算を順に追っていけば、確かに計算したいことが実現できていることを確認できる。しかし、計算を終えると、どこか狐につままれたような気分になるのが、再帰的な関数の定義。

自分で再帰的な関数を定義しようと思っても、考えるとっかかりがどこにあるのか分からない。突然迷路に投げだされ、どちらに行けばいいのかわからない感覚。いやむしろ、迷路の構造そのものが全く見えない。

Haskell を学んで良かったと思うことは、再帰を考えるための環境が整っていること。ループのための構文が用意されていないこと。関数定義において、引数のデータコンストラクタによるパターンマッチ (x:xs) があること。リスト操作において、関数 head , tail による再帰構造へと導く関数があること。これらにより、再帰的な考え方になじんでいく。

命令型のプログラミングだけではなく、関数型のプログラミングにも最初から親しんでおけば、再帰の考え方に抵抗を感じることがなかった。

 

2. for ループを再帰で置き換える

例えば、Ruby で

「数値の配列の要素を 2 倍して出力する」

場合、 for ループを使って書くと、

for i in [1,2,3,4,5]
  puts i * 2
end

再帰を使って定義するなら、

def rec_each(ary)
  return if ary.empty?
  puts ary[0] * 2
  rec_each(ary[1..ary.size-1])
end

rec_each [1,2,3,4,5]

これを書くためには、次の 2 点に意識を向ける必要がある。

1. 配列を「先頭の要素と、それよりも後ろの要素」という構造として見る
2. 配列の、最後の要素まで関数を適用した場合に、どうなるか？

再帰のわかりにくい理由は、コードにしたときの処理の流れと、人が頭で順次処理をしていくときの流れが、一致しないということにある。コードでは、最初に 2 番目の条件に着目しなければならない。

この2番目のことを、

「基底条件」

と言う。「再帰のときは、基底条件をまず書く」と覚えこんでおけば、コード書き出す契機と実際にはなる。

Python で同じ関数を書くなら、

def rec_each(ary):
    if ary == []: return
    print ary[0] * 2
    rec_each(ary[1:])

rec_each([1,2,3,4,5])

シーケンス操作において、 ary[1:] のように、先頭の要素以降を取得する書き方が簡潔でいい。

• cf. 2.3.6 シーケンス型 の注釈(4)

Ruby では ary[1..ary.size-1] のように書いたが、もっと簡単に書けるのだろうか？オープンクラスを使い、定義するのがいいかな。

• Ruby, JavaScript, Python で既存のクラスを拡張 - オープンクラス(モンキーパッチ) と Scala の暗黙の型変換

 

3. 配列に操作を適用する

上記を少し変更し、

「要素を変更した結果を、配列として返す」

には、どうすればいいだろうか。

ループを使って書くならば、

result = []
[1,2,3,4,5].each do |i|
  result << i * 2
end
p result

ついでに map, inject を使っても書いてみる。

p [1,2,3,4,5].map{|i| i * 2}
p [1,2,3,4,5].inject([]){|x,y| x + [y*2]}

再帰で書くと、

def rec_each2(ary)
  return [] if ary.empty?
  return [ary[0] * 2] + rec_each2(ary[1..ary.size-1])
end

注意する点は、要素を 2 倍にした後、要素を[ ] で囲って配列にすること。それから、対象の配列が空の場合 [ ] を返すこと。この辺り、最初、ややこしく感じた。 (+_+)

Haskell で書くなら、

each :: (Num a) => [a] -> [a]
each [] = []
each (x:xs) = x*2 : each xs

main = print $ each [1,2,3,4,5]

比較してみると、Haskell で再帰を書いた場合の可読性は高い。リストが空の場合と、そうでない場合を明確に分けている。引数におけるパターンマッチでは、先頭の要素とそれ以降の要素に分ける書き方が簡潔。

Python で書くなら、

def rec_each2(ary):
    if ary == []: return []
    return [ary[0] * 2] + rec_each2(ary[1:])

print rec_each2([1,2,3,4,5])

 

4. 総計を求める

次に、配列の合計を求める。

ループを使って書くならば、

result = 0
for i in [1,2,3,4,5]
  result += i
end
puts result

inject を使えばよりシンプルに書ける。

p [1,2,3,4,5].inject{|x,y| x+y}

これを再帰で書いてみる。

def rec_sum(ary)
  return 0 if ary.empty?
  return ary[0] + rec_sum(ary[1..ary.size-1])
end

今度は、要素に対する操作ではないので、先ほどのように先頭の要素を [ ] で囲まない。

Haskell なら、

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

Prelude に sum があったので、別名にした。

Python だと、

def rec_sum(ary):
    if ary == []: return 0
    return ary[0] + rec_sum(ary[1:])

print rec_sum([1,2,3,4,5])

 

5. 総乗を求める

配列の要素をすべて掛け合わせたものを計算したい。

総乗 – Wikipedia によると、

総乗（そうじょう）とは、積の定義される集合における 多項演算の一つで、元の列のすべての積をあらわしたものである。

「元の列」の `列’ の意味は、

数学において列（れつ、sequence）とは、対象あるいは事象が羅列されたものを順番に並べたものである。 (...)

列の各項が、数である列を数列、整数である列を整数列、多項式である列を多項式列といったように、「何々」の列を省略して「何々」列と呼ぶことは多い。適当な「文字」集合から作った列は文字列（string あるいは語 word）、ある空間の「点」の列を言うのであれば、点列である。

(列 (数学) – Wikipedia より)

「列 = シーケンス」ということは、Python では数学の列の概念に沿ってるということだろうか？

「文字の集合から作った列が文字列」

というのも、Python において、文字列は変更不可能なシーケンス型として扱われてことに対応する。

• cf. Python の シーケンス型に慣れる

そういえば、 Haskell も文字列が文字のリストだった。

type String = [Char]

(Prelude より)

話を元に戻し、要素を掛け合わせたものをループを使って書くと、

ary = [1,2,3,4,5]
result = ary[0]

for i in ary[1...ary.length]
  result *= i
end
puts result

再帰で書くと、

def prod(ary)
  return 0 if ary.empty?
  return ary[0] if ary.size == 1
  return ary[0] * prod(ary[1..ary.size-1])
end

puts prod([1,2,3,4,5])

Haskell なら、

prod :: (Num a) => [a] -> a
prod [] = 0
prod [x] = x
prod (x:xs) = x * prod xs

main = print $ prod [1,2,3,4,5]

Python なら、

def prod(ary):
    if ary == []: return 0
    if len(ary) == 1 : return ary[0]
    return ary[0] * prod(ary[1:])

print prod([1,2,3,4,5])

 

6. 階乗を求める

再帰の問題でおなじみの階乗もやっておく。

階乗 – Wikipedia によると、

階乗（かいじょう）とは、自然数 n に対し、1 から n までの自然数の総乗を言う。

今度は、要素を渡すのではなくて、自然数を渡す関数とする。

def fact(n)
  return 1 if n == 0
  return n * fact(n-1)
end

puts fact(5)

Haskell なら、

fact :: Int -> Int
fact 0 = 1
fact x = x * fact(x-1)

main = print $ fact 5

Python なら

def fact(n):
    if n == 0 : return 1
    return n * fact(n-1)

print fact(5)

 

7. これまでの計算を一般化する

総和、総乗の定義内容は、適用する演算子以外の部分はよく似ている。そこで、より一般化して、「演算子とリストを渡したら、累積的にそれを適用した結果を返す関数」を定義してみる。名前は適当に hoge とした。

hoge :: (Num a) => (a -> a -> a) -> [a] -> a
hoge _ [] = 0
hoge _ [x] = x
hoge f (x:xs) = x `f` (hoge f xs)

main = print $ hoge (-) [1,2,3,4,5]

そういえば、これは前回やった foldl によく似ている。初期値を与えていないところが違うけれど。

Haskell だと、こういう一般化をするときに書きやすい。

Python で書くと、

def hoge(ary, f):
    if ary == []: return 0
    if len(ary) == 1: return ary[0]
    return f(ary[0], hoge(ary[1:], f))

print hoge([1,2,3,4,5], lambda x,y: x-y)

Ruby で書くと、

def hoge(ary, &f)
  return 0 if ary.empty?
  return ary[0] if ary.size == 1
  return f.call(ary[0], hoge(ary[1..ary.size-1], &f))
end

puts hoge([1,2,3,4,5]){|x,y| x-y}

もしくは、ブロックを使わずに

def hoge2(ary, f)
  return 0 if ary.empty?
  return ary[0] if ary.size == 1
  return f.call(ary[0], hoge2(ary[1..ary.size-1], f))
end

puts hoge2([1,2,3,4,5], lambda{|x,y| x-y})

(ブロックを関数に渡すのは、Ruby のブロックと Proc を参照)

こうやってみると、Ruby の .call の呼出しは可読性が下がるなぁ (@_@;) それに対して、Haskell の関数を中置演算子のように扱える ` ` の機能はいい。

 

8. 書き方いろいろ

ところで、【RubyKaigi'08】詳細レポート : 多様化するRuby：CodeZine に

「1から10までの合計を求めるプログラム（多様性の例）」

として、Rubyハッカー、実務プログラマー、研究者の書き方の例が載っていた。各々、「inject 、for、lamda と再帰」を使った方法で書かれていた。

研究者として書かれていたのは、次の通りだった。

lambda{fn=lambda{|x| return 0 if x==0; x+fn.call(x-1)}}.call.call(10)

lambda がネストしているので、理解しづらい。ただし、今回の記事と、Ruby のブロックと Proc を理解しておけば OK 。

関連記事

• >> Python でリストに対する再帰的な関数の適用

配列を「集計」するときの手順のわかりにくさ

1. 配列の要素を集計をするときに感じた違和感

配列の要素を集計をすることを考える。

例えば、1 ~ 5 までの整数に対して、

1 + 2 + 3 + 4 + 5

の答えを求める場合、次のような手順を踏む。

Ruby で書くなら、

ary = [1, 2, 3, 4, 5]

total = 0
for elem in ary
  total += elem
end

puts total

もちろん、慣れているので、この計算の方法に抵抗は感じない。

しかし、この手順を初めて見たとき、

「わかりにくい」

と感じた。極めてシンプルなコードなんだけれど、どこか頭が混乱するような、そんな感覚に陥ったことを覚えている。

では、その原因はどこにあったのだろうか？

 

2. わかりにくい理由は、「要素の走査」「計算」「変数の再代入」を行なっているから

頭が混乱する印象を受けたのは、以下の箇所。

total += elem

コードの意味を、わかりやすくするために、書きなおす。

total = total + elem

全体のコードで行なっていることは、

1. for によって要素を走査し、
2. その途中で計算を行う。

気になるのは、total の使い方。 配列を走査している最中に、

1. 集計するための total から値を取り出し、
2. それを計算の後、再び total へ設定する。

つまり、以下の 3 つの要素が絡み合っているため、何をやっているのか想像しにくい。

• 「要素の走査」
• 「計算」
• 「変数の再代入」

 

3. 最初は集計の方法をイディオムとして覚えた

プログラミングを始めた当初は、厳密にどのように動いているかというよりも、

このようなイディオムによって集計を行うんだ

と、感覚的な理解をしていた。

今では、配列の要素を「集計」しようと考えたとき、自然と上記のようなコードを書く。しかし、これがどのように動くかを、頭の中で全て思い描けるかと言えば、実はあやしい。デバッガを動かし、それぞれの変数の動きを目で追い、「なるほどなぁ」と思う。それでもコードを見ると、だまされたような感覚に陥る。

ところで、自分の頭の容量は小さい。同時に色々なことを覚えておくことも、把握しておくこともできない。将棋の棋士は、同時に何手先も読むと言うが、あれはいったいどういう頭の仕組みをしているのだろうか。だから、自分の「集計」に対する理解は、まるで刺激に対する反応するようなものだと感じる。これが要求されたら、この方法をとる。まるで、条件付けされているパブロフの犬のようだ。

 

4. 計算の様子をイメージすると、わかりにくい理由がより明確になる

集計をするコードに戻る。

変数 total が、全体を理解する上で、やっかいな存在。 最初に変数が宣言されているのが、for ループの外にある。つまり、要素を走査することとは、別の文脈に存在する。それが要素を走査している文脈に絡んでくるからわかりにくい。

「いつ、どこで、何をしているのか？」

が把握しにくい。

特に、total に elem の値を加算した後、自分自身に再代入しているので、

「誰がどうなったの？」

って感じる。 (@_@;)

イメージしにくいので、絵を描いてみる。そうするば、見通しが立てやすくなる。

1. 配列の要素を elem に割当てる。
2. total と elem を加算する。
3. 上記の結果を total に割当てる。

1 ~ 3 を要素ごとに繰り返す。

絵を描いてみると、「加算」を行っている文脈と、 total が存在する文脈が異なっていることがはっきりする。しかし、コード上では、

total = total + elem

のように、一文で簡潔に表現しされている。

この点が、自分のように容量の小さい頭には、イメージするのが難しい所。複数の文脈が一箇所に集約されていることが混乱の元になっている。

 

5. 計算の手順を分離し、各々役割をクラスに与える

では、これを理解しやすくするには、どうすればいいのだろう？

「要素の走査」「計算」「変数の再代入」を、次のように二つに分けて考えることにした。

• 「要素の走査」
• 「計算」「変数の再代入」

下図のようなイメージした。

集計をするための Total クラスを作り、集計をするための役割を与えた。つまり、「計算」「変数の再代入」の操作を Total クラスにカプセル化。 (まぁ、普通こんなことはしないけれど ^^;)

# 集計の値を保持するクラス
class Total   attr_reader :value  # 集計の値   # 初期化   def initialize    @value = 0   end   # 集計の値に val を加算   def add(val)    @value += val   end
end

add メソッドの中身を見ると、「与えられた値を、これまでの値に加算する」という、極めてシンプルな役割を持っていることがわかる。

このクラス使うには、以下のようにする。

ary = [1, 2, 3, 4, 5, 6]

total = Total.new
for elem in ary
  total.add(elem)
end

puts total.value

for ループの中身を見ると、要素を走査し、Total に「要素の値を追加してね☆」とお願いしているだけになる。

繰り返すが、普通こんなコードは書かない。ただし、自分のようにワーキングメモリの小さい脳みそにとって、このような表現の方が、動作の理解はしやすいと感じる。

 

6. Enumerable の inject を使う場合

ところで、Ruby を使っているなら、イテレータを使って、次のように書くことができる。

total = 0
[1, 2, 3, 4, 5, 6].each do |elem|
  total += elem
end
puts total

Enumerable の inject メソッドを使えば、より簡潔に、

puts [1, 2, 3, 4, 5, 6].inject{|result, item| result + item}

ただし、シンプルだけど、動作をイメージしにくい。

Enumerable - Rubyリファレンスマニュアル によると、

inject([init]) {|result, item| ... }

最初に初期値 init と self の最初の要素を引数にブロックを実行します。2 回目以降のループでは、前のブロックの実行結果と self の次の要素を引数に順次ブロックを実行します。そうして最後の要素まで繰り返し、最後のブロックの実行結果を返します。 ...

初期値 init を省略した場合は、最初に先頭の要素と 2 番目の要素をブロックに渡します。この場合、要素が 1 つしかなければブロックを実行せずに最初の要素を返します。要素が空なら nil を返します。

inject の意味は、Yahoo!辞書 - inject によると、

1 …を（…に）注入する((into ...))；…に（…を）注入［導入］する, 入れる((with ...))

inject a tank with water ［＝inject water into a tank］ タンクに水を注ぎ入れる

ブロックで実行した結果を、再注入するという意味合いなのだろうか？

あぁ～、それにしても動作を想像しにくい。 パタッ(o_ _)ｏ~†

とりあえず、絵に描いておこう。

1. 先頭から 2 つ要素を取り出し、ブロック変数へ入れる。
2. ブロックで実行した結果と、次に要素を取り出し、ブロック変数へ入れる。

これを末尾まで繰り返す。

 

7. 「再帰」で集計するには

for ループを使った計算は、再帰的な定義で置き換えることができる。

ary = [1, 2, 3, 4, 5, 6]

def total(ary)
  return ary[0] if ary.size == 1
  return ary[0] + total(ary[1..ary.size-1])
end

puts total(ary)

これは、次のように集計の手順を考えていると言える。

合計 = 要素の先頭 + 2 番目以降の要素の合計

要素が一つしかない場合は、当然、次のようになる。

合計 = 要素の先頭

イメージとしては、

「先頭と、それ以降、という構造」が、リストの至るところで見られると見なし、順次関数を適用していく方法。

この方法では、「要素の走査」という部分が、「再帰的な関数の適用」にすりかわり、「変数の再代入」が消失し、「計算」のみが残っている。しかし、これが直観的にわかりやすいかどうかと問われたら、微妙。 ^^;

慣れの問題なのかな？