ATND アテンド β PRODUCED BY RECRUIT

イベント開催支援ツール:ATND(アテンド)

ログイン or 新規登録

Haskell Annual Meeting Autumn.jp 2009

HAMA.jp 2009

09_formal_original
日時 :
2009/09/19 10:00 to 2009/09/23 21:30
定員 :
-
会場 :
online meeting (everywhere/どこでも)
URL :
http://atnd.org/events/1048
管理者 :
ikegami__ ikegami__
ハッシュタグ :
-
住所が入力されていません

Thank you with best regards! The meeting was closed. See logs at IRCLogs@GoogleDocs.



This event is an informal, grassroots collaborative Haskell coding festival; broadcasts on the internet.

日本語で読みたい人は、ただちに、このリンクをたどるべし

Contents

About



This event is the first occasion of the online meeting; for who live or stay in Japan; about the programming language Haskell with talks and discussion.

However, you can join the meeting whenever you please, in Japanese Standard Time (JST), which is 9 hours ahead of UTC.

Haskell Annual Meeting Autumn 2009 (abbr. HAMA.jp 2009) will be held September 19-23 at the freenode IRC channels. It is open to all. All you need is basic knowledge of Haskell, wishes to learn, and a project you’re excited to help with (or project of your own to work on), finally waking up at local time where you are. A few people in Japan, who will join the meeting, maybe not going to bed, but still continue to talk with you, probably.

There will be lots of hacking, some talks (informal or formal), and of course, fun! We apologize to you that we cannot serve any good food nor drink.

We will create some channels for the meeting at “irc.freenode.net”, and names of each channel have been decided. See Channels section for the channel names. Lambdabot will be stayed during the meeting. Thanks Conrad for this good proposal.

Logs of each channel will be kept and published at the organizer’s blog. However, IP-address of each member has to be erased.

The registration is not needed; it will be described below in detail. However, if you want to give a live talk using USTREAM.tv, slides or messages, please contact the organizer. We are pleased to reserve a session for your presentation or kindly messages. The address of the organizer will be written at the Contact section.

News



September 19



The channel names on irc.freenode.net have been decided.

Schedule has been changed: Talk1 will start at 13:30.

August 28

Program has been announced.

August 2

We propose two Haskell problems to share the same topics with us.

July 19

The first announce as a draft.

Registration



The registration is not needed. The event is an online meeting at IRC channel of freenode at some channels. Names of each channel will be announced later at this web page.

Program



September 19-22, 2009, 10 a.m. – 10 p.m, JST, GMT+9. The last day September 23, we will plan to closing session, for planning the meeting in next year and meeting for reviewing 3 p.m – half of 4 p.m, JST, GMT+9.

Event time-lines and program will be fixed this web page before September 6.

date (GMT) 01:00 – 02:30 (GMT) 06:00 – 07:30 (GMT) 10:00 – 12:30 (GMT) later until 01:00 (GMT)
2009-09-19 (GMT)Opening sessionSession for newbiesQuestions and Answers about programming in HaskellNight session for Japanese and You
2009-09-20 (GMT)How to start your project in Haskell (about the latest Cabal, Haskell Platform and etc.)Talks 1 will start at 04:30(GMT).Talks 2Night session for Japanese and You
2009-09-21 (GMT)ReservedReservedReservedReserved
2009-09-22 (GMT)Free discussionHow to debug and test in HaskellFree discussionNight session for Japanese and You
2009-09-23 (GMT)Final lightening talks & Closing sessionBusiness meeting

Talks

Some or All talks will be given in Japanese. However, we will try to our best for translating in English about each talk at the IRC channel. Don’t hesitate to about asking a question, please.

Talks 1

2009-09-20 04:30 (GMT)
Speaker

keigoi

Title

Type level programming in Haskell and its application

Abstract

keigoi will give an introduction to type-level programming in Haskell and its advantage of strong type safety. Also he will present an implementation of the session types. As an application, an implementation of an SMTP client using type-level programming will be appeared. He may introduction another topics about HaskellDB and Takusen.

Talks 2

2009-09-20 10:00–10:30 (GMT)
Speaker

