2010年7月30日金曜日

Windows で GitHub の利用 - msysgit, TortoiseGit を使って

0. 目次

  1. Git の特徴
  2. Windows で msysgit
  3. GitHub でリポジトリを作成
  4. 日本語の設定
  5. Git を使うためのクライアント - TortoiseGit
  6. Git のコマンドを使ってみる

 

1. Git の特徴

SnapCrab_No-1007ソースコードの管理に GitHub を利用してみる。

Git - Wikipedia とは、

プログラムなどのソースコード管理を行う分散型バージョン管理システム。動作速度に重点が置かれている。Linuxカーネルのソースコード管理を目的として、リーナス・トーバルズによって開発された。

特徴を押さえておく。

Gitは、arch等にも採用される分散リポジトリをサポートしており、

  • 中央リポジトリからコピーする
  • コピーしたリポジトリを編集し、コンテンツの修正、追加、削除を行う
  • ローカルへコミットする
  • 中央リポジトリへ変更内容を反映させる

という形で行われる。

リポジトリへのアクセスは

  • ローカル
  • WebDAV
  • Git 独自プロトコル
  • rsync
  • ssh

を用いる(書き込みができるのはローカル、WebDAV および ssh)。

(同上より)

分散バージョン管理なので、基本的な考え方として、

… ローカルのリポジトリ(master)をリモートのリポジトリ(origin)にプッシュ、つまり反映させます。

(せっかちな人のための git 入門 - git をインストールし、共同で開発できる環境を整えるまで : 僕は発展途上技術者 より)

詳しくは以下を参照。

 

2. Windows で msysgit

SnapCrab_No-1013Windows で git を使うために 「github を Windows で使ってみる | Numb.」 を参考にした。

をダウンロードしてインストール。

( はじめて msysgit を設定したときは、msysGit-netinstall-1.5.4-rc0-preview20071217.exe を利用した。今回は Git-1.7.0.2-preview20100309.exe 。)

とっても優しい github の使い方 - ¬¬日常日記 によると、

あ、私のようなgit初心者の方は、まず最初に … 名前とメールアドレスを設定しておいて下さい。これを忘れるとマシン名とかがコミットログに残って恥ずかしい感じになります。

最初に、名前とメールアドレスを設定しておく。

git config --global user.name "名前"
git config --global user.email メールアドレス

これにより、環境変数 %HOME% 以下に .gitconfig ファイルが作成された。

 

3. GitHub でリポジトリを作成

  1. SnapCrab_No-1014 Your Dashboard – GitHub において Create a Repository により新規にリポジトリを作成。
  2. 最低限 Project Name を記述し、 Create Repository ボタンを押す。
  3. この後に行うコマンドライン上での作業が表示される。
  4. Global setup については上記で既に行なったので、それ以降の作業を行う。

 

SSH-key の作成

リポジトリへアクセスするための認証用に SSH-key を作成。

先ほどインストールした Git Bash を起動して、

ssh-keygen -t rsa –C "メールアドレス"

( Help.GitHub - Generating SSH keys (Win/msysgit) より )

これにより環境変数 %HOME% 以下に .ssh フォルダが作成され、その中に

  • id_rsa
  • id_rsa.pub

の二つのファイルができる。

この内、id_rsa.pub の内容を Your Account - GitHub の SSH Public Keys に設定。

 

git remote コマンドにより、リモートのリポジトリを指定

上記の「コマンドライン上での作業」における Next steps: には、次のように書かれていた。

mkdir プロジェクト名
cd プロジェクト名
git init
touch README
git add README
git commit -m 'first commit'
git remote add origin git@github.com:ユーザ名/プロジェクト名.git
git push origin master

ファイル README を追加した後、コミットして、プッシュするという作業の流れ。

プッシュする前のコマンド git remote add は、git-remote(1) によると、

git remote add [-t <branch>] [-m <master>] [-f] [--tags|--no-tags] [--mirror] <name> <url>

ここでの add の意味は、

add

Adds a remote named <name> for the repository at <url>.

name と url を結び付ける。

git push では、上記で設定した name を指定。

git-push(1) の Examples によると、

git push origin master

Find a ref that matches master in the source repository (most likely, it would find refs/heads/master), and update the same ref (e.g. refs/heads/master) in origin repository with it. If master did not exist remotely, it would be created.

初回の実行では master がリモートに作成される。

 

4. 日本語の設定

を参考にして、日本語の設定を行う。

C:\Program Files\Git\bin に lessnkf を配置。

C:\Program Files\Git\etc\inputrc に以下を記述。

set convert-meta off
set meta-flag on
set output-meta on
set kanji-code utf-8

(WindowsでのGit環境構築とその注意点 より)

C:\Program Files\Git\etc\profile に以下を追記。

export GIT_EDITOR="'<使用するテキストエディタのパス>'"
export GIT_PAGER="nkf -s | less"

このとき、テキストエディタのパス中の「\」は「/」に、「C:」は「/c」に置き換えて指定する。

(同上より)

これにより、ソースコードが変更されたフォルダで、Git Bash を起動 (右クリック > Git Bash) し、

git diff ファイル名

を実行すると、日本語が表示される。

ファイルの中身を見たいときは、

nkf –s ファイル名 | less

 

5. Git を使うためのクライアント - TortoiseGit

SnapCrab_No-1006コマンドライン上での操作ではなく、GUI で Git を扱いたいなら TortoiseGit tortoisegit を使う。TortoiseSVN に慣れている場合は、これを使うのが良い。

Download – tortoisegit より、「本体」と「言語パック」をダウンロードする。

 

日本語化

言語パックをインストールした後、

  • TortoiseGit > Settgings > General > TortoiseGit > Language:

において、日本語を選択する。

SnapCrab_No-1004

 

SSH

を参考にして SSH を設定。

TortoiseGitの設定ダイアログを開き、「Network」の「SSH client」にmsysgit付属のssh.exeを指定する。

上記では 「OpenSSHの秘密鍵をPuTTY形式に変換して使う」 方法も書かれている。

 

6. Git のコマンドを使ってみる

まずは、基本的なところで 「github を Windows で使ってみる | Numb.」 より、

git add README
README というファイルをリポジトリに追加
git commit -m ‘first commit’
ローカルのリポジトリに変更を適用 ‘first…’ のところはコメント
git push origin master
リモートリポジトリに変更を適用( master を origin に push )
( cd hogehoge )
git pull origin master
(ローカルリポジトリのディレクトリに移動して)リモートリポジトリの変更をローカルリポジトリに適用

その他、解説しているサイトを試して慣れる。

コマンドの解説としては以下を参照。

 

チェックアウト

既にリポジトリにソースが存在し、チェックアウトするには、予め GitHub で SSH の URL コピーしておく。

