clojure備忘録[replを使った開発手法 その２（map関数）]
標準のmap関数の挙動
最初に実装する関数は「map」という名称の関数です。
（データ型のマップではありません。）
次のようなデータについて考えます。
; 関数名と年代 '(("FORTRAN" 1954) ("Lisp" 1958) ("C" 1972) ("C++" 1983) ("Perl" 1987) ("Python" 1990) ("Haskell" 1990) ("Java" 1995) ("JavaScript" 1995) ("Ruby" 1995) ("Scala" 2003) ("Clojure" 2007))
このデータから、言語名だけを抽出するコードを記述するとしましょう。
早速、sample.cljに次のコードを記述してください。
; 関数名と年代のサンプルデータ (def languages '(("FORTRAN" 1954) ("Lisp" 1958) ("C" 1972) ("C++" 1983) ("Perl" 1987) ("Python" 1990) ("Haskell" 1990) ("Java" 1995) ("JavaScript" 1995) ("Ruby" 1995) ("Scala" 2003) ("Clojure" 2007))) ; 関数名だけを抽出したシーケンスを返す。 (map (fn [language] (first language)) languages)
このコードについて少し説明します。
languagesは、前述のデータを（後で何回も使いたいので）束縛した名称です。
次にmapの呼び出しですが、このコードの目的は「関数名だけを抽出する」なので、
第2引数に先ほどのlanguagesがセットされ、第1引数に変換用の無名関数がセットされています。
この無名関数の引数「language」にはシーケンスlanguagesの要素である、
(言語名 年代)
という構成のS式が渡されてきます。
我々が欲しいのは先頭要素の「言語名」だけですのでfirst関数を使い、
(first language)
とやると目当ての関数名が取得でき、無名関数としてはそれをそのまま返却すればOK、
ということになります。
一応、ダミーのデータを使って確認してみましょう。
user=> (first '("FORTRAN" 1954)) "FORTRAN" user=>
ばっちり言語名が取得できそうです。
では、上記のコードをsample.cljに保存し、
replを起動してload-file関数にsample.cljを指定して評価させてみてください。
user=> (load-file "sample.clj") ("FORTRAN" "Lisp" "C" "C++" "Perl" "Python" "Haskell" "Java" "JavaScript" "Ruby" "Scala" "Clojure") user=>
このように評価結果が返ってくればOKです。
改めて整理すると、
となっていることが分かると思います。
入力データ→「言語名」と「年代」を一対のペアとする要素のシーケンス
出力データ→入力のペアから「言語名」のみが抽出されたシーケンス
念のため、languagesの中身が変更されていないかどうか確認しましょう。
user=> languages (("FORTRAN" 1954) ("Lisp" 1958) ("C" 1972) ("C++" 1983) ("Perl" 1987) ("Python" 1990) ("Haskell" 1990) ("Java" 1995) ("JavaScript" 1995) ("Ruby" 1995) ("Scala" 2003) ("Clojure" 2007)) user=>
・・・横に長くてだいぶ見にくいですね。
こういう時は、pprint関数を使用しましょう。
もう少し見やすい形に整形して表示してくれます。
user=> (pprint languages) (("FORTRAN" 1954) ("Lisp" 1958) ("C" 1972) ("C++" 1983) ("Perl" 1987) ("Python" 1990) ("Haskell" 1990) ("Java" 1995) ("JavaScript" 1995) ("Ruby" 1995) ("Scala" 2003) ("Clojure" 2007)) nil user=>
こちらは定義した時のままちゃんと年代情報が保持されています。
これで、mapは受け取ったデータに対して、
破壊的変更をしない関数であることがお分かり頂けるかと思います。
また、mapの第2引数である無名関数を工夫すると、言語名と年代を使った、
「文字列"XX is created in YYYY."を要素としたシーケンスを生成する」
なんてマネもできます。
先ほどの、関数名だけを抽出した無名関数を参考にして、
年代を抽出するにはどうすればよいかを、
ダミーデータ「'("FORTRAN" 1954)」を使って考えましょう。
年代はfirstでとれないのですからrestを使います。
replに入力して試してみましょう。
user=> (rest '("FORTRAN" 1954)) (1954) user=>
・・・アトムとしての数値だけが欲しいのですが、シーケンス（リスト）で返ってきています。
restはあくまでも「2番目の要素以降をシーケンスとして取得する」ので、
要素が一つしか残っていなくてもシーケンスとして返却されてしまうのです。
では、どうすればよいでしょうか。
ヒントは、
・「(1954)」もシーケンスである。
・1952という数値は、「(1954)」というシーケンスの先頭要素である。
ということです。
そうです、この評価結果のシーケンスに対して、
更にfirst関数を適用するというのが正しいです。
user=> (first (rest '("FORTRAN" 1954))) 1954 user=>
期待した通り、ちゃんと年代情報がアトムとして取得できました。
これで必要な材料は揃いました。
あとは、「"XX is created in YYYY."」という文字列を生成できればOKです。
おあつらえ向きに「str」という関数があります。
この関数は、可変長の引数を受け取り、全ての引数の文字列表現を使用して、
それらを全て連結した文字列を生成して返却します。
language（languagesにあらず）、言語名の取得の仕方、年代の取得の仕方、
そしてstr関数を使うと、目的の処理が記述できます。
(fn [language] (str (first language) " is created in " (first (rest language)) "."))
これでOKなはずです。
んが、もう一つ贅沢を言えば、ちょっと横に長くて見づらいので、
let特殊系式を使用してすっきりさせましょう。
(fn [language] (let [name (first language) ;言語名を取得してnameに束縛 year (first (rest language))] ;年代を取得してyearに束縛 (str name " is created in " year ".") ;name、yearを使って合成した文字列を返却 ))
いかがでしょうか、少し見やすくなったと思います。
（手続き型言語に慣れた方にはそれでも見づらいと思いますがw）
というわけで、mapの第2引数になっている無名関数を次ように変更してみましょう。
; mapの評価 (map (fn [language] (let [name (first language) year (first (rest language))] (str name " is created in " year "."))) languages)
・・・このままでも良いのですが、
この無名関数は後で自前map関数を実装した際にまた使用したいので、
無名ではなく、名前を付けた関数として独立させてしまいましょう。
こんな風に表記できます。
;メッセージ生成関数 (defn create-message [language] (let [name (first language) year (first (rest language))] (str name " is created in " year "."))) ; mapの評価 (map create-message languages) ;上記で定義した関数データを第1引数として渡す。
ついでに関数名だけ返す関数も作っておきましょう。
;関数名取得関数 (defn get-language-name [language] (first language))
最終的に、sample.cljには次のようなコードがかかれている状態になります。
; 関数名と年代のサンプルデータ (def languages '(("FORTRAN" 1954) ("Lisp" 1958) ("C" 1972) ("C++" 1983) ("Perl" 1987) ("Python" 1990) ("Haskell" 1990) ("Java" 1995) ("JavaScript" 1995) ("Ruby" 1995) ("Scala" 2003) ("Clojure" 2007))) ;メッセージ生成関数 (defn create-message [language] (let [name (first language) year (first (rest language))] (str name " is created in " year "."))) ;関数名取得関数 (defn get-language-name [language] (first language)) ;とりあえずメッセージ生成関数を使用してmapを適用 (map create-message languages)
map関数を呼び出しているS式がかなりシンプルになりました。
sample.cljを保存したら、再度load-file関数を使ってリロードしてください。
あ、その際、pprint関数を使って見やすくしましょう。
user=> (pprint (load-file "sample.clj")) ("FORTRAN is created in 1954." "Lisp is created in 1958." "C is created in 1972." "C++ is created in 1983." "Perl is created in 1987." "Python is created in 1990." "Haskell is created in 1990." "Java is created in 1995." "JavaScript is created in 1995." "Ruby is created in 1995." "Scala is created in 2003." "Clojure is created in 2007.") nil user=>
期待した結果が帰ってきました。
さて、改めてmap関数の動作を文章化してみるとこんな感じになります。
入力されたシーケンスを構成している要素を利用して新しい要素を合成し、
それらで構成されるやはり新しいシーケンスを返却する。
言語名を抽出する処理を末尾再帰で実装
さて、map関数の使い方を題材にしてclojureでのコーディングのプロセスに慣れてもらっていますが、
ここからはそのmap関数を自前で実装していくことを題材として、
末尾再帰の考え方に慣れていきます。
それではまず、言語名のみを抽出する具体的なケースについて、
関数呼び出し時にデータがどのようになってゆけばよいか考えてみます。
＜0回目＞ 入力シーケンス：'(("FORTRAN" 1954) ("Lisp" 1958) ("C" 1972) ... ("Clojure" 2007)) ↑の第一要素：'("FORTRAN" 1954) 返却シーケンス：'() ＜1回目＞ 入力シーケンス：'(("Lisp" 1958) ("C" 1972) ... ("Clojure" 2007)) ↑の第一要素：'("Lisp" 1958) 返却シーケンス：'("FORTRAN") ＜2回目＞ 入力シーケンス：'(("C" 1972) ... ("Clojure" 2007)) ↑の第一要素：'("C" 1972) 返却シーケンス：'("FORTRAN" "Lisp") ＜3回目＞ 入力シーケンス：'(... ("Clojure" 2007)) ↑の第一要素：... 返却シーケンス：'("FORTRAN" "Lisp" "C") ... ＜11回目＞ 入力シーケンス：'(("Clojure" 2007)) ↑の第一要素：'("Clojure" 2007) 返却シーケンス：'("FORTRAN" "Lisp" "C" ... "Scala") ＜12回目＞ 入力シーケンス：'() ↑の第一要素：nil 返却シーケンス：'("FORTRAN" "Lisp" "C" ... "Scala" "Clojure") ＜13回目？＞ ★入力シーケンスの要素がなくなったので終了。
なんとなくイメージが沸きますでしょうか。
上記のデータの変遷から、思いつくままにどんな式が必要か考えると、
こんな感じになります。
・入力シーケンスに毎回first関数を適用して要素を取得する式。
・取得した要素から言語名を取得する式。
・再帰呼び出し時、入力シーケンスにrest関数を適用し残りの部分を渡す式。
・再帰呼び出し時、返却シーケンスに言語名を連結する式。
・終了条件として、入力シーケンスの要素がなくなったことを判定する式。
・終了時に返却シーケンスを返す式。
で、いきなりですが、「末尾再帰のロジックを記述するコツ」は↓これです。
１のように実装すると、終了条件に合致した時に返却用データの引数を返すだけで済みますので非常に楽になります。
１．引数に、入力用シーケンスと、最後に返却する為のシーケンスの為の変数を定義してしまう。
２．終了条件を決定し、if特殊系式を書いてしまう。
３．if特殊形式のthen式に、返却する為の変数を書いてしまう。
４．if特殊形式のelse式に、自分自身を呼び出すS式を記述してしまう。
５．４の自分自身を呼び出すS式の第1引数に、「(rest 入力用シーケンス引数)」を書いてしまう。
６．４の自分自身を呼び出すS式の第2引数に、返却するためのデータを合成する式を記述してみる。
２では、全体のロジックの一番大きな骨格ができあがります。「肝その１」です。
３と４と５はもう機械的にやっちゃってください。
６が「肝その２」になります。ここは頭をひねる必要が出てくるでしょう。
材料（データ）や手段（関数）として何が必要になるかが見えてくれば、
もう出来たも同然です。
場合によってはifがletの入れ子になったり、
終了条件や返却値の合成が多少複雑になったために、
doやらletが必要になったりすることはありますが、
１〜５で、大体の骨組みはできてしまっています。
というわけで、分かるところからとりあえずコードを書いてみましょう。
分からないところは適当に「???」とかにしちゃってかまいません。
関数名は自前のmapなので「my-map」にしましょう。
わかりやすさの為、まずは自分自身を呼び出す再帰で実装してみます。
（後でloop/recur特殊形式に変更します。）
(defn my-map [input-seq return-seq] ;★１ (if (???終了条件???) ;★２ return-seq ;★３ (my-map ;★４ (rest input-seq) ;★５ (???return-seqに連結??? (???言語名を取得???) ...)))) ;★６
「末尾再帰のロジックを記述するコツ」に従って、
ここまで一気に記述できました。
あとは★２と★６を埋めれば完成です。
＜★２＞
終了条件です。
前述のデータ遷移のセクションの「＜12回目＞」の入力シーケンスを見てみると、空リスト「'()」となっています。
これを判定するには、単純に「=」関数で比較すればOKです。
(= input-seq '())
＜★６＞
この行は、「(???言語名を取得???)」という式と、
その結果を使って「(???return-seqに連結??? ...)」を行う式の、
２つの式の入れ子になっています。
言語名を取得する式は、「input-seqの先頭要素」を取得後、
更に「その要素の先頭要素」が「言語名」になっていますので、このように記述できます。
(first (first input-seq))
では、return-seqに連結する式はどのように記述したら良いでしょうか。
とりあえずあまり悩まずにconsを使ってしまいましょう。
（順番は逆転してしまいますが、もう一度逆転させればよいですし、
そもそも順番を逆転させる関数を作るのは割と簡単ですので。）
このように記述できます。
(cons (first (first input-seq)) return-seq)
さあ、では「???」になっていた部分を埋めてしまいましょう。
(defn my-map [input-seq return-seq] (if (= input-seq '()) ;★２ return-seq (my-map (rest input-seq) (cons (first (first input-seq)) return-seq)))) ;★６
このような定義になります。早速sample.cljに保存しましょう。
あ、それからもう多分使用することはないですので、
現在記述されているmap関数の呼び出しはコメントアウトしちゃいましょう。
load-file時に余計な出力があるのはうるさいので。
; 関数名と年代のサンプルデータ (def languages '(("FORTRAN" 1954) ("Lisp" 1958) ("C" 1972) ("C++" 1983) ("Perl" 1987) ("Python" 1990) ("Haskell" 1990) ("Java" 1995) ("JavaScript" 1995) ("Ruby" 1995) ("Scala" 2003) ("Clojure" 2007))) ;メッセージ生成関数 (defn create-message [language] (let [name (first language) year (first (rest language))] (str name " is created in " year "."))) ;関数名取得関数 (defn get-language-name [language] (first language)) ;;;とりあえずメッセージ生成関数を使用してmapを適用 ;;(map create-message languages) (defn my-map [input-seq return-seq] (if (= input-seq '()) return-seq (my-map (rest input-seq) (cons (first (first input-seq)) return-seq))))
では、毎度お馴染みload-fileを評価してください。
user=> (load-file "sample.clj") #'user/my-map user=>
早速my-map関数を評価してみましょう。最初に指定する引数は、
「＜0回目＞」の入力シーケンス、返却シーケンスを参考にしてください。
user=> (my-map languages '()) ("Clojure" "Scala" "Ruby" "JavaScript" "Java" "Haskell" "Python" "Perl" "C++" "C" "Lisp" "FORTRAN") user=>
いかがでしょうか、上述のように結果出力されましたか？
見事に逆転してはいますが、言語名のみ抽出できています。
さて、このままでは末尾再帰最適化されていないので落ち着きません。
recurを呼び出す形に変更してしまいましょう。
なぁ〜んにも難しいことはありません、
再帰呼び出ししている箇所の「my-map」を「recur」に変更するだけです。
(defn my-map [input-seq return-seq] (if (= input-seq '()) return-seq (recur ;←★ここです。 (rest input-seq) (cons (first (first input-seq)) return-seq))))
これだけで末尾再帰最適化の形にできます。
が、最初のmy-map関数の呼び出しが美しくありません。
使う側が返却用シーケンスの入れ物を用意するなんてのは使いにくいです。
そこでloop特殊形式の登場です。
my-map関数の引数を、「init-input-seq」という引数一つだけにしてしまいましょう。
もちろんmy-mapを最初に評価するときに指定するのはlanguagesになります。
そして、input-seqとreturn-seqを、letのようにローカル束縛できるのでその形にしてしまいます。
一段ネストが深くなります。
(defn my-map [init-input-seq] (loop [input-seq ???初期化するための入力シーケンス??? return-seq ???初期化するための入力シーケンス???] (if (= input-seq '()) return-seq (recur (rest input-seq) (cons (first (first input-seq)) return-seq)))))
loopのS式の中に終了条件やら次の再帰呼び出しが含まれました。
これにより、recurの呼び出しはloopの呼び出し位置にジャンプすることになります。
ところで「???」で記述した箇所には何を入れればよいでしょうか。
これらはあくまもで初期値ですので、最初の呼び出し時の値にしかなりません。
故に、次のようになります。
(defn my-map [init-input-seq] (loop [input-seq init-input-seq ;my-mapの入力シーケンス引数で初期化。 return-seq '()] ;空リストの入れ物で初期化 (if (= input-seq '()) return-seq (recur (rest input-seq) (cons (first (first input-seq)) return-seq)))))
loop/recur特殊形式を使用したおかげで余計な引数を外部から渡す必要がなくなったので、
my-map関数の呼び出しが自然な感じに変わりました。
例によってload-fileでリロードし、本関数を試してみてください。
動き自体に変化はなく、相変わらず逆転した関数名のみのシーケンスが返却されると思います。
user=> (my-map languages) ("Clojure" "Scala" "Ruby" "JavaScript" "Java" "Haskell" "Python" "Perl" "C++" "C" "Lisp" "FORTRAN") user=>
ここまで来ましたが、recurの引数が分かりにくいのが気に入りません。
recur呼び出しの前に、letを使って意図の分かるコードに変更しましょう。
(defn my-map [init-input-seq] (loop [input-seq init-input-seq return-seq '()] (if (= input-seq '()) return-seq (let [element (first input-seq) ;入力シーケンスの先頭要素 converted-element (first element) ;言語名 next-input-seq (rest input-seq) ;次の再帰呼び出しの為の入力シーケンス next-return-seq (cons converted-element return-seq)] ;次の再帰呼び出しの為の返却用シーケンス。変換・合成された新しい要素（言語名）を連結する。 (recur next-input-seq next-return-seq)))))
如何でしょうか。
letのローカル束縛により、recurが何をしようとしているのかがわかりやすくなったと思いませんか？
ちなみにletはローカル束縛後に複数のS式を記述できますが、
最後に記述されたS式の返却値がletの返却値になります。
故にこのコードの場合、recurが最後に評価されるので末尾再帰最適化の条件に合致することになります。
（recurは特殊形式ですが、特殊形式ならばどんなものでも引数が最後に評価される、というわけではありません。
そもそもrecurは末尾再帰最適化の為の特殊形式ですし。）
ここまで来ると、あとは任意の要素変換用関数を外部から引数で渡してくれば、
my-mapが完成するイメージが沸いてくると思います。
渡してきた変換用関数はどこに記述すれば良いでしょうか。
languageの行、firstを、任意の変換関数で置き換えてやればOKとなります。
(defn my-map [func init-input-seq] ;任意の変換用関数を引数で渡す。 (loop [input-seq init-input-seq return-seq '()] (if (= input-seq '()) return-seq (let [element (first input-seq) converted-element (func element) ;←ここで引数として渡されてきた変換・合成用関数をelementに適用するように変更。 next-input-seq (rest input-seq) next-return-seq (cons converted-element return-seq)] (recur next-input-seq next-return-seq)))))
sample.cljに記述・保存して、load-fileでリロードしてください。
user=> (load-file "sample.clj") #'user/my-map user=>
読み込みは問題なさそうです。
では以前作成したget-language-name関数、create-message関数を使用して動作を確認してみましょう。
user=> (my-map get-language-name languages) ("Clojure" "Scala" "Ruby" "JavaScript" "Java" "Haskell" "Python" "Perl" "C++" "C" "Lisp" "FORTRAN") user=> (pprint (my-map create-message languages)) ("Clojure is created in 2007." "Scala is created in 2003." "Ruby is created in 1995." "JavaScript is created in 1995." "Java is created in 1995." "Haskell is created in 1990." "Python is created in 1990." "Perl is created in 1987." "C++ is created in 1983." "C is created in 1972." "Lisp is created in 1958." "FORTRAN is created in 1954.") nil user=>
大丈夫そうですね。
最後に順序を逆にする関数についてですが、私ちょっと疲れたのでズルして標準のreverse関数を使用しちゃいます。
ifのthen式で返却しているreturn-seqにreverse関数を適用してください。
それでいけちゃいます。
(defn my-map [func init-input-seq] ;任意の変換用関数を引数で渡す。 (loop [input-seq init-input-seq return-seq '()] (if (= input-seq '()) (reverse return-seq) (let [element (first input-seq) converted-element (func element) next-input-seq (rest input-seq) next-return-seq (cons converted-element return-seq)] (recur next-input-seq next-return-seq)))))
一応確認。。
user=> (my-map get-language-name languages) ("FORTRAN" "Lisp" "C" "C++" "Perl" "Python" "Haskell" "Java" "JavaScript" "Ruby" "Scala" "Clojure") user=>
よっしゃ。
如何でしたでしょうか。
手続き型の人が、段階を追ってLisp的コーディングを理解できるようにしたため、
アホみたいな長さになってしまいました。誰も最後まで読まねぇだろうなぁコレw
ま、Lispの「基礎的なコード」というのは、
の３つじゃないかと思います。
・first、rest、consを駆使したデータの分解・合成
・末尾再帰
・関数オブジェクト（クロージャ）
これを押さえて、次のステップであるより便利なシーケンス操作関数（リスト操作関数）を知っていくと、
「繰り返し構文て要らなくね？」という境地に立てる・・・かも？
この後のエントリでは、filter関数、reduce関数、sort関数の使い方を紹介します。
いずれもかなり頻繁に使用するシーケンス関数です。
これらの関数の内部では同じような（いや実際にはもっと効率的になっているんじゃないかなぁと思いますが）手法が使われているとイメージしつつ、
シーケンス関数群の使い方を一段深いレイヤーで理解する助けになればと思います。
あー疲れた。。