smly

Title

How to compress data in Haskell

Abstract

A case study of how to enjoy compressed data in Haskell.

2009-09-20 10:45–(GMT)
Speaker

Sakai

Title

Introduction to categorical programming

Abstract

TBA. The following papers and an theoretical webpage will be introduced.

IRC server and channels

We discuss on the IRC server ‘irc.freenode.net’. There are some channels for this event. However, we have not decided the prefix of name of each channel.

#HAMAYA
The hall of this event.
#HAMAYA-bots
Sandbox of bots.
#HAMAYA-stage
A channel for presentation
#HAMAYA-staff
Staff room.

Logs at each channel will be published at somewhere.

Location



Many attendees live in Japan. You do not need to visit Japan, because this meeting is online.

Preparations



  • Your favorite editor to write Haskell code.
  • The latest GHC
  • Web browser to watch presentations

  • IRC client for discussion, which has UTF-8 encoding and decoding

Contact



For any questions, you can always send an email to IKEGAMI Daisuke, who is one of the organizers. The address is "ikegami.da" ++ chr 64 ++ "gmail.com". Please do not hesitate to ask your question about this meeting.

Note

The below is written in Japanese about the same things, and you do not have to read them. Unfortunately, you cannot write a comment at the bottom of this page, because you have to do several complex steps, which is written only Japanese… Otherwise could you send an email to the organizer, please.

Two Haskell Assignments



We propose two Haskell assignments for you, who has no own project. One is to create an IRC bot in Haskell. Another is several questions of a combinatorial problem, called ‘finding the minimum spanning tree from a graph’.

The aim of this proposal is to share topics with us. Therefore, you do not have to complete nor submit your exercise to us. Please do your work instead and join our meeting freely. By the way, we are going to show the following two jobs:

  1. Create an IRC bot
  2. Finding the minimum spanning tree

Create an IRC bot

This project is simple: create an IRC bot and run it on ‘irc.freenode.net’.

Note that please do not run an incomplete bot on the public network ‘irc.freenode.net’. Instead, run an IRC server on your computer, and test enough to rely entirely your bot, please.

During this meeting, we will provide a channel for our bots, and discuss about features and techniques.

Notice again: The lambdabot, which is made by Don Stewart, will stay every channel. You do not need to make it. Please keep the following manners:

  • Be polite social behavior.
  • Talk with ‘notice’ instead of ‘privmsg’ by your bot on IRC. In other word, your bot should not use any ‘privmsg’ message.
  • Do not reply any ‘notice’.

During the meeting, you can stay your bot at only #HAMA-bots.

Finding the minimum spanning tree from a graph

The minimum spanning tree problem is a well-known problem in graph theory.

  1. implement several algorithms to find the minimum spanning tree for a given graph.
  2. implement ditto with parallel computations.
  3. how to estimate the efficiency? (e.g. draw a graph, or show the complexity, and so on.)

The scope of this problem is how to write a procedual algorithm in Haskell as fast as in another language, such as C.

Weekly Quotes of Zen



Here, we quote words of Zen in Japanese.

28 August

前三三後三三

前三三後三三 is a composite Chinese Kanji word which means we are brimful of hope. This is the final quotation for this event.

22 August

本来無一物

本来無一物 is a composite Chinese Kanji word in a poem. The poem is very popular in Zen, because it represents the foundation of Zen. The meaning is ‘Everything come out of nothing, really!’ Zen does not apply any logic nor experience for dogma, but Zen has only one doctrine : Zen Buddhist has to ignore evidence, instead be impressed by nature. We choose this word fifth since we believe programmer and non-programmer will join us at the event.

19 August

一期一会

一期一会 is a composite Kanji word and pronounced ‘ichi go ichi e’ in Japanese. ‘一’ means the one, ‘期’ a chance, and ‘会’ a meet, respectively. This word is very popular in Japan, and translated as ‘We have a chance to meet at once.’ In 2009, this event makes a chance to meet several Japanese Haskell programmers and many beginners. The Zen word does not mean ‘Opportunity knocks only once’, but, I say, this event is an occasion to extend activity of Haskell community in Japan.