Git Bash において、

git clone git@github.com:ユーザ名/プロジェクト名.git

このとき公開鍵を作成したときのパスワードを入力。

TortoiseGit を使う場合は、適当なフォルダで右クリック > Git Clone… 。github にある SSH の URL を入力して Web を選択。

 

コミットとプッシュ
  1. TortoiseGit を使うなら、ソースコードを変更した後、右クリック > Git Commit –> “master”…
  2. ローカルの変更をリモートに反映させるには、右クリック > Tortoise Git > Push

 

ブランチの削除

間違えて作成したブランチを削除したい。

リモートのブランチの削除は
% git push origin :experimental

( GitHubをRemote Repoとして、MacにインストールしたGitから使ってみる:Goodpic より)

git-push(1) によると、

git push origin :experimental

     Find a ref that matches experimental in the origin repository (e.g. refs/heads/experimental), and delete it.

Git Bash を起動し、上記 experimental の代わりに、GitHub のリポジトリのページにある `Switch Branches’ に表示される `削除したいブランチ名’ を入れて実行する。

2010年7月28日水曜日

オーバークロックの基礎知識を仕入れる - Core 2 Duo E8400 の

Windows 上のユーティリティで CPU をオーバークロック のつづき

1. AI SUITE によるオーバークロック

Core 2 Duo E8400 をオーバークロックするために、Windows 上で設定を行うことができるツール AI SUITE を用いた。

このとき、何によってオーバークロックすると、どこが変化するのかわからないまま適当に値を変えていた。最初はメモリの耐性も考えずに設定をしたので、すぐにブルースリーンとなった。 (+_+)

 

2. BIOS における設定

a. オーバークロックする環境

自分が PC で利用しているパーツは以下の通り。

相変わらず、オーバークロックに関して、何が正しい知識で、どう設定するのがベストなのかよくわからない。しかし、分からないなりに今回 BIOS でオーバークロックしてみる。

目標値は 3.6 GHz で常用。

 

b. CPU とメモリの設定

BIOS で CPU とメモリを、以下のように設定した。

Advanced > JumperFree Configuration

  • Ai Overclocking : Manual
    • CPU Ratio Control : 9.0
    • FSB Frequency : 400
  • PCIE Frequency : 100
  • DRAM Frequency : DDR2-667MHz (DDR2-801MHz と表示される)
  • DRAM Timing Control : Manual
    • CAS# Latency : 5
    • RAS# to CAS# Delay : 5
    • RAS# Precharge : 5
    • RAS# Activate to Precharge : 15
  • CPU Voltage : 1.2375V
  • DRAM Voltage : 1.80V

ここで気をつけることは DRM Frequency で、オーバークロックによって規格以上の周波数になってしまうと、即ブルースクリーンになってしまうこと。使っているメモリは DDR2-800 だから、オーバークロックしたときに、メモリの耐性の上限を超えてしまうので、DDR2-667MHz を選択。FSB Frequency を 400 に設定した後は、800MHz 付近を大きく上まらないようにした。

CPU の電圧を 1.2V に設定ときは、動画を再生中に、ブラウザのスクロールをするとビリビリとノイズがした。上記の設定であると、大分ノイズが減る。

 

c. ファンの設定

CPU に負荷がかかっていないときに、ファンがやかましくならないように設定した。

Power > Hardware Monitor

  • CPU Q-Fan Control : Enabled
    • CPU Fan Profile : Performance Mode
  • Chassis Q-Fan Control : Enabled
    • Chassis Fan Ratio : Auto
  • Chassis Target Temperature : 38

 

3. オーバークロックをするために参考にしたサイト