18 August

惺々著

惺々著 is a composite Kanji word in Chinese and pronounced “sei sei jaku” in Japanese. They have three Kanji characters; ‘惺’, ‘々’, and ‘著’. Since ‘々’ is the special character which is adjective and means the previous Kanji character repeatedly, we see the word as another word ‘惺惺著’ that has only two characters. ‘惺’ means ‘Wake up’, on the other hand, ‘著’ is the emphasis word. Finally, we can translate ‘惺々著’ as ‘Wake up! Devote yourself!’ We choose the word thirdly, because the deadline of a proposal of this event is the next sunday in JST. Please send your comment to the organizer. Otherwise, happy Haskell hacking!

7 August

当機

当機 is a composite Kanji word and pronounced “tōki”. They have two Kanji characters; ‘当’ and ‘機’. In the sense of Zen in Japanese, ‘当’ means ‘right now’, respectively, ‘機’ means ‘a chance’.
The word ‘当機’ suggests that you shall get the chance right now.

We choose the word secondly, because we wish you will not miss any chance. If you find this event and decide to join, we are welcome you, and celebrate you with the lucky keyword ‘当機’.

On the other hand, ‘当機’ is also a technical word for the pilot of aircraft, which means the plain. The pilot says this word when the plain will take off; ‘当機はまもなく離陸いたします。シートベルトをお締めください’ – translated frankly – ‘The plain will take off at the airport. Fasten your safety belt, please.’

Now you realize that you don’t miss the chance (i.e. this event), and will visit Japan via the Internet in the next month. Von voyage!

3 August

○ is pronounced “ensō” in Japanese, which you can see this picture about Zen at the en.wikipedia.org. This symbol means the shape of the world quite simply. Because it means also the state of completeness, we choose the first symbol of this event.


大見出し



このイベントは終了しました。ログはIRCLogs@GoogleDocsにあるので見てね。

何をするの?



おじいちゃん、おばあちゃんを大切にしよう!それから、プログラミング言語 Haskell について、発表や議論をオンラインでつなごうぜ、という催しです。初心者歓迎。秋の味覚とともに、みんなでまったりと話しあいましょう。

目的は?



「Haskell って名前は聞いたことあるけど、使ったことないよ」って人から、「Haskell 大好き」って人まで、いろんな人がいるよね。そういう皆が集まって話し合うのは楽しそうだと思わない?

この機会に、Haskell についての疑問誤解が解けたり、『何か(打つゲームとか踏むゲームとかメールサーバとか)を作ったよ!とかいう発表』があればいいと思います。あと、Haskell と関係したりしなかったりする新しい何かを掴みましょう。

参加資格?



参加資格なんてありません!自分のことを初心者だと思っている人も、普通の人も、そうでない人も、皆、歓迎します。二度書くけど、「このイベントに参加する」の手順を踏む必要もありません!

「話題についていけないよ」とか「なにそれ日本語でok」ってことがないように、複数の会場(IRC チャンネル)を用意します。

皆が「礼儀正しく」、ただし、「わからないことはすぐ聞く!」の態度を守れば、きっと共有できてなかったことが共有されるはず、と考えています。

参加できない人は?

せっかくの四連休。参加できない気持ち、わかります。後日、このイベントのログを公開しますので、それをお読みになってくだされば。

ニュース

日時 告知内容
2009-09-19

IRC のチャンネル名が決まりました。

9/20 午後の開始時間が 15:00 から 13:30 に変更になりました。

2009-09-02

申し込みくださった発表を載せました。まだ、かろうじてスロットは残っているので、喋りたい人は申し出てください。よろしくお願いします。

2009-08-28

プログラムが決まりました。あと、IRC ログを保存することを書きました。

2009-08-01

IRC についての説明を追加しました。それから、
いくつかのイベントと夏休みの課題のお知らせ!

2009-07-28

ocaml-nagoya 夏合宿と接触しました。また、タイムテーブルを少しずつ埋めています。変更はできますので早めにお申し付けください。

2009-07-26


普通の人向けのタイムテーブルを仮に埋めました。今後イベントの提案がない場合は、微調整しつつこのまま行きます。8/23 締め切りのイベントの提案や質問を引き続きお待ちしております。

2009-07-25

コメント欄で、皆さんの日時調整をやりますよ、という告知をしました。

2009-07-19

文面の修正、特に帰国子女様のための記述がなされました。

2009-07-17

残念なお知らせです、タイトルロゴ(仮)が掲載されました。引き続き改悪される予定です。

2009-07-12

最初のアナウンスです!

参加登録について



ATND のこのイベントに登録する必要はありません。ただし、このページのコメントの読み書きには登録が必要です。コメント欄では、主にスケジュール調整を行います。

このイベントで発表したい人や、集会の日時に希望がある人、発表しないけど自己アピールをしたい人は、ATND のこのイベントに参加する(赤いボタン「このイベントに参加する」を押して、その指示にしたがう)必要があります。発表したい人は、発表の手続きがあるので、最後までよく読んでね。

また口頭ライブ発表を行うひとは、直前の金曜日(9/18)のリハーサルにも参加してくれると嬉しいです。できるだけ。

イベントの当日直前に、このページに詳細が書かれますので、また見にきてください。具体的には、どうすれば発表を見ることができるか、議論するにはどうするか、それからスケジュール表が確定しています。

スケジュール



自称初心者から普通のひと向けのタイムテーブル

午前(10:00-11:30)午後(15:00-16:30)夕方から晩にかけて(19:00-21:30)
9/18(金)特になし特になしオンライン発表リハーサル(発表者の方々へ : リハーサル無理だったら本番でどんといきましょう)
9/19(土)OpeningHaskellの初歩(モナドだって初歩のうち)Q & A
9/20(日)Haskell のプロジェクトの始め方発表 1 13:30-(時間が変
更になりました!
)
発表・ライトニングトーク 2
9/21(月):敬老の日ReservedReservedReserved
9/22(火):国民の休日Free discussionHaskell のテストデバッグ術Free discussion
9/23(水):秋分の日Final lightening talks & Closing sessionMeeting for reviewing & planning for this event in the next year

質問は随時受け付けますが、特に初日の夕方は「質問攻め」の時間を予約しました。

普通じゃないひと向けのタイムテーブル

午前(10:00-11:30)午後(15:00-16:30)夕方から晩にかけて(19:00-21:30)深夜から早朝にかけて
9/18(金)特になし特になしオンライン発表リハーサルEve of the festival
9/19(土)Opening皆の質問に答えてください皆の質問に答えてくださいNight session
9/20(日)Free discussionTalks(13:30-)TalksNight session
9/21(月):敬老の日ReservedReservedReservedNight session
9/22(火):国民の休日Free DiscussionHow to debug and test in HaskellTechnical lightening talks寝ましょう。
9/23(水):秋分の日Final lightening talks & Closing sessionMeeting for reviewing (post event evaluation) and planning for this event in the next year

ふたつのタイムテーブルは独立していなくて、同時並行で行われます。だから、ついていけなくなる前に質問を!わかってる人は質問に答えてくれるボランティア精神をよろしくお願いします。

場所



どこかに集まるわけではありません。が、団体発表される方々はお好きなところにお集まりください。

もしも、日時や場所をこのページで通知したければ、ATND のこのイベントに参加する手順を踏んだ上で、コメントを書けばいいです。コメントは、書いた人が編集したり削除したりできます。

あるいは、制作委員会にメールをくだされば、このページを編集します。

発表一覧

発表 1

2009-09-20 13:30–
発表者

keigoi

タイトル

Haskellによる型レベルプログラミングと、その応用例で型付きDSLの実装について

アブストラクト

Haskellによる型レベルプログラミングと、その応用例で
型付きDSLの実装について話したいと思います。具体的には、セッション型の実装と型安全な(?)SMTPクライアントの例を出します。
できれば、その他の話題(HaskellDBやTakusenとか)にも触れます。

発表・ライトニングトーク

2009-09-20 19:00–19:30
発表者

smly

タイトル

Haskellで圧縮

アブストラクト

圧縮されたデータを Haskell で処理する際のケーススタディ