上記の設定をしたとき、いろいろなサイトを参考にした。しかし、細かいところまでは結局分からず。 (@_@;

参考にした記事を列挙しておく。

 

a. オーバークロックの方法

まずは、オーバークロックをする方法として押さえておくべきことは、

低ランクのCPU(Celeron等)を高ランクのCPU(Pentium II等)と同じFSBで動作させる事で全体的な性能の底上げを期待する方法。BIOS画面等で簡単に設定できるため、現在のカジュアルなオーバークロックの主流となっている。この場合、使用するマザーボードには、PCIクロックを100MHzに固定できること、メモリクロックだけを落とせることが事実上必須となり、さらには、CPUの電圧を上げられることが望ましい。

  • 倍率変更・FSB向上の特徴

同じ(あるいは近い)周波数になる組み合わせであっても、FSBを高くして倍率を小さくする設定の方が高性能に なる。FSBはCPU以外のメモリやチップセットといったシステムを構成する主要パーツにも供給されているからである。

(オーバークロックの手法  より、太字は引用者による)

 

b. 前提となるパーツの知識

オーバークロックに関して、前提となる PC に関する大枠の知識は、

【特集】魅惑のクロックアップ ~自作PCの限界チューニングにチャレンジ (2) クロックアップのしくみ | パソコン | マイコミジャーナル

一般的なクロック供給の状態

クロック供給において、その元となるのは「PLL(Phase Locked Loop)」と呼ばれる発信器であり、これがシステムが動作するために必要なほとんどのクロック(上図の青ライン) を供給している。…

…クロックを上昇するとパソコンに組み込んでいる周辺機器へのクロックも同時に上昇するため、CPUほどにクロックアップの耐性がない周辺機器は誤動作を起こしやすくなってしまう…

上図にある重要な部品について調べる。

チップセット - Wikipedia

チップセットにはメモリインタフェースやAGPなどの制御回路が搭載されているため、コンピュータの性能に重大な 影響を与える。すなわちマザーボード[2]は 特殊な場合を除き、CPUをターゲットに設計されるのではなく、直接の設計ターゲットはチップセットとなる。CPUの交換が想定されているシステムは必ず しも珍しくないが、チップセットのみの交換を想定しているシステムは存在しない。

ノースブリッジ - Wikipedia

PC/AT互換機における2チップ構成のチップセットを搭載したマザーボードにおいて、CPUに接続されている方のチップを言う。設計図(製品ではプリント基板)を地図に 見立てた場合、上方に位置し、データの橋渡しを担う部品であることからこう呼ばれる。

ノースブリッジには、CPUインタフェース、メモリーインタフェース、AGPPCI Expressなどの制御回路が入っている。その性格上、特定のCPU専用品となる。

サウスブリッジ - Wikipedia

サウスブリッジには、PCIバス、IDEキーボードポートマウスポート、USBなどの回路が含まれる。最近はサウンドやイーサネットなどを含むものも増えて、高機能化する傾向にある。

 

c. FSB とベースクロックの関係

ところで FSB / 4 がベースクロックになると説明されているのを見かけるが、これはどういうことか?

図解 CPUのクロック周波数 - [ノートパソコン] All About によると、

クロック周波数とは...

処理のタイミングを取るためのテンポ

単位はヘルツ(Hz)で、1ヘルツなら1秒間に1回の周波数と いう意味。

1971年に登場した世界初のマイコンである Intel 4004は500kHzで動作していたと いう。

FSB (Front Side Bus:フロント・サイド・バス)
CPUとチップセットを接続するバス(伝送 路)
FSBとベースクロックの周波数が異なっているが、これは1クロックで1つの信号を送るところ、クアッドパンプ(Quad Pumped)と いう技術を使い、1クロックで4つの信号を送っているためだ。
クアッドパンプが使われ出したのは、2000 年に登場のPentium 4から。
倍率とEnhanced Intel SpeedStep

CPUの動作倍率は、Core 2 Duo T7300の場合なら6倍から10倍(11倍)程度の範囲で倍率 と電圧が変化する。一般的にバッテリ駆動時は倍率を低く、AC駆動時などパフォーマンスを重視する場合は倍率を高くする。この倍率と電圧を 可変させているのがEnhanced Intel SpeedStepだ。

 

d. CPU の電圧

CPU の電圧の設定で参考にしたのは、

Core 2 Duo E8400 オーバークロックと性能、CPU温度 の説明。

Fudzilla によれば、E8400は容易に 4.4GHzに達するようである。しかし、解説の中で最適なセッティングは動作クロック3.60GHz、コア電圧は1.2250V - 1.2750Vと述べていた。また4GHz辺りまではコア電圧を1.3250V - 1.4000Vにする必要があるようである。

E8400 の電圧に関するスペックを確認しておく。

Intel® Core™2 Duo Processor E8400 (6M Cache, 3.00 GHz, 1333 MHz FSB) with SPEC Code(s) SLAPL, SLB9J

VID Voltage Range    0.8500V-1.3625V
TCASE                      72.4°C
VID

ここでまた VID という分からない単語がでてきた。VID は Core Temp で確認できる。
自分の PC では 1.2250v と表示された。

VID の意味は、

CPU とマザーは、連携してCPUへの供給電圧を決定しています。
その関係は、CPUがVID信号で規定の電圧をマザーにしらせ、
マザーはその VID信号の指示に基づいて電圧を生成し、CPUに供給する。
CPUはマザーから供給される電圧を「指示した通りと信じて」受け取る。
と いう仕組みです。

(定格動作( より)

CPU の電圧と消費電力の関係は、

ワット チェッカーで自作マシンの消費電力計測 によると、

CPU の電圧 (CPU VCore) を上げると消費電力が増えるのは有名な話。それを実験で試してみる。CPU の消費電力は周波数に比例し、電圧の 2 乗に比例する。たとえば、電圧が 1.2 倍になれば消費電力は 1.2 の 2 乗で 1.44 倍になる。
では、CPU の最大電圧はどのくらいなのだろう?
Max CPU voltage range and overclocking - CPUs - Overclocking  には、
For 65nm: ABSOLUTE MAX is 1.5v.
For 45nm: ABSOLUTE MAX is 1.45v.
ABSOLUTE MAX is the point where the CPU starts to get physically damaged. It is the point of no return.
VID Voltage Range - How does it affect overclocking? - XtremeSystems Forums
The way I understand VID is that it is similar to SPD on ram. It tell the mobo how much voltage it requires to run at its defined speed. A low VID is considered better as it requires less voltage and theoretically can overclock higher due to there being less voltage required at a given overclock resulting in less heat. That dosn't mean to say 1.5 is 'officially' safe. It simply means some cpus require 1.5v to run correctly, while others do not.

site:intel.com absolute max voltage - Google 検索 により、CPU に関する文書を見つけた。

以下の節に電圧に関することが書かれているがよくわからなかった。 (+_+)

2.6        Voltage and Current Specification
2.6.2       DC Voltage and Current Specification

とにかく、VID と BIOS で設定できる CPU Voltage Control は別物であると理解。

TCASE

オーバークロックしたときに気になるのは CPU の温度。

PCが不安定 2/3 | PCトラブルバスターズ!!! | DOS/V POWER REPORT

CPU の温度は、CPUメーカーが公開しているデータシートやサーマル デザインガイドに記載されているTcase MAXの値が参考になる。TcaseはCPUのヒートスプレッダ中央部分の温度のことで、Tcase MAXはその上限だ。つまり、この温度より低くなるように冷却すればよい。厳密には上にあるようなユーティリティ類が表示するCPU温度=Tcaseでは ないが、目安にはなる。
ASCII.jp:パソコンがうるさいと思ったときの「最高動作温度」|ぱそぢえ~3分で分かるPCの基本

CPUのデータシートで規定されている最高動作温度は「T-Junction(Tj)」「T-Case(Tc)」「T-Sink(Tsink)」「T-Ambient(Ta)」の4種類がある。具体的には下記の温度を示している。...
Pentium 4以降のデスクトップ向けCPUは欠損などを防ぐため、コアの表面に金属製プレートを装着することが一般的になっている。そのためにT-Caseが用いられることが多い。

 

e. メモリの設定

使用するメモリの個数は、

OC による負担はメモリーが一番多く被るので,2個以上のメモリーを用いるときは必ず同じクロック数のものに限定し,特に Dual Channel 設定の際は必ずそれが可能なメモリーの2枚挿しを行なおう.また,4枚挿しの メモリー OC は基本的に無理である

(パソコンのオーバーク ロック(OC)勉強中:BIOS を用いた OC 設定の基本 ― OC 初心者専用です より)

2枚が無難そうだけれど、4 枚使うことにした。

CPU の電圧を固定したので、メモリの電圧も固定することに。

ASUSTeK Computer Inc. -Support- FAQ P5K-E FAQ メモリの電圧について

JEDEC(半導体技術協会)が定義する標準的な電圧値は、 DDR2メモリ、DDR3メモリではそれぞれ 1.8V、1.5Vですが、それ以上の電圧が必要なメモリもあります。これらのメモリでは電圧供給が足りなくなり、このような症状が起こることがありま す。

これらの症状が見られ る場合は、ご使用のメモリの動作電圧を確認し、それに応じてBIOSでメモリ電圧を手動で設定してください。

ところで、メモリの種類については、DDR2 SDRAM - Wikipedia によると、

4ビットのプリフェッチ機能(CPUがデータを必要とする前にメモリから先読みして取り出す機能)をもち、外部クロックに内部クロックの2倍のクロックを用いる。そのため理論上、同一クロックで動作するDDR SDRAMの2倍、SDRAMの4倍のデータ転送速度を得られる。...

動作電源電圧は、DDR SDRAMの2.5V/2.6Vに対し、DDR2 SDRAMは1.8V動作

メモリのアクセスタイムについては、

アクセスタイムとは【access time】 - 意味/解説/説明/定義 : IT用語辞典

メモリチップのアクセスタイムは、行アドレス(CAS)信号から列アドレス(RAS)信号への切り換え遅延時間(RAS to CAS Delay)に、行アドレスを与えてからデータが読み出せるようになるまでの時間(CASレイテンシ)を加えた時間である。

DDR3 SDRAM - Wikipedia

JEDEC準拠のDDR2デバイスは5-5-5-15であった

PCメンテナンス&リペア・ガイド:第3回 メモリ増設前の基礎知識(3)

CAS Latency(Column Address Strobe Latency)

「キャス・レイテンシ」と読む。メモリのスペックでは「CL2」や「CL3」などと表記される。SDRAMDDR SDRAMなどのメモリ内部には、半導体記憶素子が格子状に並んでおり、データの読み書きを行う際には、対象となる記憶素子の位置を、行(Row)と列(Column)という2種類の位置情報(アドレス)で指定する必要がある。列を指定する信号をCAS(Column Address Strobe)信号というが、この信号が発行されてから、実際にデータの読み書きが行われるまでにかかる待ち時間(Latency)のことをCAS Latencyという。

SDRAM RAS to CAS Delay

SDRAMについて、RASの後にどれだけ時間を置いてCASに移行するかを設定する項目。間隔が短く(数字が小さく)なればメモリアクセスが高速になる。

この辺になると何がなんだか本格的にわからなくなってきたので、標準的な値でありそうなところで固定した。

 

関連記事

2010年7月26日月曜日

Dropbox でファイルを共有する場合、パスの記述に環境変数を利用する

Windows において Dropbox でファイルを共有している。共有しているファイルへのパスを文書中に記述し、ファイルの所在に関する情報も共有しておきたい。

例えば、`テスト.txt’ が以下の場所に置いてあるとする。

C:\Users\ユーザ名\Documents\My Dropbox\テスト.txt

このパスを何処かへ書いておき共有しようとしても、ユーザ名や Windows のバージョンによって絶対パスが異なるため、このままでは適切にリソースを指し示すことができない。

 

環境変数の設定

「コンピュータ > プロパティ > システムの詳細設定 > 詳細設定 > 環境変数」で、Dropbox のあるフォルダの位置を環境変数として設定しておく。

環境変数ダイアログにおいて、新規ボタンを押してユーザ変数を追加。「変数名」は適当に

DROPBOX

とした。

変数値」は、Windowsの環境変数 によると、

USERPROFILE
現在のユーザのユーザプロファイルフォルダのパス名が設定されている。例: C:\Documents and Settings\%USERNAME%

よって、Windows Vista の場合、
%USERPROFILE%\Documents\My Dropbox
Windows xp の場合、
%USERPROFILE%\My Documents\My Dropbox

とする。

環境変数を確認するにはコマンドプロンプトで、

echo %DROPBOX%

により表示。

 

ショートカットキーで素早く開く

設定をしたら、Dropbox 上に置いてあるフォルダを指し示すのに以下の形式で文書中に記述できる。

%DROPBOX%\フォルダ名

フォルダを開くには

  1. 上記文字列をコピーし、
  2. Windows キー + R で 「ファイル名を指定して実行」ダイアログを表示させ、
  3. ペーストして OK バタンを押せば、

素早く目的のものに到達する。

2010年7月24日土曜日

Meadow で Undo, やり直し

一般的なアプリケーションにおける「元に戻す」「やり直す」

Windows や Mac の一般的なアプリーケーションにおける 「元に戻す」「やり直し」の操作は、

Windows 7 のショートカット キー

Ctrl + Z 元に戻す
Ctrl + Y 操作をやり直す

 Mac OS X のキーボードショートカット

command + Z 前のコマンドの取り消し
shift + command + Z 前のコマンドのやり直し

しかし、操作を 「やり直す」 ということが滅多にないので、これにショートカットキー Ctrl + Y が付けられていることを長いこと知らなかった。 ^^; 友人から「初心者向け PC の検定問題にあった」と聞いて、はじめてそんなキーが割り当てられていることに気づかされ、「使わない機能に対しては、その存在すら意識が向かないものだなぁ」とつくづく感じた。いや、しかし、Mac 使ってたときは上記のショートカットキーを使っていたような気もするんだけれど。。

img07-24-2010[1]

それはともかく、

元に戻す  >>  元に戻す  >>  元に戻す

によって行なった操作は、

やり直し  >>  やり直し  >>  やり直し

により、また元の状態に戻る。

 

Meadow の Undo

Meadow で操作を「元に戻す」には、

C-/

Undo の `u’ の字が割り当てられているキー操作を使うなら、

C-x u

 

操作の繰り返し

元に戻す操作を繰り返したいとき、上記 C-x u を連続して入力するのは面倒なので、

C-x z

と組み合わせる。 2.2 ファイルの作成,編集 によると、

バッファに対して何らかの編集作業を行った後,その作業を繰り返す場合には, C-x zを入力します.これにより,前に行った作業を反復して実行できます.このように操作の反復を行うことを``Redo''といいます.Redoを繰り返すことによって,作業を効率的に行えます.なお,C-x zは,一度実行した後は zを押すだけで繰り返しを行えます.Undoと組み合わせることで,一度取り消した作業を再びやり直すUndoを繰り返し行うなどの作業を行えます.

(太字は引用者による)

つまり、 EmacsWiki: Category Undo で述べられているように、

Having once undone a change with ‘C-x u’ or `C-_’, you can repeat the undo command by pressing ‘C-x z’, which is ‘repeat’. So the overall sequence of C-x u C-x z z z z z undoes changes back through time, and may be easier to type than `C-_ C-_ …’.

(太字は引用者による)

 

やり直し

これに対して、「やり直す」操作は、

一般のWindowsアプリのundoのつもりで使ってると混乱するんですよ。

具体的には「undo:ひとつ前のコマンドを取り消す」なんですが、「undo」自体もコマンドと認識されるので、undoコマンドでundoをundo できるっていう(※連続してundoしてるかぎりは直前のundoがundoされることはない)。つまり一般的なアプリでいうところのredoをundo コマンドひとつでやってしまうっていう。慣れたら便利だけど慣れないときもい。

(080525(Sun) emacsメモその2・undo/redo編 - BKCのBの方 より)

例えば、間違えて 

C-/

により Undo し過ぎたら、

C-g

を入力して、再び

C-/

を入力する。

つまり、

C-/   >>   C-/   >>   C-/

によって行なった操作は、

C-g   >>   C-/   >>   C-/   >>   C-/

により、また元の状態に戻る。

 

参考サイト

Key Index - GNU Emacs Manual

2010年7月22日木曜日

ネットラジオでボサノバ (3) と Time After Time

あ~、暑い暑い。 (+_+) 

こういう日は冷房の効いた部屋で、ゆったりとボサノバでも聴きながらまったりとしてたい。

これまでボサノバが聴きたくなったら、SHOUTcast RadioBossa Nova カテゴリーの中にある Bossa Nova Jazz - S K Y . F M  を BGM として流していた。しかし、このチャンネルはややアップテンポな曲が多く、酷暑のときはちょっとうっとおしく感じることも。

 

Blue Bossa Nova

ボッサを中心に曲が聴きたいのだけれど、割と軽めでイージーリスニングに近く、テンポがゆるめのチャンネルはないものか?と思っていたところ、Radionomy というインターネットラジオの Bossa Nova カテゴリーの中にあった

が良かった。 ^^

このチャンネルのジャンルを見ると、

Lounge , Latin Jazz , Latin Pop , Bossa Nova , Chill-out

自分の聴きたいところと大体かぶっている。局によって、「ラウンジ」と書かれていると少し重めの曲が流れることがあるが、ここはそうでもない。また、「ラテン」とあるけれどそれほど暑苦しい曲でもない。ラテンなフュージョンと言った感じの音楽が流れていた。例えば、

LUISITO QUINTERO feat ANANE' OUR LOVE

爽やかで良かったのは、カーペンターズやビートルズをアレンジした曲。流れていたものと同じではないけれど Youtube で検索してみたら次の曲がヒット。

Marcela Mangabeira Goodbye To Love

 Monique Kessous - Yesterday

などなど。

 

Time After Time の色々なアレンジ

その他、なつかしいフレーズを聴くことができた。「何だったかなこの曲?」 と思いタイトルを検索したら、シンディ・ローパーTime After Time 。このボサノババージョン。流れていた曲とは違うけれど、これまたいい感じ。

FLAVOR BOSSA CASE TIME AFTER TIME YASUKO OKANO

他にも色々とアレンジされた Time After Time を探したら、個人的にはこれが一番かな。

Time After Time - Ashley Tisdale (FULL)

Jazz ? Swing ? バージョンもあり。 Time After Time - Sarah Menescal

日本人もあり。 Sowelu - Time After Time

 Chara Time After Time

まだまだ、たくさんあった。 Cassandra Wilson Time after time

YouTube - Time After Time (Tuck & Patti)

YouTube - Ronan Keating - Time After Time

YouTube - Time After Time - QUIETDRIVE (w/ lyrics)

YouTube - Time After Time - INOJ

 YouTube - Novaspace - Time after Time Rebirth - 2009 (HQ 16:9)

 

関連記事

2010年7月21日水曜日

SKKIME の辞書ファイルはDropbox 置き、壊れたら前のバージョンに戻す

何かの拍子に SKKIME の辞書ファイルが壊れることがたまにある。色々と単語を登録してあるので修復せざる負えない。しかし、定期的にバックアップするのは面倒だし、それほど大した手間ではないけれど元に戻すときはうんざりしてしまう。

だから、バージョン管理を自動的にしてくれる Dropbox に辞書ファイルを置いている。以下、辞書ファイルが壊れたときの対処。

 

Dropbox 上で以前のバージョンに戻す

SKKIME の辞書が置いてある Dropbox 内のフォルダを開き、右クリック > Browse on Dropbox Website…

img05-04-2010[5]

Dropbox 上で以前のバージョンに戻すために、辞書ファイルで Previous versions を選択。

img05-04-2010[6]

正常な辞書ファイルはファイルサイズが大きいはずなので、Size を目安にして元に戻すバージョンを選ぶ。

img05-04-2010[7]

 

辞書の修復

ローカルの PC 上のファイルサイズが元に戻ったのを確認したら、SKKIME で辞書の参照設定をする。

  1. 言語バーで右クリック > 設定。
  2. 「全般」タブにおいて、SKKIME を選択してプロパティボタンを押す。
  3. 「辞書設定」タブにおいて、ユーザ辞書の「修復」ボタンをクリック。

img05-04-2010[8]

ファイルを復活させた後から修復ボタンを押すまでの間に漢字変換をすると、また壊れてしまうのかな?

Haskell のデータ構造と高階関数 - 総和・総乗から畳み込み関数へ

1. ウォーミングアップ用の課題を作成

久しぶりに Haskell を触ったら、毎度のごとく、頭から抜けてる。。 (o_ _)o~† 以前の記事を読み返しても、他人が書いたものにしか見えない。 (@_@;

どんな言語でも、一定期間、手を動かしてないと、基本的なことですら忘れる。

関数を定義する構文って def で始まるんだっけ?それとも function だったかな?

変数定義するとき、何を前に書くんだっけ?

など枚挙にいとまがない。だから、関数名なんて、色々なものがごちゃ混ぜになり、覚える気さえ起きない。

言語の依って立つパラダイムに馴染んでないと、そんな表層的な部分だけでなく、根本的なところでわからなくなる。覚えたと思ったことが、その片鱗さえ消え去っていることは日常茶飯事。そして、意気消沈。 1 歩進んでは 2,3 歩後退し、何かの間違えで、偶然 1 歩進める。そんな繰り返し。

当の Haskell は、相変わらず停滞している。どこまで何を理解したか、記憶が定かでない。さすがにこれではまずい。

対策として、思いついたのは計算ドリル。小学生のとき、機械的に計算を繰り返すことにより、計算に慣れた。それと同じように、ウォーミングアップ用の課題を用意しておき、記憶の底に沈み込んだ感覚を、少しでも回収できるよう、自分用の課題を用意しておくことにした。

 

2. 課題の内容

今回、課題としたのは、関数型プログラミングを学ぼうとした契機となった論文の一つより抽出。

の部分。この節は特に、関数の抽象化に馴染むための題材として打って付け。 Haskell に限らず、関数を引数として渡せたり、関数の返り値として関数を返すことができる言語、所謂、関数がファーストクラスオブジェクトな言語の練習課題として良いはず。

課題の内容は、

  1. リスト型を定義
  2. リストの要素に対して、「総和・総乗」を求める関数を定義 … (A)
  3. (A) の関数を元にして、抽象化した畳み込み関数を定義
  4. 上記の畳み込み関数を使って以下を定義
    • 総和・総乗
    • 値をコピーする関数
    • 要素に関数を適用する関数 ( map )
    • 特定の要素を抽出する関数 ( filter )

上記と同様な課題を、ツリーに対しても行う。

まとめると、

  1. 代数的データ型を定義し
  2. 簡単な計算を行ない
  3. そこから高階関数を導き
  4. 高階関数を使って、他の関数を定義する

 

3. リストで総和・総乗から、畳み込み関数まで

a. リストを代数的データ型で定義

まずはリストを定義する。 Haskell ではリストに対して特別な構文が用意されているが、ここでは代数的データ型として自分で定義する。 (cf. 6.1.3 リスト, Haskell の cons ) その方が、後々、別のデータ型を定義したときの参考になるため。

データコンストラクタは、以下の二つから成る。

  • 空のリストを表わす Nil
  • リスト型の先頭に要素を追加するデータコンストラクタ Cons
data List a = Nil 
            | Cons a (List a)
              deriving Show

これを用いて、例えば、数値 1 ~ 4 の要素を持つリストを作成。

list0 = Cons 1 (Cons 2 (Cons 3 (Cons 4 Nil)))

 

b. リストで総和、総乗の定義

次に、リストの要素の総和を返す sumList 関数の定義をしてみる。

sumList Nil = 0
sumList (Cons x xs) = x + sumList xs

これに対して、総乗を返す関数 productList の定義は、

productList Nil = 1
productList (Cons x xs) = x * productList xs

先ほど定義した変数、リスト list0 に対して、上記の関数を適用すると、

main = do print $ sumList list0      -- 10 
          print $ productList list0  -- 24

 

c. リストで畳み込み関数

上記二つの関数の形は、よく似ている。違いは以下の具体的な値と関数。

  • リストがのときの値
  • 値を畳み込むための二項演算子

よく似た処理があるなら、それをまとめたい。そのためには、上記二つを「引数」として与える関数を考えれる。この関数を reduceList という名前にするなら、次のように定義できる。

reduceList f z Nil = z
reduceList f z (Cons x xs) = x `f` reduceList f z xs

元の関数から、引数を増やし、具体的な関数を、引数で与えた関数で置き換えるだけ。

この関数を用いて先ほどの総和と総乗を再定義すると、

sumList'     = reduceList (+) 0
productList' = reduceList (*) 1

 

d. 畳み込み関数を利用してリストを返す

総乗・総和の計算は、二項演算子を手段として、要素を一つの値に畳み込み集約する。一つの値に集約できるのは、二項演算子 (+), (*) の型を見ればわかる。

*Main> :t (+)
(+) :: (Num a) => a -> a -> a
*Main> :t (*)
(*) :: (Num a) => a -> a -> a

数値数値を足し合わせたり、掛け合わせると、結果が数値になるため。

ところで、リスト型を定義したときのデータコンストラクタは、

  • 要素
  • リスト

の二つを引数に与えると、リストが生成される二項演算子だった。データコンストラクタの型を確認すると、

*Main> :t Cons
Cons :: a -> List a -> List a

第 1 引数と第 2 引数の型が異なることがわかる。

データコンストラクタは、普通の関数と同じようなもの。(+), (*), Cons を中置記法で書いて比較すると、

*Main> 1 + 2
3
*Main> 1 * 2
2
*Main> 1 `Cons` Nil
Cons 1 Nil

データコンストラクタ Cons は、 (+) や (*) とはちょっと赴きが違うけれど、同じ仲間であることが、形の上ではっきりとする。ということは、総和・総乗を reduceList で定義したときと同じように Cons を reduceList へ与えても問題ない。

では、Cons を reduceList の第1引数として渡した場合、第2引数には何を渡せばいいのだろうか?

reduceList の計算のイメージを List folds as structural transformations を元に、第1引数に (+), 第2引数に 0 を与えた場合で考えたのが下図。

img07-14-2010[1]

これに対して上図の (+) の代わりに Cons を渡した場合、右端に置ける値は何か?

img07-14-2010[2]

先ほど Cons の型を確認したときのことを思い出せば、

*Main> :t Cons
Cons :: a -> List a -> List a

上記 `?’ の場所には List a 型の値を置けることが見てとれる。

img07-14-2010[3]

reduceList 関数において、これで問題ない理由は、Cons の 第2引数 と 返り値 の型が同じであるため。

ところで `?’ に Nil が来れば、与えたリストの要素をそのまま返す copyList 関数が定義できる。

copyList = reduceList Cons Nil

Nil ではなく Cons 1 (Cons 2 … のようなリストが来たなら、リストをリストに追加する appendList が定義できる。

appendList xs ys = reduceList Cons ys xs

もちろん、reduceList 関数を使わなくても、以下のように定義できる。

appendList' Nil xs         = xs
appendList' (Cons x xs) ys = Cons x (appendList' xs ys)

 

e. 要素に関数を適用する map 関数

なぜ関数プログラミングは重要か」 では、reduce 関数から map 関数を導くまで、丁寧に描かれている。ここでは、そこはすっ飛ばし、関数を合成する関数 compose を定義する。

compose f g h = f (g h)

この関数を使った、以下のような計算を考える。

compose Cons (* 2)

この式の型は、

*Main> :t compose Cons (* 2)
compose Cons (* 2) :: (Num t) => t -> List t -> List t

第 1 引数に数値、第 2 引数にリストを与えるとリストが返される。例えば、

*Main> (compose Cons (* 2)) 1 Nil
Cons 2 Nil

よって、compose の第2引数に関数を与える形にして、 reduceList の第1引数に与えることで map 関数が導かれる。

mapList f = reduceList (compose Cons f) Nil

mapList 関数を試してみる。

print $ mapList (* 2) list0 -- Cons 2 (Cons 4 (Cons 6 (Cons 8 Nil)))

もちろん、reduceList を使わなくても、map 関数は以下のように定義できる。

mapList' f Nil         = Nil
mapList' f (Cons x xs) = Cons (f x) (mapList' f xs)

 

f. 要素を抽出する filter 関数

map 関数が定義できたので、次は filter 関数。

ここでは、できるだけ Haskell で用意されている構文を使わないで書いてみたい。そこで、予め if を関数として書いておく。 (cf. if と真偽値 )

if' True  x _ = x
if' False _ y = y

これを用いて、要素を判定する述語を第1引数として与える関数 filterList を定義。 ( cf. 述語 )

filterList p = reduceList filter' Nil
    where
      filter' e l = if' (p e) (Cons e l) l

例えば、2 で割れる要素だけ抽出したい場合は、

print $ filterList (\x -> x `mod` 2 == 0) list0

こちらも map と同じく reduceList を使わずに定義するなら、

filterList' p Nil         = Nil
filterList' p (Cons x xs) = if' (p x) (Cons x filter') filter'
    where
      filter' = filterList' p xs

 

4. ツリーで総和・総乗から、畳み込み関数まで

リストの場合と同じように、ツリーでも以下の流れを踏襲して定義する。 ( filter だけちょっと違うけれど。)

  1. ツリー型を定義
  2. ツリーの要素に対して、「総和・総乗」を求める関数を定義 … (A)
  3. (A) の関数を元にして、抽象化した畳み込み関数を定義
  4. 上記の畳み込み関数を使って以下を定義
    • 「総和・総乗」を再定義
    •   値をコピーする関数を定
    • 要素に関数を定義する関数を定義 ( map )
  5. 特定の要素を抽出する関数を定義 ( filter )

 

a. ツリーを代数的データ型で定義

最初は、ツリーの代数的データ型を定義。

ここで、ツリーは各値を持つノードから成り、ノードはツリーのリストを持つとする。(「なぜ関数プログラミングは重要か」 に書かれていたのと同じ形にした。)

data Tree a = Node a (List (Tree a)) 

これを用いてツリーの値を作成してみる。

tree0 = Node 1 
        (Cons (Node 2 
               (Cons (Node 10 Nil) 
                (Cons (Node 20 Nil) 
                 Nil)))
         (Cons (Node 3 Nil) 
          (Cons (Node 4 Nil) 
           Nil)))

上記の表現だと、全体を把握しにくいので、Tree a 型を Show クラスのインスタンスにして、print 関数で出力したときに見やすく整形して出力されるようにしておく。

instance (Show a) => Show (Tree a) where
    show (Node x Nil) = show x
    show tree0        = show' tree0 0
        where
          show' (Node x trees) n = tabs   ++ 
                                   show x ++ 
                                   showTrees' trees (n+1)
              where
                tabs = replicate n '\t'

                showTrees' Nil n                = ""
                showTrees' (Cons tree1 trees) n = "\n"          ++ 
                                                  show' tree1 n ++ 
                                                  showTrees' trees n

これにより先ほどのツリーは、

*Main> tree0
1
	2
		10
		20
	3
	4

と表示される。

 

b. ツリーで総和、総乗の定義

リストの時と同じように、総和と総乗を定義する。

ノードが保持する値が数値であるとして、ツリー全体の「総和」を求めるには、

sumTree (Node x trees) = x + sumTree' trees
    where
      sumTree' Nil               = 0
      sumTree' (Cons tree trees) = sumTree tree + sumTree' trees

これに対して「総乗」は、

productTree (Node x trees) = x * productTree' trees
    where
      productTree' Nil               = 1
      productTree' (Cons tree trees) = productTree tree * productTree' trees

上記 2 つの関数を試してみる。

print $ sumTree tree0      -- 40
print $ productTree tree0  -- 4800

 

c. ツリーで畳み込み関数 (1)

リストの場合と同じく、畳み込み関数を定義する。ただし、ここでは、ツリーのリストを畳み込むための関数と、その結果となる値と、ツリーのノードを畳み込む関数を、同じもので定義してみる。

reduceTree f z (Node x trees) = x `f` reduceTree' f z trees
    where
      reduceTree' _ z Nil         = z
      reduceTree' f z (Cons t ts) = reduceTree f z t `f` reduceTree' f z ts

これを用いて総和と総乗を再定義。

print $ reduceTree (+) 0 tree0
print $ reduceTree (*) 1 tree0

 

d. ツリーで畳み込み関数 (2)

次に、ツリーの要素に対して何もせず、元のツリーの値を返す関数の定義を試みる。リストのときと同様に考え、reduceTree にツリーのデータコンストラクタを渡せば…

copyTree = reduceTree Node Nil

… としてはダメ。これでは、ツリーをコピーすることができない。理由は上記の定義で、敢えて関数を適用した後の値を書くとするなら、以下のようなツリーを構築しようとしているため。

tree0 = Node 1 
        (Node (Node 2 
               (Node (Node 10 Nil) 
                (Node (Node 20 Nil) 
                 Nil)))
         (Node (Node 3 Nil) 
          (Node (Node 4 Nil) 
           Nil)))

これは、明らかにツリーではない。

ツリーの型は、以下のように、

data Tree a = Node a (List (Tree a)) 

データコンストラクタ Node と、リストのデータコンストラクタから構成されている。よって reduceTree は高階関数として、もう一つデータコンストラクタを受け取る引数を用意しなければならない。

reduceTree f g z (Node x trees0) = x `f` reduceTree' f g z trees0
    where
      reduceTree' _ _ z Nil                 = z
      reduceTree' f g z (Cons tree1 trees1) = reduceTree  f g z tree1 `g` 
                                              reduceTree' f g z trees1

これを使い元のツリーをそのまま返す関数は、

copyTree = reduceTree Node Cons Nil

と定義できる。

総和・総乗を定義するなら、

print $ reduceTree (+) (+) 0 tree0
print $ reduceTree (*) (*) 1 tree0

 

e. 要素に関数を適用する map 関数

全てのノードの保持する値に関数を適用するには、ノードの値に関数を適用できるようにすればよい。よって、畳み込み関数の第1引数に、Node と与えた関数を合成したものを与える。

mapTree f = reduceTree (compose Node f) Cons Nil

試してみる。

*Main> mapTree (* 2) tree0
2
	4
		20
		40
	6
	8

 

f. filter (1) – ツリーからリストに変換した後に抽出する方法

では、要素を抽出するための filter はどうやって定義できるのだろう?うーん… (@_@;

ところで、「ふつうのHaskellプログラミング」(p122) には、Haskell で採用されている「遅延評価」について、次のように述べられている。

評価しなければならない値が存在するとき、実際の計算を値が必要になるまで行わない

( 遅延評価 - Wikipedia より )

また、Haskell で代表的なデータ型である「リスト」については、「インターフェイスを統一できる」 利点があるとして、次のように述べられている。

例えば巨大なツリー構造の全要素を順番にアクセスしたいと考えてみてください。Java で書くなら、ツリーに対するイテレータを用意するでしょう。一方Haskell の場合には、ツリーの要素すべてを含むリストを返す flatten という関数が使われます。

Haskell で用意されている Data.Tree 型を見ると、

flatten :: Tree a -> [a]

という関数が定義されており、返り値はリスト。

リストが遅延評価される Haskell ならば… ツリーの要素をすべて集める flatten 関数を使っても、本当にリストが生成されるのはリストを初めてたぐったときです。 flatten 関数を使ったリストが生成されることはありません。

(同上より)

Scheme:オブジェクト指向表現」 では、「ツリーの要素を辿って関数を適用するコード」が紹介さている。これに対しても、Haskell の遅延評価の観点から次のようなコメントがされている。

tree のトラバースは、要するに与えられた tree のすべてのノードを一列のリストに ならべればよいわけです。

Haskell プログラミング ∼ 純粋関数型言語への誘い∼」 (p.28) には 「Haskell のパターン」として、次のように書かれている。

代数データ型を定義する
そのデータ型を走査する高階関数を書く
高階関数に条件を指定し、必要な部分をリストにする
リストになれば、何でもあり

以上より、ツリーをリストにする関数 flatten を定義してみる。

flatten (Node x trees0) = Cons x (flatten' trees0)
    where
      flatten' Nil                 = Nil
      flatten' (Cons tree1 trees1) = flatten  tree1  `appendList` 
                                     flatten' trees1

この関数と、先ほどリストで定義したフィルタ関数を合成して、以下のように定義できる。

filterTree2List p = filterList p . flatten

この関数を使ってみる。

*Main> filterTree2List (\x -> x `mod` 2 == 0) tree0
Cons 2 (Cons 10 (Cons 20 (Cons 4 Nil)))

 

g. flatten の定義でリストの畳み込み関数を使う

ところで、Haskell で用意されている Data.Tree 型の flatten 関数の定義を見ると、畳み込み関数 foldr が使われている。

flatten :: Tree a -> [a]
flatten t = squish t []
  where squish (Node x ts) xs = x:Prelude.foldr squish xs ts

一見したところ、何でこれで定義できるのかわからなかった。。 (@_@; 特に squish 関数の定義の中で、畳み込み関数を使っており、その第 1 引数に squish を与えるところがイメージできない。

頭の中でイメージできないときは、図を描きながら考えてみる。まず、squish 関数の中の xs は、最初に空リストを与えられて呼出されていることより、リスト であることがわかる。 ts は Tree a 型のデータコンスラクタの定義より [Tree a] 。 よって、先ほどのように畳み込み関数をツリー状にして考えるなら、以下の図のようになる。

img07-21-2010[1]

最初に、右下端の二項演算子を適用する部分に注目。この二項演算子の引数は、squish の定義で見たように第1引数は Tree a 型の値で、第2引数は空リスト。

ところで、定義の 1 行目は以下のように記述されている。

flatten t = squish t []

squish は flatten と比較すると引数が一つ追加され、具体的な値が与えられていることより、

flatten  は汎用的な squish 関数の特殊なケース

であることが読み取れる。

しかし、なぜ flatten が squish の特殊ケースとして定義できるのだろう?上図の青い点線で囲ったところを意識しながら見るとわかるかもしれない。 flatten t が t をリストに変換することに対して、squish t [] は t をリストに変換したものに対して空リストを追加している。つまり、両者は同じ結果を返すことが明白 (?) QQQ

それにしても、どうして上記のような定義ができることを思い付いたのか理解できない。(+_+)

関数を定義するときに、

「この関数はどういった汎用的な関数の特殊ケースであるか?」

ということを常に考えていればいいのだろうか…。

この点に関して、とりあえず横に置いておき、先ほどの flatten を畳み込み関数を使って定義しなおしてみる。

flatten (Node x trees0) = Cons x (reduceList flatten' Nil trees0)
    where
      flatten' tree1 xs = flatten tree1 `appendList` xs

うーん…、動作はするけれど定義の仕方が異なる。 (+_+)

ここで flatten’ の第1引数をデータコンストラクタによるパターンマッチに変更し、上記の appendList 関数を使わず Cons で書いてみる。

flatten (Node x trees0) = Cons x (reduceList flatten' Nil trees0)
    where
      flatten' (Node x tree1) xs = Cons x (reduceList flatten' xs tree1)

上記の太字の部分を見比べると、

Cons x (reduceList flatten' Nil trees0)

は、

Cons x (reduceList flatten' xs tree1)

の特殊なケースであることがわかる。

よって、これをまとめ、最終的に以下のように定義ができるということだったのかな?

flatten (Node x trees0) =  flatten' tree0 Nil
    where
      flatten' (Node x tree1) xs = Cons x (reduceList flatten' xs tree1)

 

h. filter (2) - なるべくツリーの形を保って要素を抽出

先ほどはツリーをリストに変換してから要素を抽出した。別の抽出方法として、ある程度ツリーの形を保ったまま抽出ではできないだろうか?

例えば以下のようなツリーがあった場合、

1
	2
		10
		20
	3
	4

奇数の要素のみを抽出した結果は、

1
	3

偶数の要素を抽出した結果は、

2
	10
	20
4

というような関数を定義したい。

返される値は、ツリーが一つのこともあれば、ツリーのリストであることもある。関数名を filterTree とするなら、Tree a 型の値と要素を抽出するための述語を与えたら、Tree a 型の値のリストを返せばいいので

filterTree :: (a -> Bool) -> Tree a -> List (Tree a)

何も考えずにだらだらと定義すると…

filterTree :: (a -> Bool) -> Tree a -> List (Tree a)
filterTree p (Node x trees0) 
    | p x  == True = Cons (Node x trees') Nil
    | otherwise    = trees'
    where
      trees' = filterTree' trees0
          where
            filterTree' Nil                 = Nil
            filterTree' (Cons tree1 trees1) = filterTree p tree1 
                                              `appendList` 
                                              filterTree' trees1

せっかくなので、畳み込み関数で置き換えると、

filterTree p (Node x trees0) 
    | p x  == True = Cons (Node x trees') Nil
    | otherwise    = trees'
    where
      trees' = reduceList filter' Nil trees0
          where
            filter' tree xs = filterTree p tree `appendList` xs

ここから、Data.Tree 型の flatten 関数の定義 と同じように、より汎用的な関数の特殊な形という形式に定義を置き換えることはできるだろうか?

上記の tree’ をインライン化し、filter’ 関数の第1引数をデータコンストラクタによるパターンマッチに置き換えると次のようになる。

filterTree p (Node x trees0) 
    | p x  == True = Cons (Node x $ filterTree' trees0) Nil
    | otherwise    = filterTree' trees0
    where
      filterTree' = reduceList filter' Nil
          where
            filter' (Node x trees1) xs 
                | p x == True = Cons (Node x $ filterTree' trees1) xs
                | otherwise   = filterTree' trees1 `appendList` xs

よく見ると、上部の太字の定義は、下部の太字の定義の特殊なケースであることがわかる。

よって、これをまとめると以下のように書ける。

filterTree p trees0 = filter' trees0 Nil
    where
      filter' (Node x trees1) xs
          | p x  == True = Cons (Node x $ filterTree' trees1) xs
          | otherwise    = filterTree' trees1 `appendList` xs
          where
            filterTree' = reduceList filter' Nil

上記の関数を使う前に List a 型の導出インスタンス宣言を削除し、出力の方法を変える。

instance (Show a) => Show (List a) where
    show Nil          = ""
    show (Cons x Nil) = show x
    show (Cons x xs)  = show x ++ "\n" ++ show xs

試してみる。

*Main> filterTree (\x -> x `mod` 2 /= 0) tree0
1
	3
*Main> filterTree (\x -> x `mod` 2 == 0) tree0
2
	10
	20
4

 

関連記事

 

参考サイト