2009-09-20 19:45–
発表者

Sakai

タイトル


Categorical Programming について紹介

アブストラクト

予定している元ネタ:

各団体の集まる日時と場所



まだ何も聞いてないよ!

IRC サーバとチャンネル名



IRC サーバは “irc.freenode.net” を使います。チャンネルは複数作ります。

#HAMAYA

みんな(帰国子女さまも含む)が集まる最初の場所。最初の日の最初のタイムテーブルで、簡単な自己紹介をしてもらいます。自己紹介したくない人は、一言 ‘pass’ とつぶやいてくれればいいです。

その後は、帰国子女様(がくれば)との交流の場所になります。とくに、Night session でこの場所を使います。

#HAMAYA-jp

日本語みたいな日本語で会話する場所。帰国子女様には申し訳ありません。

#HAMAYA-newbie

自分は初心者だ! という方、および質問に答えてくれるボランティアの方がたむろう場所です。ボランティア急募。

#HAMAYA-cafe

またーり雑談する。Haskell に限らず、どんな話題でもどうぞ。

#HAMAYA-staff

このイベントの運営者が常駐しています。なんかやっかいそうな人とか、トラブルなどがおきたら、ここに報告してください。

#HAMAYA-stage

IRC で発表する人のためのチャンネルです。+v で発表者のみが喋ります。その他の皆さんは、この部屋に join して、発表を聞きます。質疑応答は、#HAMAYA や #HAMAYA-jp でおねがいします。

#HAMAYA-bots

このページで告知した夏休みの宿題の bot が集まる場所です。ここ以外に自作 bot は join しないでほしいです。ご協力お願いします。

その他、この期間内のイベント(ウェブアプリ制作部隊とか)をやりたい人は #HAMAYA-name_of_event を勝手に作っていただいて構いません。Lambda bot が必要なら、出張します。

後日、IRC channel のログは公開する予定です。ただし、皆様の IP address は削除します(IRC の仕様で、IP address は逆引きされて表示されてしまいます)。また、不適当なログは制作委員会のほうで適当に編集されます。あらかじめご了承ください。匿名希望の方は、匿名 nick と怪しいネットワーク経由でお越し下さい。保存場所は、まだ決まっていません。

事前の準備



  1. 空白とタブの違いを目で見て確認できるエディタ
  2. Haskell インタプリタ/コンパイラ ghc 最新版

    GHC 本家からインストール

    GHC のページの “Current Stable Release”


    Haskell Platform

    もしくは、Haskell Platformの人柱になる(お勧めはしません)

  3. SWF を表示できるウェブブラウザ
  4. IRC クライアント (※ UTF-8 に対応しているクライアントに限る)

以上を用意してください。
IRC (Internet Relay Chat) についてわからない子は、自分で調べてね。 UTF-8 を使うことができる IRC クライアントを用意してください。

IRC のサーバ名ならびにチャンネル名は、イベント間近に、このページで発表します。IRCサーバとチャンネルの項目をお読みください。

発表申し込み



発表したい人、団体は ATND の「このイベントに参加する」の手続きを踏んでください。また、発表申し込みフォームを制作委員会にメールで提出してください。発表申し込みフォームは、この下に書いてあります。提出期限は 8/23(日) です。面倒だけど許してね。

発表申し込みは締め切りましたが、駆け込みで喋りたい人は、こちらに言ってもらえればなんとかします。

発表の方法は大きく分けて、2 種類を考えています:

  1. ライブ口頭発表(USTREAMなどを利用)
  2. 資料による発表(SlideShare, Google ドキュメント, ソースレポジトリなど)

ライブ口頭発表は、あらかじめスケジュールに時間を割り当てます。

資料による発表は、発表者の資料へのリンクをこのページに作ります。イベントの間、いつでも IRC でみんなと議論することができます。

発表申し込みフォーム



メールの Subject に HAMA.jp 2009” と書いてくれると大変助かるのでよろしくお願いします。

  • 名前またはニックネーム
  • 発表タイトルと概要
  • 発表時間

    • 10分
    • 30分 + 質疑応答 10 分

    • その他(何分かを連絡)

長い名前などは、制作委員会が短くする場合があります。あらかじめご了承ください。

イベントの提案



発表フォームに収まらないイベントの提案などありましたら、制作委員会にメールを出すか、あるいはこのページのコメントを書いてください。コメントを書くには、ATND の「このイベントに参加する」手続きを踏む必要があります。

イベント一覧

提案されたイベントの一覧です。一人ででも、団体ででも取り組んでください!イベントはもうすでに始まっています。9月まで待たずにどんどん進めちゃいましょう!

  1. Webサービスを Haskell で
    1. つくる
    2. 利用する

メンバーとの連絡や、具体的になにをするかなどは、Haskell-jp Wiki の HAMA.jp 2009 のページを利用してください。Haskell-jp Wiki を運営して下さる方に感謝します。

他イベントとの協力

同時期に開催されるイベントがありましたら、私たちは喜んで協力したいと考えています(※ただし、プログラミングに関すること、あるいは Haskell に限る)。タイムテーブルの変更も考えます。制作委員会までご連絡ください。

当日付近のイベントは、はなずきん様の作成されている IT 勉強会カレンダーでご確認ください。はなずきん様には、スケジュール表を作っていただいて感謝しております。

ocaml-nagoya 夏合宿と日程が重なったため、交流のための日時などを交渉しています。プログラムが確定するまえなら、他のイベントとの交流も可能ですので、制作委員会までご連絡ください。

なお、このイベントが終わると、次は Implementation and Application of Functional Programming (IFL) 2009 が始まります!

制作委員会への連絡先



メイルあどれす ikegami.da アーッと gmail.com まで。
いただいたメールアドレスは、このイベントの目的のみに使います。

このページのコメントはこまめに見るつもりですが、反応は遅れる可能性があります。

Twitter や、Skype、MSN などは発表申し込みをしたことになりません。メールで!

このページのコメントに関する注意



コメントの読み書きには、ATND の「このイベントに参加する」手続きが必須です。まったりとコメントを書いてください。

夏休みの課題



Haskell 秋の例会は 9 月ですが、それまで待ちきれないあなたのために、ふたつの課題を制作委員会が提案します。答えの提出義務はないので、気楽に取り組んでください。また、すでに個人のプロジェクトを持っている方はそれを優先すればいいです。複数人で取り組みたくなったら、イベントとして提案してください。

もちろん、参加するひとの義務でもなんでもないです。ただ、「暇だなーっ、だけど何していいかよくわかんない」っていう人に何かあげたかったんだ。それだけ。このイベント(HAMA.jp 2009)自体は 初心者大歓迎です。課題をやらない人も、イベント当日近辺にこのページをもう一度見ればいい。

Haskell を使って IRC ボットを作りましょう



この課題を行うには、守っていただきたい条件が二つあります。最初の一つは、プログラムを始める前に、自分のマシンに IRC サーバをインストールするということです。もう一つは一番最後に言います。

「何を言っているのか、わからないよ!」という人は、別にこの課題をやらなくてもいいです。9 月のイベントでお会いしましょう。そのときに質問をすればいいんじゃないかなと思います。

自分のマシンにインストールする IRC サーバはGigazine さんの2008年01月28日の記事にある、Inspire IRCd – The Stable C++ Modular IRCd なんかがよいのではないかなと思います。
これは、Windows系, *nix および MacOSX で動くんだそうです。なお、これをインストールして何か実害がでても当イベント制作委員会は責任をとれません。というか、ごめんなさい。

もちろん、 IRC サーバはいろいろな実装があるのでお好きなものを選んでいただければよいのですが。Gigazine さんの Windows におけるインストール手順が丁寧だったのでお借りしました。*nix や MacOSX の人は自分でなんでもするよね。

次にやることは、 UTF-8 に対応した IRC クライアントを用意することです。これもまたたくさんあるので、好きなのを選べばよいかと。

気をつけていただきたいのは、このクライアントで、自分のサーバに接続することです。今まで説明してきたことは、一言でいえば、自分のマシンに IRC bot の開発環境と遊び場を作る、ということです。開発当初は、無限ループしたり、IRC のマナーを守らない bot を作ってしまうかもしれません。これはよくあることです。ですから、まず、自分のマシンで動かしてみて大丈夫だなあ、というところまで完成したら合格です。未完成のまま、既存の IRC ネットワークには接続しないでください。

Haskell 秋の年会 2009 では、会場が主に IRC なので、皆さんが完成させた IRC bot が集う部屋を準備します。イベントまでに完成しているといいですね。あるいは、ある程度しあげて、イベントでコメントをもらうのもありだと思います。

なお、IRC bot が集う部屋でも UTF-8 が用いられます。privmsg や topic などの解析をするときは、文字コードにも気をつけてください。

とにかく、あなたのアイデア次第で面白い IRC bot を作ってみてください。もしも、困難に出会ったら、それをメモしておいて秋の年会イベントで質問すればいいと思います。

最後に、言い忘れていた二番目の約束を言います。IRC bot の発言は privmsg ではなく notice を使ってください。また、あらゆる notice に対して返答してはなりません。理由は、IRC プロトコルを定めたRFC 1459 IRC プロトコルにあります。なお、訳文はタイトルが NTICE になってしまってますが、これは NOTICE の誤りです。

では、皆さんの健闘を祈ります。なお、Don Stewart の lambdabot は、もうすでにいますので、それ以外の bot でお願いします。

グラフから全域木を取り出すアルゴリズムとその評価



上から順番に解いていくと、最後までたどりつけるような工夫はしたつもりです。

  1. データ構造としてのを Haskell で定義してください。木とは、頂点と辺の二種類のデータからなります。

    ここで紹介した「木」の説明のうち、ページの下半分の数式は、好きな人だけ読めばいいです。

    要するに「木」は、なんとなく確かに漢字としての木みたいな形になっていて、定義を言うと「サイクルを持たない連結なグラフ」ということになります。何がサイクルで何が連結なグラフかを定義しだすときりがないのでやめておきます。その代わりに、木のページの図 1 から 6 までを見てください。横にふたつ以上ならんでいる図では、その一つ一つを木だと思います。ふたつ離れた木を合わせると、くっつかない、つまり連結ではなくなってしまいます。

    たとえば、このページの左上のロゴのλがよっつある図で、○を頂点とし、○と○を結ぶ直線を辺だとすると、これは「木」です。

    [余談]
    木とは何かをすでに知っているひとは GHC についてくる Data.Tree を使ってもいいです。そういう子は「木」だけでなく「森」についても知っているかもしれないので、その場合はこの課題を「森」に拡張してくれていいです、がんばれ。[余談ここまで]

    実は Haskell において、データ構造としての木を定義する方法はいくつもあります。できれば一通りではなく、複数の定義を考えてみましょう。




  2. Haskell でグラフのデータ構造を定義する、のは容易ではないので、代わりに GHC の標準ライブラリ Data.Graph を見て、どんなことができるか、いろいろ試しましょう。たとえば、どうすれば、左上のλのグラフを描くことができるでしょうか。(○を頂点と思い、直線を辺と思います)

    これでは物足りないひとは、自分でグラフのデータ構造を定義してみてください。定義の方法は複数あります。できるだけ様々な定義を用意しましょう。

  3. 全域木とは、与えられた連結なグラフの全ての頂点をもっている木を言います。別の言葉でいうと、与えられた連結なグラフには、サイクルがあったとしても、全域木は、そのサイクルの一部のみを使い、グラフ全部の頂点を通る(サイクルを持たない)木なのです。たとえば、左上のロゴでλが4つある図の○を頂点と思い直線を辺と思えば、すでに全域木になっているグラフです。なんと。
    全域木を説明しているページの□に対する全域木などの例も見ましょう。

    グラフから全域木をひとつみつける関数 spanningTree :: Graph -> Tree を実装しましょう。実装は一通りではありません。時間/空間計算量の小さな関数をどうやって実装したらよいでしょうか。また、計算量の評価はどうやったらいいでしょうか?(ヒント: GHC のプロファイラを使いましょう、使わなくても理詰めで計算量を導きだすことができるかもしれません)

    前の課題に戻り、木やグラフのデータ構造を上手に定義しなおすのも手です。実はこの課題は、データ構造がアルゴリズムと密接に関係がある例なのです。

  4. 次は、グラフが与えられたときに、各辺に非負整数をくっつける関数 weightedGraph :: Graph -> [Word] -> WeightedGraph を作りましょう。そのためには、データ構造 WeightedGraph を作らなければなりません。また、関数 weightedGraph は、二番目の引数 [Word] が一番目の引数 Graph の辺の順番の付け方と一致していないと意味がないことに注意してください。Graph の枝の順番はどうやってつければいいでしょうか?

    なお Word は、GHC の標準ライブラリ Data.Word にあり、Word は非負整数を表します。データ構造 WeightedGraph の定義は一通りとは限りません。頭を柔らかくして臨みましょう。

  5. 非負整数が枝についているグラフ WeightedGraph の全域木を求めましょう。ただし、あらゆる全域木のなかで、枝の非負整数の和を極小にしてください。 そのような極小全域木を求める関数 minimumSpanningTree :: WeightedGraph -> Tree を作りましょう。

    関数 minimumSpanningTree :: WeightedGraph -> Tree の実装もまた一通りではありません。時間/空間計算量の小さな関数をどうやって実装したらよいでしょうか。また、計算量の評価はどうやったらいいでしょうか?

  6. 次は、Haskell 独特の手法を用います。並行計算に使う関数 parと、ghc に与える引数 -threaded を用いて、並行計算で 関数 spanningTree および minimumSpanningTree を実装してください。core が二つ以上ないと面白くないですが、dual core などのマシンを持ってるひとは、ぜひ試してみてください。計算量に違いは現れるでしょうか。なお、HaskellWiki に簡単なサンプルがありますので、そちらを読むのもお勧めします。

  7. 最後に、これは今までの課題とは無関係ですが、複数の実装があったときの計算量を視覚化する試みを行ってみてください。カラフルなグラフなどができあがると望ましいです。この課題の評価はヒューマンインターフェースからの観点とユーザビリティの観点の二つがなされます。

なお、この課題はきわめて数学的に見えますが、その応用は幅広く、知っておいて損はないことだらけだ、と制作委員会は考えました。数学嫌いな子も英語嫌いな子も、格闘してくれると嬉しいです。

「何を言っているのか、わからないよ!」という人は、別にこの課題をやらなくてもいいです。9 月のイベントでお会いしましょう。そのときに質問をすればいいんじゃないかなと思います。

これ以上課題が増えることはありません!安心してください。それでは、秋のイベントでお会いしましょう。このページはちょくちょく更新されますので、たまに訪れるなりするといいと思います。

ほぼ週替わり禅語



昭和八十四年八月二十八日


前三三後三三




「三三」とは、満ち足りている様を言う。此れ、即ち、我々は全面に満ち足りており、不足のないことを意味する。Haskell も Haskell でないものも、満ち足りていることを体感せよ。

HAMA.jp に参加者が限りなく訪れ、満ち足りますよう。

『碧巌録』より抜粋。

昭和八十四年八月二十二日

本来無一物

本来無一物である。Haskell も Haskell でないものにも打ち込むべし。何処惹塵埃。

『六祖壇経』より引用。

昭和八十四年八月十九日

一期一会

皆と一緒に Haskell で遊ぶことができるのは、この連休しかないのかもしれません。

昭和八十四年八月十八日

惺々著

「起きているか!」常に刃を研がねば、その刀は用を為さず。

公案集『無門関』より引用。

昭和八十四年八月七日

当機

当機を逸すること勿れ。感覚を失して即断実行すべからず。耳で見よ、目で聞け。一喝。

昭和八十四年八月三日

円相に、自らの不足を見よ

  • このコメントはイベント参加者と主催者のみ閲覧/投稿できます。
  • comment RSS:RSS
  • このイベントにハッシュタグは設定されていません
掲載されるイベント情報は、利用者の皆様によりご提供いただくものであり、株式会社リクルートホールディングスは本情報の正確性や内容について、一切保証するものではございません。詳しくは利用規約をご参照ください。