https://wiki.haskell.org/api.php?action=feedcontributions&user=Liyang&feedformat=atomHaskellWiki - User contributions [en]2019-10-15T22:34:00ZUser contributionsMediaWiki 1.27.4https://wiki.haskell.org/index.php?title=HakkuTaikai/Projects&diff=42186HakkuTaikai/Projects2011-09-24T06:33:05Z<p>Liyang: /* update websockets */ correct spec version</p>
<hr />
<div>== Sharing your code ==<br />
<br />
If you need a place to host a project so that others can help with it, we suggest<br />
[http://github.com github], which offers free hosting for public git repositories. If you're using darcs, [http://patch-tag.com/ patch-tag] is just dandy as well. You can also apply for an account on [http://community.haskell.org/admin/ the community server].<br />
<br />
== Projects ==<br />
<br />
If you have a project that you want to work on at the Hackathon, please describe it here.<br />
<br />
Since Hackathons are great for teamwork, consider joining one of the projects mentioned below. If you're interested in one of these projects, add your name to the list of hackers under that project.<br />
<br />
=== containers ===<br />
<br />
Johan Tibell has [http://blog.johantibell.com/2011/05/new-release-of-unordered-containers.html recently been doing some work] on [http://hackage.haskell.org/package/unordered-containers unordered-containers], with an eventual goal of unifying the current {Int,Hash,}Map interfaces. Would be nice to have some form of unboxed containers in there too.<br />
<br />
* Liyang<br />
<br />
=== time ===<br />
<br />
The current implementation of time uses lots of Integers internally along with realToFrac, which makes it much slower than necessary. Thinking about moving to an Int64-based representation while still being able to represent any conceivable dates & times.<br />
<br />
* Liyang<br />
* Kazu<br />
* Mikhail<br />
<br />
=== unordered-containers ===<br />
<br />
I anticipate to make a new release of the package just before ICFP, with a completely rewritten implementation. I'd like to spend some time after the release to flesh out the API a bit more.<br />
<br />
* Johan Tibell<br />
<br />
=== HiggsSet ===<br />
<br />
I recently released a package called [http://hackage.haskell.org/package/HiggsSet-0.1 HiggsSet]. Although it works for me in a production environment, I would sleep much better if it were properly tested. So, what needs to be done is a test/benchmark suite.<br />
<br />
* Lars Petersen<br />
<br />
=== TKYProf ===<br />
<br />
I released an alpha version of [http://blog.foldr.in/tkyprof-a-web-based-interactive-visualizer-fo TKYProf], which is a visualizer for GHC profiling. I'd like to take care of the [https://github.com/maoe/tkyprof/issues existing issues]. The public repository is on [https://github.com/maoe/tkyprof GitHub].<br />
<br />
* Mitsutoshi Aoe<br />
<br />
=== carettah ===<br />
<br />
A presentation tool writtten with Haskell.<br />
I would like to cleanup code, and upload to the Debian repository.<br />
The public repository is on [https://gitorious.org/carettah gitorious].<br />
<br />
* Kiwamu Okabe<br />
<br />
=== language-java-revised ===<br />
<br />
Challenge to implement Practical Java Parser and Pretty Printer supporting annotation and new specifications of Java. I want use this for code generation.<br />
<br />
* Kei Hibino<br />
<br />
=== update websockets ===<br />
<br />
Update the "[http://hackage.haskell.org/package/websockets websockets]" package to the latest version of the websockets protocol ([http://tools.ietf.org/html/draft-ietf-hybi-thewebsocketprotocol-10 hybi-10], used by e.g. chrome 14)<br />
<br />
* Steffen<br />
<br />
<!-- Copy this template<br />
=== Project name ===<br />
<br />
I am a project. Love me.<br />
<br />
* Hacker 1<br />
* Hacker 2<br />
--></div>Liyanghttps://wiki.haskell.org/index.php?title=HakkuTaikai/Projects&diff=42185HakkuTaikai/Projects2011-09-24T06:29:52Z<p>Liyang: /* update websockets */</p>
<hr />
<div>== Sharing your code ==<br />
<br />
If you need a place to host a project so that others can help with it, we suggest<br />
[http://github.com github], which offers free hosting for public git repositories. If you're using darcs, [http://patch-tag.com/ patch-tag] is just dandy as well. You can also apply for an account on [http://community.haskell.org/admin/ the community server].<br />
<br />
== Projects ==<br />
<br />
If you have a project that you want to work on at the Hackathon, please describe it here.<br />
<br />
Since Hackathons are great for teamwork, consider joining one of the projects mentioned below. If you're interested in one of these projects, add your name to the list of hackers under that project.<br />
<br />
=== containers ===<br />
<br />
Johan Tibell has [http://blog.johantibell.com/2011/05/new-release-of-unordered-containers.html recently been doing some work] on [http://hackage.haskell.org/package/unordered-containers unordered-containers], with an eventual goal of unifying the current {Int,Hash,}Map interfaces. Would be nice to have some form of unboxed containers in there too.<br />
<br />
* Liyang<br />
<br />
=== time ===<br />
<br />
The current implementation of time uses lots of Integers internally along with realToFrac, which makes it much slower than necessary. Thinking about moving to an Int64-based representation while still being able to represent any conceivable dates & times.<br />
<br />
* Liyang<br />
* Kazu<br />
* Mikhail<br />
<br />
=== unordered-containers ===<br />
<br />
I anticipate to make a new release of the package just before ICFP, with a completely rewritten implementation. I'd like to spend some time after the release to flesh out the API a bit more.<br />
<br />
* Johan Tibell<br />
<br />
=== HiggsSet ===<br />
<br />
I recently released a package called [http://hackage.haskell.org/package/HiggsSet-0.1 HiggsSet]. Although it works for me in a production environment, I would sleep much better if it were properly tested. So, what needs to be done is a test/benchmark suite.<br />
<br />
* Lars Petersen<br />
<br />
=== TKYProf ===<br />
<br />
I released an alpha version of [http://blog.foldr.in/tkyprof-a-web-based-interactive-visualizer-fo TKYProf], which is a visualizer for GHC profiling. I'd like to take care of the [https://github.com/maoe/tkyprof/issues existing issues]. The public repository is on [https://github.com/maoe/tkyprof GitHub].<br />
<br />
* Mitsutoshi Aoe<br />
<br />
=== carettah ===<br />
<br />
A presentation tool writtten with Haskell.<br />
I would like to cleanup code, and upload to the Debian repository.<br />
The public repository is on [https://gitorious.org/carettah gitorious].<br />
<br />
* Kiwamu Okabe<br />
<br />
=== language-java-revised ===<br />
<br />
Challenge to implement Practical Java Parser and Pretty Printer supporting annotation and new specifications of Java. I want use this for code generation.<br />
<br />
* Kei Hibino<br />
<br />
=== update websockets ===<br />
<br />
Update the "[http://hackage.haskell.org/package/websockets websockets]" package to the latest version of the websockets protocol (draft-ietf-hybi-thewebsocketprotocol-06, used by e.g. chrome 14)<br />
<br />
* Steffen<br />
<br />
<!-- Copy this template<br />
=== Project name ===<br />
<br />
I am a project. Love me.<br />
<br />
* Hacker 1<br />
* Hacker 2<br />
--></div>Liyanghttps://wiki.haskell.org/index.php?title=HakkuTaikai/Attendees&diff=42184HakkuTaikai/Attendees2011-09-24T05:54:26Z<p>Liyang: /* HakkuTaikai Attendees */</p>
<hr />
<div>= HakkuTaikai Attendees =<br />
<br />
The venue is not open to the public on the day of the Hackathon, so we must submit a list of names to security. If you're name is not on the list, you may not be admitted.<br />
<br />
If you do not wish to announce your attendance in public, please email haskathon★liyang.hu instead.<br />
<br />
{| class="wikitable"<br />
!Nickname<br />
!Real Name<br />
!Affiliation<br />
!Mobile<br />
|-<br />
| liyang<br />
| Liyang HU<br />
| Tsuru Capital LLC<br />
| +81 80 4361 1307<br />
|-<br />
| kfish<br />
| [[User:ConradParker|Conrad Parker]]<br />
| Tsuru Capital SG Pte Ltd<br />
| +81 80 4162 1307<br />
|-<br />
| erikde/m3ga<br />
| [[User:Erik de Castro Lopo|Erik de Castro Lopo]]<br />
| bCODE Pty Ltd<br />
| not public<br />
|-<br />
| kazu<br />
| Kazu Yamamoto<br />
| IIJ<br />
| not public<br />
|-<br />
| tibbe<br />
| Johan Tibell<br />
| Google<br />
| not public<br />
|-<br />
| lpeterse<br />
| Lars Petersen<br />
| -<br />
| not public<br />
|-<br />
| TacticalGrace<br />
| [[User:chak|Manuel Chakravarty]]<br />
| University of New South Wales<br />
| not public<br />
|-<br />
| [[User:shelarcy|shelarcy]]<br />
| KIDO Takahiro<br />
| -<br />
| -<br />
|-<br />
| tcard<br />
| Travis Cardwell<br />
| Yuzu Technology<br />
| -<br />
|-<br />
| dcoutts<br />
| Duncan Coutts<br />
| Well-Typed<br />
| -<br />
|-<br />
| zenzike<br />
| Nicolas Wu<br />
| Well-Typed<br />
| -<br />
|-<br />
| exoticbaboon<br />
| Remo STORNI<br />
| University of Tokyo<br />
| -<br />
|-<br />
| juhp<br />
| Jens Petersen<br />
| Red Hat<br />
| -<br />
|-<br />
| tanakh<br />
| Hideyuki Tanaka<br />
| Preferred Infrastructure<br />
| -<br />
|-<br />
| khibino<br />
| Kei Hibino<br />
| ASAHI Net<br />
| -<br />
|-<br />
| master_q<br />
| Kiwamu Okabe<br />
| Ricoh<br />
| -<br />
|-<br />
| dmorneau<br />
| Dominic MORNEAU<br />
| -<br />
| -<br />
|-<br />
| imsut<br />
| Ken Kawamoto<br />
| -<br />
| -<br />
|-<br />
| jystic<br />
| Jacob Stanley<br />
| Fugro<br />
| -<br />
|-<br />
| maoe<br />
| Mitsutoshi Aoe<br />
| -<br />
| -<br />
|-<br />
| nobsun<br />
| Nobuo Yamashita<br />
| -<br />
| -<br />
|-<br />
| mkotha<br />
| Takano Akio<br />
| Tsuru Capital<br />
| -<br />
|-<br />
| nobu_toyofuku<br />
| Chikanobu Toyofuku<br />
| -<br />
| -<br />
|-<br />
| manpacket<br />
| Mikhail Baikov<br />
| Tsuru Capital LLC<br />
| -<br />
|-<br />
| andrew<br />
| Andrew Richards<br />
| Tsuru Capital LLC<br />
| -<br />
|-<br />
| alang<br />
| Alex Lang<br />
| Tsuru Capital LLC<br />
| -<br />
|-<br />
| lostman<br />
| Maciej Wos<br />
| -<br />
| -<br />
|-<br />
| steffen<br />
| Steffen Schuldenzucker<br />
| Tsuru Capital LLC<br />
| -<br />
|}</div>Liyanghttps://wiki.haskell.org/index.php?title=HakkuTaikai/Attendees&diff=42168HakkuTaikai/Attendees2011-09-22T13:50:01Z<p>Liyang: /* HakkuTaikai Attendees */ receive manpacket</p>
<hr />
<div>= HakkuTaikai Attendees =<br />
<br />
The venue is not open to the public on the day of the Hackathon, so we must submit a list of names to security. If you're name is not on the list, you may not be admitted.<br />
<br />
If you do not wish to announce your attendance in public, please email haskathon★liyang.hu instead.<br />
<br />
{| class="wikitable"<br />
!Nickname<br />
!Real Name<br />
!Affiliation<br />
!Mobile<br />
|-<br />
| liyang<br />
| Liyang HU<br />
| Tsuru Capital LLC<br />
| +81 80 4361 1307<br />
|-<br />
| kfish<br />
| [[User:ConradParker|Conrad Parker]]<br />
| Tsuru Capital SG Pte Ltd<br />
| +81 80 4162 1307<br />
|-<br />
| erikde/m3ga<br />
| [[User:Erik de Castro Lopo|Erik de Castro Lopo]]<br />
| bCODE Pty Ltd<br />
| not public<br />
|-<br />
| kazu<br />
| Kazu Yamamoto<br />
| IIJ<br />
| not public<br />
|-<br />
| tibbe<br />
| Johan Tibell<br />
| Google<br />
| not public<br />
|-<br />
| lpeterse<br />
| Lars Petersen<br />
| -<br />
| not public<br />
|-<br />
| TacticalGrace<br />
| [[User:chak|Manuel Chakravarty]]<br />
| University of New South Wales<br />
| not public<br />
|-<br />
| [[User:shelarcy|shelarcy]]<br />
| KIDO Takahiro<br />
| -<br />
| -<br />
|-<br />
| tcard<br />
| Travis Cardwell<br />
| Yuzu Technology<br />
| -<br />
|-<br />
| dcoutts<br />
| Duncan Coutts<br />
| Well-Typed<br />
| -<br />
|-<br />
| zenzike<br />
| Nicolas Wu<br />
| Well-Typed<br />
| -<br />
|-<br />
| exoticbaboon<br />
| Remo STORNI<br />
| University of Tokyo<br />
| -<br />
|-<br />
| juhp<br />
| Jens Petersen<br />
| Red Hat<br />
| -<br />
|-<br />
| tanakh<br />
| Hideyuki Tanaka<br />
| Preferred Infrastructure<br />
| -<br />
|-<br />
| khibino<br />
| Kei Hibino<br />
| ASAHI Net<br />
| -<br />
|-<br />
| master_q<br />
| Kiwamu Okabe<br />
| Ricoh<br />
| -<br />
|-<br />
| dmorneau<br />
| Dominic MORNEAU<br />
| -<br />
| -<br />
|-<br />
| imsut<br />
| Ken Kawamoto<br />
| -<br />
| -<br />
|-<br />
| jystic<br />
| Jacob Stanley<br />
| Fugro<br />
| -<br />
|-<br />
| maoe<br />
| Mitsutoshi Aoe<br />
| -<br />
| -<br />
|-<br />
| nobsun<br />
| Nobuo Yamashita<br />
| -<br />
| -<br />
|-<br />
| mkotha<br />
| Takano Akio<br />
| Tsuru Capital<br />
| -<br />
|-<br />
| nobu_toyofuku<br />
| Chikanobu Toyofuku<br />
| -<br />
| -<br />
|-<br />
| manpacket<br />
| Mikhail Baikov<br />
| Tsuru Capital LLC<br />
| -<br />
|-<br />
| andrew<br />
| Andrew Richards<br />
| Tsuru Capital LLC<br />
| -<br />
|-<br />
|}</div>Liyanghttps://wiki.haskell.org/index.php?title=HakkuTaikai/Projects&diff=42145HakkuTaikai/Projects2011-09-20T23:43:52Z<p>Liyang: /* time */</p>
<hr />
<div>== Sharing your code ==<br />
<br />
If you need a place to host a project so that others can help with it, we suggest<br />
[http://github.com github], which offers free hosting for public git repositories. If you're using darcs, [http://patch-tag.com/ patch-tag] is just dandy as well. You can also apply for an account on [http://community.haskell.org/admin/ the community server].<br />
<br />
== Projects ==<br />
<br />
If you have a project that you want to work on at the Hackathon, please describe it here.<br />
<br />
Since Hackathons are great for teamwork, consider joining one of the projects mentioned below. If you're interested in one of these projects, add your name to the list of hackers under that project.<br />
<br />
=== containers ===<br />
<br />
Johan Tibell has [http://blog.johantibell.com/2011/05/new-release-of-unordered-containers.html recently been doing some work] on [http://hackage.haskell.org/package/unordered-containers unordered-containers], with an eventual goal of unifying the current {Int,Hash,}Map interfaces. Would be nice to have some form of unboxed containers in there too.<br />
<br />
* Liyang<br />
<br />
=== time ===<br />
<br />
The current implementation of time uses lots of Integers internally along with realToFrac, which makes it much slower than necessary. Thinking about moving to an Int64-based representation while still being able to represent any conceivable dates & times.<br />
<br />
* Liyang<br />
* Kazu<br />
* Mikhail<br />
<br />
=== unordered-containers ===<br />
<br />
I anticipate to make a new release of the package just before ICFP, with a completely rewritten implementation. I'd like to spend some time after the release to flesh out the API a bit more.<br />
<br />
* Johan Tibell<br />
<br />
=== HiggsSet ===<br />
<br />
I recently released a package called [http://hackage.haskell.org/package/HiggsSet-0.1 HiggsSet]. Although it works for me in a production environment, I would sleep much better if it were properly tested. So, what needs to be done is a test/benchmark suite.<br />
<br />
* Lars Petersen<br />
<br />
=== TKYProf ===<br />
<br />
I released an alpha version of [http://blog.foldr.in/tkyprof-a-web-based-interactive-visualizer-fo TKYProf], which is a visualizer for GHC profiling. I'd like to take care of the [https://github.com/maoe/tkyprof/issues existing issues]. The public repository is on [https://github.com/maoe/tkyprof GitHub].<br />
<br />
* Mitsutoshi Aoe<br />
<br />
=== carettah ===<br />
<br />
A presentation tool writtten with Haskell.<br />
I would like to cleanup code, and upload to the Debian repository.<br />
The public repository is on [https://gitorious.org/carettah gitorious].<br />
<br />
* Kiwamu Okabe<br />
<br />
<!-- Copy this template<br />
=== Project name ===<br />
<br />
I am a project. Love me.<br />
<br />
* Hacker 1<br />
* Hacker 2<br />
--></div>Liyanghttps://wiki.haskell.org/index.php?title=HakkuTaikai&diff=41775HakkuTaikai2011-08-26T08:10:14Z<p>Liyang: /* HakkuTaikai: Haskell Hackathon */ More prominent links to HS and HIW.</p>
<hr />
<div>= HakkuTaikai: Haskell Hackathon =<br />
<br />
Sunday, 2011-09-25, National Institute of Informatics, Tokyo, Japan<br />
<br />
== About ==<br />
<br />
The Haskell Hackathon is an international, grassroots collaborative coding<br />
festival with a simple focus: build and improve Haskell libraries, tools,<br />
and infrastructure.<br />
<br />
HakkuTaikai (aka Gotta Hack 'Em All, Hakkushima & other rejected names) will<br />
be held on the Sunday after [http://icfpconference.org/icfp2011/ ICFP]/[http://haskell.org/haskell-symposium/2011/ HS]/[http://haskell.org/haskellwiki/HaskellImplementorsWorkshop/2011 HIW]/[http://cufp.org/conference CUFP] has concluded. Given that we have<br />
only one day for this hackathon, there won't be time for talks or presentations.<br />
<br />
Potential attendees may also be interested in the [http://haskell.org/haskell-symposium/2011/ Haskell Symposium] and [http://haskell.org/haskellwiki/HaskellImplementorsWorkshop/2011 Haskell Implementors' Workshop].<br />
<br />
== News ==<br />
<br />
* IRC channel: [irc://irc.freenode.net#haskathon #haskathon on FreeNode] ([http://webchat.freenode.net?channels=haskathon WebChat])<br />
* Twitter HashTag: [http://twitter.com/search/%23haskathon #haskathon]<br />
<br />
== Registration ==<br />
<br />
'''Venue security requires a list of attendees' names.'''<br />
If you will (likely) be attending, please [[/Attendees|list yourself as an<br />
attendee]]. Registration is free (gratis). Then check out the [[/Projects|projects page]].<br />
<br />
== Whe(n|re) ==<br />
<br />
* Time: from 09:00, on Sunday the 25th of September, 2011.<br />
* Location: [http://maps.google.com/maps?q=東京都千代田区一ツ橋2-1-2 National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo-to 〒101-8430]<br />
* アクセス: 〒101-8430 東京都千代田区一ツ橋2-1-2 国立情報学研究所<br />
* Room: 1208 (12th floor of NII)<br />
<br />
If anyone wishes to carry on hacking after Sunday, we should always be able to find somewhere at short notice.<br />
<br />
== Accommodation ==<br />
<br />
Let us know if your accommodation costs for the hackathon would not be<br />
covered as part of the conference, and you would like somewhere to crash<br />
or help with finding low-cost hostels & c.<br />
<br />
If you live locally and can offer accommodation (e.g. a floor or sofa bed or<br />
spare futon to crash on), do let us know too.<br />
<br />
== Preparations ==<br />
<br />
=== What to bring ===<br />
<br />
* A laptop with wireless facilities, and appropriate power adaptors for Japan (A,B; 100V, 50Hz; basically the same plug as USA)<br />
* Ethernet access will be difficult. We can probably set up our own wired LAN if necessary. Please let us know if you think you need wired access.<br />
<br />
=== Before you arrive ===<br />
<br />
* Pick out a couple of projects to work on and familiarise yourself with them, or bring your own project(s) to work on. See the [[/Projects|projects page]] for a list of projects others plan to work on. If you plan to work on your own project, be sure to list it on the [[/Projects|projects page]] and set up a public repository if you don't already have one, so that other people can help hack on your project.<br />
<br />
* Install an up-to-date Haskell toolchain: at least the latest haskell-platform and cabal-install, or preferably the latest GHC (7.2.1 at time of writing). If you don't already have these installed (or need to install from scratch on the laptop you're bringing), the easiest way is the [http://hackage.haskell.org/platform/ Haskell Platform].<br />
<br />
== Organisers ==<br />
<br />
* Liyang HU <haskathon★liyang.hu>, +81 80 4361 1307<br />
* Zhenjiang HU <hu★nii.ac.jp><br />
* Conrad Parker (kfish) <conrad★tsurucapital.com><br />
<br />
[[Category:Community]]<br />
[[Category:Events]]<br />
[[Category:Hackathon]]</div>Liyanghttps://wiki.haskell.org/index.php?title=HakkuTaikai&diff=41774HakkuTaikai2011-08-26T08:07:12Z<p>Liyang: /* Registration */ is gratis.</p>
<hr />
<div>= HakkuTaikai: Haskell Hackathon =<br />
<br />
Sunday, 2011-09-25, National Institute of Informatics, Tokyo, Japan<br />
<br />
== About ==<br />
<br />
The Haskell Hackathon is an international, grassroots collaborative coding<br />
festival with a simple focus: build and improve Haskell libraries, tools,<br />
and infrastructure.<br />
<br />
HakkuTaikai (aka Gotta Hack 'Em All, Hakkushima & other rejected names) will<br />
be held on the Sunday after [http://icfpconference.org/icfp2011/ ICFP]/[http://haskell.org/haskell-symposium/2011/ HS]/[http://haskell.org/haskellwiki/HaskellImplementorsWorkshop/2011 HIW]/[http://cufp.org/conference CUFP] has concluded. Given that we have<br />
only one day for this hackathon, there won't be time for talks or presentations.<br />
<br />
== News ==<br />
<br />
* IRC channel: [irc://irc.freenode.net#haskathon #haskathon on FreeNode] ([http://webchat.freenode.net?channels=haskathon WebChat])<br />
* Twitter HashTag: [http://twitter.com/search/%23haskathon #haskathon]<br />
<br />
== Registration ==<br />
<br />
'''Venue security requires a list of attendees' names.'''<br />
If you will (likely) be attending, please [[/Attendees|list yourself as an<br />
attendee]]. Registration is free (gratis). Then check out the [[/Projects|projects page]].<br />
<br />
== Whe(n|re) ==<br />
<br />
* Time: from 09:00, on Sunday the 25th of September, 2011.<br />
* Location: [http://maps.google.com/maps?q=東京都千代田区一ツ橋2-1-2 National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo-to 〒101-8430]<br />
* アクセス: 〒101-8430 東京都千代田区一ツ橋2-1-2 国立情報学研究所<br />
* Room: 1208 (12th floor of NII)<br />
<br />
If anyone wishes to carry on hacking after Sunday, we should always be able to find somewhere at short notice.<br />
<br />
== Accommodation ==<br />
<br />
Let us know if your accommodation costs for the hackathon would not be<br />
covered as part of the conference, and you would like somewhere to crash<br />
or help with finding low-cost hostels & c.<br />
<br />
If you live locally and can offer accommodation (e.g. a floor or sofa bed or<br />
spare futon to crash on), do let us know too.<br />
<br />
== Preparations ==<br />
<br />
=== What to bring ===<br />
<br />
* A laptop with wireless facilities, and appropriate power adaptors for Japan (A,B; 100V, 50Hz; basically the same plug as USA)<br />
* Ethernet access will be difficult. We can probably set up our own wired LAN if necessary. Please let us know if you think you need wired access.<br />
<br />
=== Before you arrive ===<br />
<br />
* Pick out a couple of projects to work on and familiarise yourself with them, or bring your own project(s) to work on. See the [[/Projects|projects page]] for a list of projects others plan to work on. If you plan to work on your own project, be sure to list it on the [[/Projects|projects page]] and set up a public repository if you don't already have one, so that other people can help hack on your project.<br />
<br />
* Install an up-to-date Haskell toolchain: at least the latest haskell-platform and cabal-install, or preferably the latest GHC (7.2.1 at time of writing). If you don't already have these installed (or need to install from scratch on the laptop you're bringing), the easiest way is the [http://hackage.haskell.org/platform/ Haskell Platform].<br />
<br />
== Organisers ==<br />
<br />
* Liyang HU <haskathon★liyang.hu>, +81 80 4361 1307<br />
* Zhenjiang HU <hu★nii.ac.jp><br />
* Conrad Parker (kfish) <conrad★tsurucapital.com><br />
<br />
[[Category:Community]]<br />
[[Category:Events]]<br />
[[Category:Hackathon]]</div>Liyanghttps://wiki.haskell.org/index.php?title=HakkuTaikai&diff=41773HakkuTaikai2011-08-26T08:05:18Z<p>Liyang: /* About */ HI Workshop, not Meeting; added Haskell Symposium, and links.</p>
<hr />
<div>= HakkuTaikai: Haskell Hackathon =<br />
<br />
Sunday, 2011-09-25, National Institute of Informatics, Tokyo, Japan<br />
<br />
== About ==<br />
<br />
The Haskell Hackathon is an international, grassroots collaborative coding<br />
festival with a simple focus: build and improve Haskell libraries, tools,<br />
and infrastructure.<br />
<br />
HakkuTaikai (aka Gotta Hack 'Em All, Hakkushima & other rejected names) will<br />
be held on the Sunday after [http://icfpconference.org/icfp2011/ ICFP]/[http://haskell.org/haskell-symposium/2011/ HS]/[http://haskell.org/haskellwiki/HaskellImplementorsWorkshop/2011 HIW]/[http://cufp.org/conference CUFP] has concluded. Given that we have<br />
only one day for this hackathon, there won't be time for talks or presentations.<br />
<br />
== News ==<br />
<br />
* IRC channel: [irc://irc.freenode.net#haskathon #haskathon on FreeNode] ([http://webchat.freenode.net?channels=haskathon WebChat])<br />
* Twitter HashTag: [http://twitter.com/search/%23haskathon #haskathon]<br />
<br />
== Registration ==<br />
<br />
'''Venue security requires a list of attendees' names.'''<br />
If you will (likely) be attending, please [[/Attendees|list yourself as an<br />
attendee]]. Then check out the [[/Projects|projects page]].<br />
<br />
== Whe(n|re) ==<br />
<br />
* Time: from 09:00, on Sunday the 25th of September, 2011.<br />
* Location: [http://maps.google.com/maps?q=東京都千代田区一ツ橋2-1-2 National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo-to 〒101-8430]<br />
* アクセス: 〒101-8430 東京都千代田区一ツ橋2-1-2 国立情報学研究所<br />
* Room: 1208 (12th floor of NII)<br />
<br />
If anyone wishes to carry on hacking after Sunday, we should always be able to find somewhere at short notice.<br />
<br />
== Accommodation ==<br />
<br />
Let us know if your accommodation costs for the hackathon would not be<br />
covered as part of the conference, and you would like somewhere to crash<br />
or help with finding low-cost hostels & c.<br />
<br />
If you live locally and can offer accommodation (e.g. a floor or sofa bed or<br />
spare futon to crash on), do let us know too.<br />
<br />
== Preparations ==<br />
<br />
=== What to bring ===<br />
<br />
* A laptop with wireless facilities, and appropriate power adaptors for Japan (A,B; 100V, 50Hz; basically the same plug as USA)<br />
* Ethernet access will be difficult. We can probably set up our own wired LAN if necessary. Please let us know if you think you need wired access.<br />
<br />
=== Before you arrive ===<br />
<br />
* Pick out a couple of projects to work on and familiarise yourself with them, or bring your own project(s) to work on. See the [[/Projects|projects page]] for a list of projects others plan to work on. If you plan to work on your own project, be sure to list it on the [[/Projects|projects page]] and set up a public repository if you don't already have one, so that other people can help hack on your project.<br />
<br />
* Install an up-to-date Haskell toolchain: at least the latest haskell-platform and cabal-install, or preferably the latest GHC (7.2.1 at time of writing). If you don't already have these installed (or need to install from scratch on the laptop you're bringing), the easiest way is the [http://hackage.haskell.org/platform/ Haskell Platform].<br />
<br />
== Organisers ==<br />
<br />
* Liyang HU <haskathon★liyang.hu>, +81 80 4361 1307<br />
* Zhenjiang HU <hu★nii.ac.jp><br />
* Conrad Parker (kfish) <conrad★tsurucapital.com><br />
<br />
[[Category:Community]]<br />
[[Category:Events]]<br />
[[Category:Hackathon]]</div>Liyanghttps://wiki.haskell.org/index.php?title=Template:Main/Events&diff=41772Template:Main/Events2011-08-26T06:11:09Z<p>Liyang: ICFP and co-located Haskell events</p>
<hr />
<div><div class="subtitle">Upcoming Events</div><br />
;[http://icfpconference.org/icfp2011/ ACM SIGPLAN International Conference on Functional Programming (ICFP)]<br />
:September 19–21 (Mon–Wed), 2011, Tokyo, Japan. Co-located with:<br />
:* [http://flolac.iis.sinica.edu.tw/wgp11/doku.php?id=start Workshop on Generic Programming (WGP)]: September 18th (Sun)<br />
:* [http://haskell.org/haskell-symposium/2011/ Haskell Symposium]: September 22nd (Thu)<br />
:* [[HaskellImplementorsWorkshop/2011|Haskell Implementors' Workshop]]: September 23rd (Fri)<br />
:* [http://cufp.org/conference Commercial Users of FP (CUFP)]: September 22nd–24th (Thu–Fri: Tutorials, Sat: Talks)<br />
:* [[HakkuTaikai|HakkuTaikai—Tokyo Hackathon]]: September 25th (Sun)<br />
;[http://www.ittc.ku.edu/ifl2011/ 23rd Symposium on Implementation and Application of Functional Languages.]<br />
:October 3-5, 2011, Lawrence, KS<br />
:October 7, 2011, Leipzig, Germany<br />
;[http://portal.imn.htwk-leipzig.de/events/hal6-haskell-workshop HaL6: Haskell in Leipzig]<br />
<br />
<div class="subtitle">Recent Events</div><br />
<br />
;[http://www.utrechtsummerschool.nl/index.php?type=courses&code=H9 3rd Summerschool on Applied Functional Programming]<br />
:August 15-26, 2011, Utrecht, the Netherlands<br />
;[[CamHac|Cambridge Hackathon]]<br />
:August 12-14, 2011, Cambridge, UK<br />
;[[HacPDX-II|HacPDX: Portland Hackathon]]<br />
:July 22-24, 2011, Portland, OR<br />
;[http://goo.gl/kp4Bv SF Bay Area Haskell User Group: Iteratees]<br />
:July 13, 2011 @ 7pm, San Francisco, CA<br />
;[http://goo.gl/gLEqE SF Bay Area Haskell User Group: Multithreaded code verification using Haskell]<br />
:May 18, 2011 @ 7pm, San Francisco, CA<br />
;[http://goo.gl/MVsKy SF Bay Area Haskell User Group: Writing dynamically linked libraries in Haskell]<br />
:April 20, 2011 @ 7pm, San Francisco, CA<br />
;[http://goo.gl/tG1Wn SF Bay Area Haskell User Group]<br />
:March 16, 2011 @ 7pm, San Francisco, CA<br />
;[[BayHac2011|SF Bay Area Hackaton]]<br />
:February 11-13, 2011, Mountain View, California<br />
;[http://goo.gl/3ppzV SF Bay Area Haskell User Group]<br />
:February 9, 2011 @ 7pm, San Francisco, CA<br />
;[http://goo.gl/ijlfS SF Bay Area Haskell User Group]<br />
:January 12, 2011 @ 7pm, San Francisco, CA<br />
;[http://caes.ewi.utwente.nl/External/NLFP/E/ Dutch Functional Programming Day] :January 7, 2011, Twente University, the Netherlands<br />
;[http://www.haskell.org/haskellwiki/Ghent_Functional_Programming_Group/BelHac BelHac]<br />
:November 5-7, 2010, Ghent, Belgium<br />
;[http://goo.gl/1KPa Erik Meijer: “Fundamentalist Functional Programming”]<br />
:November 3, 2010 @ 7pm, San Francisco, CA<br />
;[http://haskell.org/haskellwiki/LtU-Kiev/Hackathon Kiev Hackathon]<br />
:October 16-17, 2010, Kiev, Ukraine</div>Liyanghttps://wiki.haskell.org/index.php?title=Template:Main/Events&diff=41771Template:Main/Events2011-08-26T05:53:59Z<p>Liyang: Move expired 'Upcoming' events to 'Recent'.</p>
<hr />
<div><div class="subtitle">Upcoming Events</div><br />
;[http://www.ittc.ku.edu/ifl2011/ 23rd Symposium on Implementation and Application of Functional Languages.]<br />
:October 3-5, 2011, Lawrence, KS<br />
:October 7, 2011, Leipzig, Germany<br />
;[http://portal.imn.htwk-leipzig.de/events/hal6-haskell-workshop HaL6: Haskell in Leipzig]<br />
<br />
<div class="subtitle">Recent Events</div><br />
<br />
;[http://www.utrechtsummerschool.nl/index.php?type=courses&code=H9 3rd Summerschool on Applied Functional Programming]<br />
:August 15-26, 2011, Utrecht, the Netherlands<br />
;[[CamHac|Cambridge Hackathon]]<br />
:August 12-14, 2011, Cambridge, UK<br />
;[[HacPDX-II|HacPDX: Portland Hackathon]]<br />
:July 22-24, 2011, Portland, OR<br />
;[http://goo.gl/kp4Bv SF Bay Area Haskell User Group: Iteratees]<br />
:July 13, 2011 @ 7pm, San Francisco, CA<br />
;[http://goo.gl/gLEqE SF Bay Area Haskell User Group: Multithreaded code verification using Haskell]<br />
:May 18, 2011 @ 7pm, San Francisco, CA<br />
;[http://goo.gl/MVsKy SF Bay Area Haskell User Group: Writing dynamically linked libraries in Haskell]<br />
:April 20, 2011 @ 7pm, San Francisco, CA<br />
;[http://goo.gl/tG1Wn SF Bay Area Haskell User Group]<br />
:March 16, 2011 @ 7pm, San Francisco, CA<br />
;[[BayHac2011|SF Bay Area Hackaton]]<br />
:February 11-13, 2011, Mountain View, California<br />
;[http://goo.gl/3ppzV SF Bay Area Haskell User Group]<br />
:February 9, 2011 @ 7pm, San Francisco, CA<br />
;[http://goo.gl/ijlfS SF Bay Area Haskell User Group]<br />
:January 12, 2011 @ 7pm, San Francisco, CA<br />
;[http://caes.ewi.utwente.nl/External/NLFP/E/ Dutch Functional Programming Day] :January 7, 2011, Twente University, the Netherlands<br />
;[http://www.haskell.org/haskellwiki/Ghent_Functional_Programming_Group/BelHac BelHac]<br />
:November 5-7, 2010, Ghent, Belgium<br />
;[http://goo.gl/1KPa Erik Meijer: “Fundamentalist Functional Programming”]<br />
:November 3, 2010 @ 7pm, San Francisco, CA<br />
;[http://haskell.org/haskellwiki/LtU-Kiev/Hackathon Kiev Hackathon]<br />
:October 16-17, 2010, Kiev, Ukraine</div>Liyanghttps://wiki.haskell.org/index.php?title=HakkuTaikai&diff=41757HakkuTaikai2011-08-25T10:00:55Z<p>Liyang: /* Whe(n|re) */</p>
<hr />
<div>= HakkuTaikai: Haskell Hackathon =<br />
<br />
Sunday, 2011-09-25, National Institute of Informatics, Tokyo, Japan<br />
<br />
== About ==<br />
<br />
The Haskell Hackathon is an international, grassroots collaborative coding<br />
festival with a simple focus: build and improve Haskell libraries, tools,<br />
and infrastructure.<br />
<br />
HakkuTaikai (aka Gotta Hack 'Em All, Hakkushima & other rejected names) will<br />
be held on the Sunday after ICFP/HIM/CUFP has concluded. Given that we have<br />
only one day for this hackathon, there won't be time for talks or presentations.<br />
<br />
== News ==<br />
<br />
* IRC channel: [irc://irc.freenode.net#haskathon #haskathon on FreeNode] ([http://webchat.freenode.net?channels=haskathon WebChat])<br />
* Twitter HashTag: [http://twitter.com/search/%23haskathon #haskathon]<br />
<br />
== Registration ==<br />
<br />
If you will (likely) be attending, please [[/Attendees|list yourself as an<br />
attendee]]. Then check out the [[/Projects|projects page]].<br />
<br />
== Whe(n|re) ==<br />
<br />
* Time: from 09:00, on Sunday the 25th of September, 2011.<br />
* Location: [http://maps.google.com/maps?q=東京都千代田区一ツ橋2-1-2 National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo-to 〒101-8430]<br />
* アクセス: 〒101-8430 東京都千代田区一ツ橋2-1-2 国立情報学研究所<br />
* Room: 1208 (12th floor of NII)<br />
<br />
If anyone wishes to carry on hacking after Sunday, we should always be able to find somewhere at short notice.<br />
<br />
== Accommodation ==<br />
<br />
Let us know if your accommodation costs for the hackathon would not be<br />
covered as part of the conference, and you would like somewhere to crash<br />
or help with finding low-cost hostels & c.<br />
<br />
If you live locally and can offer accommodation (e.g. a floor or sofa bed or<br />
spare futon to crash on), do let us know too.<br />
<br />
== Preparations ==<br />
<br />
=== What to bring ===<br />
<br />
* A laptop with wireless facilities, and appropriate power adaptors for Japan (A,B; 100V, 50Hz; basically the same plug as USA)<br />
* Ethernet access will be difficult. We can probably set up our own wired LAN if necessary. Please let us know if you think you need wired access.<br />
<br />
=== Before you arrive ===<br />
<br />
* Pick out a couple of projects to work on and familiarise yourself with them, or bring your own project(s) to work on. See the [[/Projects|projects page]] for a list of projects others plan to work on. If you plan to work on your own project, be sure to list it on the [[/Projects|projects page]] and set up a public repository if you don't already have one, so that other people can help hack on your project.<br />
<br />
* Install an up-to-date Haskell toolchain: at least the latest haskell-platform and cabal-install, or preferably the latest GHC (7.2.1 at time of writing). If you don't already have these installed (or need to install from scratch on the laptop you're bringing), the easiest way is the [http://hackage.haskell.org/platform/ Haskell Platform].<br />
<br />
== Organisers ==<br />
<br />
* Liyang HU <haskathon★liyang.hu>, +81 80 4361 1307<br />
* Zhenjiang HU <hu★nii.ac.jp><br />
* Conrad Parker (kfish) <conrad★tsurucapital.com><br />
<br />
[[Category:Community]]<br />
[[Category:Events]]<br />
[[Category:Hackathon]]</div>Liyanghttps://wiki.haskell.org/index.php?title=HakkuTaikai&diff=41756HakkuTaikai2011-08-25T10:00:24Z<p>Liyang: /* About */</p>
<hr />
<div>= HakkuTaikai: Haskell Hackathon =<br />
<br />
Sunday, 2011-09-25, National Institute of Informatics, Tokyo, Japan<br />
<br />
== About ==<br />
<br />
The Haskell Hackathon is an international, grassroots collaborative coding<br />
festival with a simple focus: build and improve Haskell libraries, tools,<br />
and infrastructure.<br />
<br />
HakkuTaikai (aka Gotta Hack 'Em All, Hakkushima & other rejected names) will<br />
be held on the Sunday after ICFP/HIM/CUFP has concluded. Given that we have<br />
only one day for this hackathon, there won't be time for talks or presentations.<br />
<br />
== News ==<br />
<br />
* IRC channel: [irc://irc.freenode.net#haskathon #haskathon on FreeNode] ([http://webchat.freenode.net?channels=haskathon WebChat])<br />
* Twitter HashTag: [http://twitter.com/search/%23haskathon #haskathon]<br />
<br />
== Registration ==<br />
<br />
If you will (likely) be attending, please [[/Attendees|list yourself as an<br />
attendee]]. Then check out the [[/Projects|projects page]].<br />
<br />
== Whe(n|re) ==<br />
<br />
* Time: from 09:00, on Sunday the 25th of September, 2011.<br />
* Location: [http://maps.google.com/maps?q=東京都千代田区一ツ橋2-1-2 National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo-to 〒101-8430]<br />
* アクセス: 〒101-8430 東京都千代田区一ツ橋2-1-2 国立情報学研究所<br />
* Room: 1208 (12th floor of NII)<br />
<br />
== Accommodation ==<br />
<br />
Let us know if your accommodation costs for the hackathon would not be<br />
covered as part of the conference, and you would like somewhere to crash<br />
or help with finding low-cost hostels & c.<br />
<br />
If you live locally and can offer accommodation (e.g. a floor or sofa bed or<br />
spare futon to crash on), do let us know too.<br />
<br />
== Preparations ==<br />
<br />
=== What to bring ===<br />
<br />
* A laptop with wireless facilities, and appropriate power adaptors for Japan (A,B; 100V, 50Hz; basically the same plug as USA)<br />
* Ethernet access will be difficult. We can probably set up our own wired LAN if necessary. Please let us know if you think you need wired access.<br />
<br />
=== Before you arrive ===<br />
<br />
* Pick out a couple of projects to work on and familiarise yourself with them, or bring your own project(s) to work on. See the [[/Projects|projects page]] for a list of projects others plan to work on. If you plan to work on your own project, be sure to list it on the [[/Projects|projects page]] and set up a public repository if you don't already have one, so that other people can help hack on your project.<br />
<br />
* Install an up-to-date Haskell toolchain: at least the latest haskell-platform and cabal-install, or preferably the latest GHC (7.2.1 at time of writing). If you don't already have these installed (or need to install from scratch on the laptop you're bringing), the easiest way is the [http://hackage.haskell.org/platform/ Haskell Platform].<br />
<br />
== Organisers ==<br />
<br />
* Liyang HU <haskathon★liyang.hu>, +81 80 4361 1307<br />
* Zhenjiang HU <hu★nii.ac.jp><br />
* Conrad Parker (kfish) <conrad★tsurucapital.com><br />
<br />
[[Category:Community]]<br />
[[Category:Events]]<br />
[[Category:Hackathon]]</div>Liyanghttps://wiki.haskell.org/index.php?title=HakkuTaikai&diff=41755HakkuTaikai2011-08-25T09:59:57Z<p>Liyang: /* Whe(n|re) */ Google maps link</p>
<hr />
<div>= HakkuTaikai: Haskell Hackathon =<br />
<br />
Sunday, 2011-09-25, National Institute of Informatics, Tokyo, Japan<br />
<br />
== About ==<br />
<br />
The Haskell Hackathon is an international, grassroots collaborative coding<br />
festival with a simple focus: build and improve Haskell libraries, tools,<br />
and infrastructure.<br />
<br />
HakkuTaikai (aka Gotta Hack 'Em All, Hakkushima & other rejected names) will<br />
be held on the Sunday after ICFP/HIM/CUFP has concluded. Given that we have<br />
only one day for this hackathon, there won't be time for talks or presentations.<br />
If anyone wishes to carry on hacking after Sunday, we should always be able to find somewhere at short notice.<br />
<br />
== News ==<br />
<br />
* IRC channel: [irc://irc.freenode.net#haskathon #haskathon on FreeNode] ([http://webchat.freenode.net?channels=haskathon WebChat])<br />
* Twitter HashTag: [http://twitter.com/search/%23haskathon #haskathon]<br />
<br />
== Registration ==<br />
<br />
If you will (likely) be attending, please [[/Attendees|list yourself as an<br />
attendee]]. Then check out the [[/Projects|projects page]].<br />
<br />
== Whe(n|re) ==<br />
<br />
* Time: from 09:00, on Sunday the 25th of September, 2011.<br />
* Location: [http://maps.google.com/maps?q=東京都千代田区一ツ橋2-1-2 National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo-to 〒101-8430]<br />
* アクセス: 〒101-8430 東京都千代田区一ツ橋2-1-2 国立情報学研究所<br />
* Room: 1208 (12th floor of NII)<br />
<br />
== Accommodation ==<br />
<br />
Let us know if your accommodation costs for the hackathon would not be<br />
covered as part of the conference, and you would like somewhere to crash<br />
or help with finding low-cost hostels & c.<br />
<br />
If you live locally and can offer accommodation (e.g. a floor or sofa bed or<br />
spare futon to crash on), do let us know too.<br />
<br />
== Preparations ==<br />
<br />
=== What to bring ===<br />
<br />
* A laptop with wireless facilities, and appropriate power adaptors for Japan (A,B; 100V, 50Hz; basically the same plug as USA)<br />
* Ethernet access will be difficult. We can probably set up our own wired LAN if necessary. Please let us know if you think you need wired access.<br />
<br />
=== Before you arrive ===<br />
<br />
* Pick out a couple of projects to work on and familiarise yourself with them, or bring your own project(s) to work on. See the [[/Projects|projects page]] for a list of projects others plan to work on. If you plan to work on your own project, be sure to list it on the [[/Projects|projects page]] and set up a public repository if you don't already have one, so that other people can help hack on your project.<br />
<br />
* Install an up-to-date Haskell toolchain: at least the latest haskell-platform and cabal-install, or preferably the latest GHC (7.2.1 at time of writing). If you don't already have these installed (or need to install from scratch on the laptop you're bringing), the easiest way is the [http://hackage.haskell.org/platform/ Haskell Platform].<br />
<br />
== Organisers ==<br />
<br />
* Liyang HU <haskathon★liyang.hu>, +81 80 4361 1307<br />
* Zhenjiang HU <hu★nii.ac.jp><br />
* Conrad Parker (kfish) <conrad★tsurucapital.com><br />
<br />
[[Category:Community]]<br />
[[Category:Events]]<br />
[[Category:Hackathon]]</div>Liyanghttps://wiki.haskell.org/index.php?title=HakkuTaikai&diff=41754HakkuTaikai2011-08-25T09:58:58Z<p>Liyang: /* About */</p>
<hr />
<div>= HakkuTaikai: Haskell Hackathon =<br />
<br />
Sunday, 2011-09-25, National Institute of Informatics, Tokyo, Japan<br />
<br />
== About ==<br />
<br />
The Haskell Hackathon is an international, grassroots collaborative coding<br />
festival with a simple focus: build and improve Haskell libraries, tools,<br />
and infrastructure.<br />
<br />
HakkuTaikai (aka Gotta Hack 'Em All, Hakkushima & other rejected names) will<br />
be held on the Sunday after ICFP/HIM/CUFP has concluded. Given that we have<br />
only one day for this hackathon, there won't be time for talks or presentations.<br />
If anyone wishes to carry on hacking after Sunday, we should always be able to find somewhere at short notice.<br />
<br />
== News ==<br />
<br />
* IRC channel: [irc://irc.freenode.net#haskathon #haskathon on FreeNode] ([http://webchat.freenode.net?channels=haskathon WebChat])<br />
* Twitter HashTag: [http://twitter.com/search/%23haskathon #haskathon]<br />
<br />
== Registration ==<br />
<br />
If you will (likely) be attending, please [[/Attendees|list yourself as an<br />
attendee]]. Then check out the [[/Projects|projects page]].<br />
<br />
== Whe(n|re) ==<br />
<br />
* Time: from 09:00, on Sunday the 25th of September, 2011.<br />
* Location: National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo-to 〒101-8430<br />
* アクセス: 〒101-8430 東京都千代田区一ツ橋2-1-2 国立情報学研究所<br />
* Google Maps: http://maps.google.com/maps?q=東京都千代田区一ツ橋2-1-2<br />
* Room: 1208 (12th floor of NII)<br />
<br />
== Accommodation ==<br />
<br />
Let us know if your accommodation costs for the hackathon would not be<br />
covered as part of the conference, and you would like somewhere to crash<br />
or help with finding low-cost hostels & c.<br />
<br />
If you live locally and can offer accommodation (e.g. a floor or sofa bed or<br />
spare futon to crash on), do let us know too.<br />
<br />
== Preparations ==<br />
<br />
=== What to bring ===<br />
<br />
* A laptop with wireless facilities, and appropriate power adaptors for Japan (A,B; 100V, 50Hz; basically the same plug as USA)<br />
* Ethernet access will be difficult. We can probably set up our own wired LAN if necessary. Please let us know if you think you need wired access.<br />
<br />
=== Before you arrive ===<br />
<br />
* Pick out a couple of projects to work on and familiarise yourself with them, or bring your own project(s) to work on. See the [[/Projects|projects page]] for a list of projects others plan to work on. If you plan to work on your own project, be sure to list it on the [[/Projects|projects page]] and set up a public repository if you don't already have one, so that other people can help hack on your project.<br />
<br />
* Install an up-to-date Haskell toolchain: at least the latest haskell-platform and cabal-install, or preferably the latest GHC (7.2.1 at time of writing). If you don't already have these installed (or need to install from scratch on the laptop you're bringing), the easiest way is the [http://hackage.haskell.org/platform/ Haskell Platform].<br />
<br />
== Organisers ==<br />
<br />
* Liyang HU <haskathon★liyang.hu>, +81 80 4361 1307<br />
* Zhenjiang HU <hu★nii.ac.jp><br />
* Conrad Parker (kfish) <conrad★tsurucapital.com><br />
<br />
[[Category:Community]]<br />
[[Category:Events]]<br />
[[Category:Hackathon]]</div>Liyanghttps://wiki.haskell.org/index.php?title=HakkuTaikai/Projects&diff=41752HakkuTaikai/Projects2011-08-25T09:12:18Z<p>Liyang: New page: == Sharing your code == If you need a place to host a project so that others can help with it, we suggest [http://patch-tag.com/ patch-tag], which offers free hosting for public darcs rep...</p>
<hr />
<div>== Sharing your code ==<br />
<br />
If you need a place to host a project so that others can help with it, we suggest [http://patch-tag.com/ patch-tag], which offers free hosting for public darcs repositories. If you're using git, [http://github.com github] is just dandy as well. You can also apply for an account on [http://community.haskell.org/admin/ the community server].<br />
<br />
== Projects ==<br />
<br />
If you have a project that you want to work on at the Hackathon, please describe it here.<br />
<br />
Since Hackathons are great for teamwork, consider joining one of the projects mentioned below. If you're interested in one of these projects, add your name to the list of hackers under that project.<br />
<br />
=== containers ===<br />
<br />
Johan Tibbel has [http://blog.johantibell.com/2011/05/new-release-of-unordered-containers.html recently been doing some work] on [http://hackage.haskell.org/package/unordered-containers unordered-containers], with an eventual goal of unifying the current {Int,Hash,}Map interfaces. Would be nice to have some form of unboxed containers in there too.<br />
<br />
* Liyang<br />
<br />
=== time ===<br />
<br />
The current implementation of time uses lots of Integers internally which makes it much slower than necessary. Thinking about moving to an Int64-based representation while still being able to represent any conceivable dates & times.<br />
<br />
* Liyang<br />
<br />
<!-- Copy this template<br />
=== Project name ===<br />
<br />
I am a project. Love me.<br />
<br />
* Hacker 1<br />
* Hacker 2<br />
--></div>Liyanghttps://wiki.haskell.org/index.php?title=HakkuTaikai/Attendees&diff=41751HakkuTaikai/Attendees2011-08-25T06:34:57Z<p>Liyang: /* HakkuTaikai Attendees */ Finalised.</p>
<hr />
<div>= HakkuTaikai Attendees =<br />
<br />
If you do not wish to announce your attendance in public, please email haskathon★liyang.hu instead.<br />
<br />
{| class="wikitable"<br />
!Nickname<br />
!Real Name<br />
!Affiliation<br />
!Mobile<br />
|-<br />
| liyang<br />
| Liyang HU<br />
| Tsuru Capital LLC<br />
| +81 80 4361 1307<br />
|-<br />
| kfish<br />
| [[User:ConradParker|Conrad Parker]]<br />
| Tsuru Capital SG Pte Ltd<br />
| +81 80 4162 1307<br />
|}</div>Liyanghttps://wiki.haskell.org/index.php?title=HakkuTaikai&diff=41750HakkuTaikai2011-08-25T06:34:11Z<p>Liyang: /* HakkuTaikai: Haskell Hackathon */ No longer under construction.</p>
<hr />
<div>= HakkuTaikai: Haskell Hackathon =<br />
<br />
Sunday, 2011-09-25, National Institute of Informatics, Tokyo, Japan<br />
<br />
== About ==<br />
<br />
The Haskell Hackathon is an international, grassroots collaborative coding<br />
festival with a simple focus: build and improve Haskell libraries, tools,<br />
and infrastructure.<br />
<br />
HakkuTaikai (aka Gotta Hack 'Em All, Hakkushima & other rejected names) will<br />
be held on the Sunday after ICFP/HIM/CUFP has concluded. Given that we have<br />
only one day for this hackathon, there won't be time for talks or presentations.<br />
<br />
== News ==<br />
<br />
* IRC channel: [irc://irc.freenode.net#haskathon #haskathon on FreeNode] ([http://webchat.freenode.net?channels=haskathon WebChat])<br />
* Twitter HashTag: [http://twitter.com/search/%23haskathon #haskathon]<br />
<br />
== Registration ==<br />
<br />
If you will (likely) be attending, please [[/Attendees|list yourself as an<br />
attendee]]. Then check out the [[/Projects|projects page]].<br />
<br />
== Whe(n|re) ==<br />
<br />
* Time: from 09:00, on Sunday the 25th of September, 2011.<br />
* Location: National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo-to 〒101-8430<br />
* アクセス: 〒101-8430 東京都千代田区一ツ橋2-1-2 国立情報学研究所<br />
* Google Maps: http://maps.google.com/maps?q=東京都千代田区一ツ橋2-1-2<br />
* Room: 1208 (12th floor of NII)<br />
<br />
== Accommodation ==<br />
<br />
Let us know if your accommodation costs for the hackathon would not be<br />
covered as part of the conference, and you would like somewhere to crash<br />
or help with finding low-cost hostels & c.<br />
<br />
If you live locally and can offer accommodation (e.g. a floor or sofa bed or<br />
spare futon to crash on), do let us know too.<br />
<br />
== Preparations ==<br />
<br />
=== What to bring ===<br />
<br />
* A laptop with wireless facilities, and appropriate power adaptors for Japan (A,B; 100V, 50Hz; basically the same plug as USA)<br />
* Ethernet access will be difficult. We can probably set up our own wired LAN if necessary. Please let us know if you think you need wired access.<br />
<br />
=== Before you arrive ===<br />
<br />
* Pick out a couple of projects to work on and familiarise yourself with them, or bring your own project(s) to work on. See the [[/Projects|projects page]] for a list of projects others plan to work on. If you plan to work on your own project, be sure to list it on the [[/Projects|projects page]] and set up a public repository if you don't already have one, so that other people can help hack on your project.<br />
<br />
* Install an up-to-date Haskell toolchain: at least the latest haskell-platform and cabal-install, or preferably the latest GHC (7.2.1 at time of writing). If you don't already have these installed (or need to install from scratch on the laptop you're bringing), the easiest way is the [http://hackage.haskell.org/platform/ Haskell Platform].<br />
<br />
== Organisers ==<br />
<br />
* Liyang HU <haskathon★liyang.hu>, +81 80 4361 1307<br />
* Zhenjiang HU <hu★nii.ac.jp><br />
* Conrad Parker (kfish) <conrad★tsurucapital.com><br />
<br />
[[Category:Community]]<br />
[[Category:Events]]<br />
[[Category:Hackathon]]</div>Liyanghttps://wiki.haskell.org/index.php?title=HakkuTaikai&diff=41666HakkuTaikai2011-08-17T06:50:30Z<p>Liyang: /* About */ short time</p>
<hr />
<div>= HakkuTaikai: Haskell Hackathon =<br />
<br />
Sunday, 2011-09-25, National Institute of Informatics, Tokyo, Japan<br />
<br />
(Page under construction. Please help improve this page or direct queries to liyang on FreeNode IRC in the meantime.)<br />
<br />
== About ==<br />
<br />
The Haskell Hackathon is an international, grassroots collaborative coding<br />
festival with a simple focus: build and improve Haskell libraries, tools,<br />
and infrastructure.<br />
<br />
HakkuTaikai (aka Gotta Hack 'Em All, Hakkushima & other rejected names) will<br />
be held on the Sunday after ICFP/HIM/CUFP has concluded. Given that we have<br />
only one day for this hackathon, there won't be time for talks or presentations.<br />
<br />
== News ==<br />
<br />
* IRC channel: [irc://irc.freenode.net#haskathon #haskathon on FreeNode] ([http://webchat.freenode.net?channels=haskathon WebChat])<br />
* Twitter HashTag: [http://twitter.com/search/%23haskathon #haskathon]<br />
<br />
== Registration ==<br />
<br />
If you will (likely) be attending, please [[/Attendees|list yourself as an<br />
attendee]]. Then check out the [[/Projects|projects page]].<br />
<br />
== Whe(n|re) ==<br />
<br />
* Time: from 09:00, on Sunday the 25th of September, 2011.<br />
* Location: National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo-to 〒101-8430<br />
* アクセス: 〒101-8430 東京都千代田区一ツ橋2-1-2 国立情報学研究所<br />
* Google Maps: http://maps.google.com/maps?q=東京都千代田区一ツ橋2-1-2<br />
* Room: 1208 (12th floor of NII)<br />
<br />
== Accommodation ==<br />
<br />
Let us know if your accommodation costs for the hackathon would not be<br />
covered as part of the conference, and you would like somewhere to crash<br />
or help with finding low-cost hostels & c.<br />
<br />
If you live locally and can offer accommodation (e.g. a floor or sofa bed or<br />
spare futon to crash on), do let us know too.<br />
<br />
== Preparations ==<br />
<br />
=== What to bring ===<br />
<br />
* A laptop with wireless facilities, and appropriate power adaptors for Japan.<br />
* Ethernet access will be difficult. We can probably set up our own wired LAN if necessary. Please let us know if you think you need wired access.<br />
<br />
=== Before you arrive ===<br />
<br />
* Pick out a couple of projects to work on and familiarise yourself with them, or bring your own project(s) to work on. See the [[/Projects|projects page]] for a list of projects others plan to work on. If you plan to work on your own project, be sure to list it on the [[/Projects|projects page]] and set up a public repository if you don't already have one, so that other people can help hack on your project.<br />
<br />
* Install an up-to-date Haskell toolchain: at least the latest haskell-platform and cabal-install, or preferably the latest GHC (7.2.1 at time of writing). If you don't already have these installed (or need to install from scratch on the laptop you're bringing), the easiest way is the [http://hackage.haskell.org/platform/ Haskell Platform].<br />
<br />
== Organisers ==<br />
<br />
* Liyang HU <haskathon★liyang.hu>, +81 80 4361 1307<br />
* Zhenjiang HU <hu★nii.ac.jp><br />
* Conrad Parker (kfish) <conrad★tsurucapital.com><br />
<br />
[[Category:Community]]<br />
[[Category:Events]]<br />
[[Category:Hackathon]]</div>Liyanghttps://wiki.haskell.org/index.php?title=HakkuTaikai&diff=41665HakkuTaikai2011-08-17T06:44:48Z<p>Liyang: spacing</p>
<hr />
<div>= HakkuTaikai: Haskell Hackathon =<br />
<br />
Sunday, 2011-09-25, National Institute of Informatics, Tokyo, Japan<br />
<br />
(Page under construction. Please help improve this page or direct queries to liyang on FreeNode IRC in the meantime.)<br />
<br />
== About ==<br />
<br />
The Haskell Hackathon is an international, grassroots collaborative coding<br />
festival with a simple focus: build and improve Haskell libraries, tools,<br />
and infrastructure.<br />
<br />
HakkuTaikai (aka Gotta Hack 'Em All, Hakkushima & other rejected names) will<br />
be held on the Sunday after ICFP/HIM/CUFP has concluded.<br />
<br />
== News ==<br />
<br />
* IRC channel: [irc://irc.freenode.net#haskathon #haskathon on FreeNode] ([http://webchat.freenode.net?channels=haskathon WebChat])<br />
* Twitter HashTag: [http://twitter.com/search/%23haskathon #haskathon]<br />
<br />
== Registration ==<br />
<br />
If you will (likely) be attending, please [[/Attendees|list yourself as an<br />
attendee]]. Then check out the [[/Projects|projects page]].<br />
<br />
== Whe(n|re) ==<br />
<br />
* Time: from 09:00, on Sunday the 25th of September, 2011.<br />
* Location: National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo-to 〒101-8430<br />
* アクセス: 〒101-8430 東京都千代田区一ツ橋2-1-2 国立情報学研究所<br />
* Google Maps: http://maps.google.com/maps?q=東京都千代田区一ツ橋2-1-2<br />
* Room: 1208 (12th floor of NII)<br />
<br />
== Accommodation ==<br />
<br />
Let us know if your accommodation costs for the hackathon would not be<br />
covered as part of the conference, and you would like somewhere to crash<br />
or help with finding low-cost hostels & c.<br />
<br />
If you live locally and can offer accommodation (e.g. a floor or sofa bed or<br />
spare futon to crash on), do let us know too.<br />
<br />
== Preparations ==<br />
<br />
=== What to bring ===<br />
<br />
* A laptop with wireless facilities, and appropriate power adaptors for Japan.<br />
* Ethernet access will be difficult. We can probably set up our own wired LAN if necessary. Please let us know if you think you need wired access.<br />
<br />
=== Before you arrive ===<br />
<br />
* Pick out a couple of projects to work on and familiarise yourself with them, or bring your own project(s) to work on. See the [[/Projects|projects page]] for a list of projects others plan to work on. If you plan to work on your own project, be sure to list it on the [[/Projects|projects page]] and set up a public repository if you don't already have one, so that other people can help hack on your project.<br />
<br />
* Install an up-to-date Haskell toolchain: at least the latest haskell-platform and cabal-install, or preferably the latest GHC (7.2.1 at time of writing). If you don't already have these installed (or need to install from scratch on the laptop you're bringing), the easiest way is the [http://hackage.haskell.org/platform/ Haskell Platform].<br />
<br />
== Organisers ==<br />
<br />
* Liyang HU <haskathon★liyang.hu>, +81 80 4361 1307<br />
* Zhenjiang HU <hu★nii.ac.jp><br />
* Conrad Parker (kfish) <conrad★tsurucapital.com><br />
<br />
[[Category:Community]]<br />
[[Category:Events]]<br />
[[Category:Hackathon]]</div>Liyanghttps://wiki.haskell.org/index.php?title=HakkuTaikai&diff=41664HakkuTaikai2011-08-17T06:43:33Z<p>Liyang: /* HakkuTaikai: Haskell Hackathon */</p>
<hr />
<div>= HakkuTaikai: Haskell Hackathon =<br />
<br />
Sunday, 2011-09-25, National Institute of Informatics, Tokyo, Japan<br />
<br />
(Page under construction. Please help improve this page or direct queries to liyang on FreeNode IRC in the meantime.)<br />
<br />
== About ==<br />
<br />
The Haskell Hackathon is an international, grassroots collaborative coding<br />
festival with a simple focus: build and improve Haskell libraries, tools,<br />
and infrastructure.<br />
<br />
HakkuTaikai (aka Gotta Hack 'Em All, Hakkushima & other rejected names) will<br />
be held on the Sunday after ICFP/HIM/CUFP has concluded.<br />
<br />
<br />
== News ==<br />
<br />
* IRC channel: [irc://irc.freenode.net#haskathon #haskathon on FreeNode] ([http://webchat.freenode.net?channels=haskathon WebChat])<br />
* Twitter HashTag: [http://twitter.com/search/%23haskathon #haskathon]<br />
<br />
== Registration ==<br />
<br />
If you will (likely) be attending, please [[/Attendees|list yourself as an<br />
attendee]]. Then check out the [[/Projects|projects page]].<br />
<br />
<br />
== Whe(n|re) ==<br />
<br />
* Time: from 09:00, on Sunday the 25th of September, 2011.<br />
* Location: National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo-to 〒101-8430<br />
* アクセス: 〒101-8430 東京都千代田区一ツ橋2-1-2 国立情報学研究所<br />
* Google Maps: http://maps.google.com/maps?q=東京都千代田区一ツ橋2-1-2<br />
* Room: 1208 (12th floor of NII)<br />
<br />
== Accommodation ==<br />
<br />
Let us know if your accommodation costs for the hackathon would not be<br />
covered as part of the conference, and you would like somewhere to crash<br />
or help with finding low-cost hostels & c.<br />
<br />
If you live locally and can offer accommodation (e.g. a floor or sofa bed or<br />
spare futon to crash on), do let us know too.<br />
<br />
<br />
== Preparations ==<br />
<br />
=== What to bring ===<br />
<br />
* A laptop with wireless facilities, and appropriate power adaptors for Japan.<br />
* Ethernet access will be difficult. We can probably set up our own wired LAN if necessary. Please let us know if you think you need wired access.<br />
<br />
<br />
=== Before you arrive ===<br />
<br />
* Pick out a couple of projects to work on and familiarise yourself with them, or bring your own project(s) to work on. See the [[/Projects|projects page]] for a list of projects others plan to work on. If you plan to work on your own project, be sure to list it on the [[/Projects|projects page]] and set up a public repository if you don't already have one, so that other people can help hack on your project.<br />
<br />
* Install an up-to-date Haskell toolchain: at least the latest haskell-platform and cabal-install, or preferably the latest GHC (7.2.1 at time of writing). If you don't already have these installed (or need to install from scratch on the laptop you're bringing), the easiest way is the [http://hackage.haskell.org/platform/ Haskell Platform].<br />
<br />
<br />
== Organisers ==<br />
<br />
* Liyang HU <haskathon★liyang.hu>, +81 80 4361 1307<br />
* Zhenjiang HU <hu★nii.ac.jp><br />
* Conrad Parker (kfish) <conrad★tsurucapital.com><br />
<br />
<br />
[[Category:Community]]<br />
[[Category:Events]]<br />
[[Category:Hackathon]]</div>Liyanghttps://wiki.haskell.org/index.php?title=HakkuTaikai&diff=41663HakkuTaikai2011-08-17T06:42:49Z<p>Liyang: /* News */ IRC URIs</p>
<hr />
<div>= HakkuTaikai: Haskell Hackathon =<br />
<br />
Sunday, 2011-09-25, National Institute of Informatics, Tokyo, Japan<br />
<br />
(Page under construction. Please direct questions to liyang on FreeNode IRC<br />
in the meantime.)<br />
<br />
== About ==<br />
<br />
The Haskell Hackathon is an international, grassroots collaborative coding<br />
festival with a simple focus: build and improve Haskell libraries, tools,<br />
and infrastructure.<br />
<br />
HakkuTaikai (aka Gotta Hack 'Em All, Hakkushima & other rejected names) will<br />
be held on the Sunday after ICFP/HIM/CUFP has concluded.<br />
<br />
<br />
== News ==<br />
<br />
* IRC channel: [irc://irc.freenode.net#haskathon #haskathon on FreeNode] ([http://webchat.freenode.net?channels=haskathon WebChat])<br />
* Twitter HashTag: [http://twitter.com/search/%23haskathon #haskathon]<br />
<br />
== Registration ==<br />
<br />
If you will (likely) be attending, please [[/Attendees|list yourself as an<br />
attendee]]. Then check out the [[/Projects|projects page]].<br />
<br />
<br />
== Whe(n|re) ==<br />
<br />
* Time: from 09:00, on Sunday the 25th of September, 2011.<br />
* Location: National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo-to 〒101-8430<br />
* アクセス: 〒101-8430 東京都千代田区一ツ橋2-1-2 国立情報学研究所<br />
* Google Maps: http://maps.google.com/maps?q=東京都千代田区一ツ橋2-1-2<br />
* Room: 1208 (12th floor of NII)<br />
<br />
== Accommodation ==<br />
<br />
Let us know if your accommodation costs for the hackathon would not be<br />
covered as part of the conference, and you would like somewhere to crash<br />
or help with finding low-cost hostels & c.<br />
<br />
If you live locally and can offer accommodation (e.g. a floor or sofa bed or<br />
spare futon to crash on), do let us know too.<br />
<br />
<br />
== Preparations ==<br />
<br />
=== What to bring ===<br />
<br />
* A laptop with wireless facilities, and appropriate power adaptors for Japan.<br />
* Ethernet access will be difficult. We can probably set up our own wired LAN if necessary. Please let us know if you think you need wired access.<br />
<br />
<br />
=== Before you arrive ===<br />
<br />
* Pick out a couple of projects to work on and familiarise yourself with them, or bring your own project(s) to work on. See the [[/Projects|projects page]] for a list of projects others plan to work on. If you plan to work on your own project, be sure to list it on the [[/Projects|projects page]] and set up a public repository if you don't already have one, so that other people can help hack on your project.<br />
<br />
* Install an up-to-date Haskell toolchain: at least the latest haskell-platform and cabal-install, or preferably the latest GHC (7.2.1 at time of writing). If you don't already have these installed (or need to install from scratch on the laptop you're bringing), the easiest way is the [http://hackage.haskell.org/platform/ Haskell Platform].<br />
<br />
<br />
== Organisers ==<br />
<br />
* Liyang HU <haskathon★liyang.hu>, +81 80 4361 1307<br />
* Zhenjiang HU <hu★nii.ac.jp><br />
* Conrad Parker (kfish) <conrad★tsurucapital.com><br />
<br />
<br />
[[Category:Community]]<br />
[[Category:Events]]<br />
[[Category:Hackathon]]</div>Liyanghttps://wiki.haskell.org/index.php?title=HakkuTaikai/Attendees&diff=41662HakkuTaikai/Attendees2011-08-17T04:21:11Z<p>Liyang: /* HakkuTaikai Attendees */ Removed the Accommodation column.</p>
<hr />
<div>= HakkuTaikai Attendees =<br />
<br />
If you do not wish to announce your attendance in public, please email haskathon★liyang.hu instead.<br />
<br />
(The information we need hasn't been finalised yet, but please fill in your details for now anyway, to give us an indication of numbers.)<br />
<br />
{| class="wikitable"<br />
!Nickname<br />
!Real Name<br />
!Affiliation<br />
!Mobile<br />
|-<br />
| liyang<br />
| Liyang HU<br />
| Tsuru Capital LLC<br />
| +81 80 4361 1307<br />
|-<br />
| kfish<br />
| [[User:ConradParker|Conrad Parker]]<br />
| Tsuru Capital SG Pte Ltd<br />
| +81 80 4162 1307<br />
|}</div>Liyanghttps://wiki.haskell.org/index.php?title=HakkuTaikai&diff=41659HakkuTaikai2011-08-17T02:14:50Z<p>Liyang: /* Whe(n|re) */ Room #</p>
<hr />
<div>= HakkuTaikai: Haskell Hackathon =<br />
<br />
Sunday, 2011-09-25, National Institute of Informatics, Tokyo, Japan<br />
<br />
(Page under construction. Please direct questions to liyang on FreeNode IRC<br />
in the meantime.)<br />
<br />
== About ==<br />
<br />
The Haskell Hackathon is an international, grassroots collaborative coding<br />
festival with a simple focus: build and improve Haskell libraries, tools,<br />
and infrastructure.<br />
<br />
HakkuTaikai (aka Gotta Hack 'Em All, Hakkushima & other rejected names) will<br />
be held on the Sunday after ICFP/HIM/CUFP has concluded.<br />
<br />
<br />
== News ==<br />
<br />
* IRC channel: #haskathon (freenode)<br />
* Twitter HashTag: #haskathon http://twitter.com/search/%23haskathon<br />
<br />
<br />
== Registration ==<br />
<br />
If you will (likely) be attending, please [[/Attendees|list yourself as an<br />
attendee]]. Then check out the [[/Projects|projects page]].<br />
<br />
<br />
== Whe(n|re) ==<br />
<br />
* Time: from 09:00, on Sunday the 25th of September, 2011.<br />
* Location: National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo-to 〒101-8430<br />
* アクセス: 〒101-8430 東京都千代田区一ツ橋2-1-2 国立情報学研究所<br />
* Google Maps: http://maps.google.com/maps?q=東京都千代田区一ツ橋2-1-2<br />
* Room: 1208 (12th floor of NII)<br />
<br />
== Accommodation ==<br />
<br />
Let us know if your accommodation costs for the hackathon would not be<br />
covered as part of the conference, and you would like somewhere to crash<br />
or help with finding low-cost hostels & c.<br />
<br />
If you live locally and can offer accommodation (e.g. a floor or sofa bed or<br />
spare futon to crash on), do let us know too.<br />
<br />
<br />
== Preparations ==<br />
<br />
=== What to bring ===<br />
<br />
* A laptop with wireless facilities, and appropriate power adaptors for Japan.<br />
* Ethernet access will be difficult. We can probably set up our own wired LAN if necessary. Please let us know if you think you need wired access.<br />
<br />
<br />
=== Before you arrive ===<br />
<br />
* Pick out a couple of projects to work on and familiarise yourself with them, or bring your own project(s) to work on. See the [[/Projects|projects page]] for a list of projects others plan to work on. If you plan to work on your own project, be sure to list it on the [[/Projects|projects page]] and set up a public repository if you don't already have one, so that other people can help hack on your project.<br />
<br />
* Install an up-to-date Haskell toolchain: at least the latest haskell-platform and cabal-install, or preferably the latest GHC (7.2.1 at time of writing). If you don't already have these installed (or need to install from scratch on the laptop you're bringing), the easiest way is the [http://hackage.haskell.org/platform/ Haskell Platform].<br />
<br />
<br />
== Organisers ==<br />
<br />
* Liyang HU <haskathon★liyang.hu>, +81 80 4361 1307<br />
* Zhenjiang HU <hu★nii.ac.jp><br />
* Conrad Parker (kfish) <conrad★tsurucapital.com><br />
<br />
<br />
[[Category:Community]]<br />
[[Category:Events]]<br />
[[Category:Hackathon]]</div>Liyanghttps://wiki.haskell.org/index.php?title=Hackathon&diff=41652Hackathon2011-08-16T15:18:09Z<p>Liyang: Tokyo</p>
<hr />
<div>[[Image:Hac-axe-icon.png|Hac icon]]<br />
<br />
'''Hac: The Haskell Hackathon'''<br />
<br />
The Haskell developer community holds regular hackathons, to get<br />
together, collaborate, and work on key tools and infrastructure.<br />
<br />
* [[HakkuTaikai|Tokyo, Sep 2011]]<br />
* [[CamHac|Cambridge, Aug 2011]]<br />
* [[HacPDX-II|Portland, Jul 2011]]<br />
* [[Hac φ|Philadelphia, Jul 2011]]<br />
* [[BayHac2011|SF Bay Area, Feb 2011]]<br />
* [[Ghent Functional Programming Group/BelHac|Ghent, Nov 2010]]<br />
* [[LtU-Kiev/Hackathon|Kiev, Oct 2010]]<br />
* [[AusHac2010|Australian Hackathon, Jul 2010]]<br />
* [[Hac φ|Philadelphia, May 2010]]<br />
* [[ZuriHac|Zurich, Mar 2010]]<br />
* [[HacPDX|Portland, OR, Sep 2009]]<br />
* [[Hac7|Edinburgh, Aug 2009]]<br />
* [[Hac φ|Philadelphia, Jul 2009]]<br />
* [[Hac5|Utrecht, Apr 2009]]<br />
* [[HaL3|Leipzig, Apr 2008]]<br />
* [[Hac 2008|Göteborg, Apr 2008]]<br />
* [[Hac 2007 II|Freiburg, Oct 2007]]<br />
* [[Hac 2007|Oxford, Jan 2007]]<br />
* [http://hackage.haskell.org/trac/ghc/wiki/Hackathon Portland, Sep 2006]<br />
<br />
[[Category:Events]]<br />
[[Category:Hackathon]]</div>Liyanghttps://wiki.haskell.org/index.php?title=HakkuTaikai/Attendees&diff=41643HakkuTaikai/Attendees2011-08-16T11:19:53Z<p>Liyang: New page: = HakkuTaikai Attendees = If you do not wish to announce your attendance in public, please email haskathon★liyang.hu instead. (The information we need hasn't been finalised yet, but pl...</p>
<hr />
<div>= HakkuTaikai Attendees =<br />
<br />
If you do not wish to announce your attendance in public, please email haskathon★liyang.hu instead.<br />
<br />
(The information we need hasn't been finalised yet, but please fill in your details for now anyway, to give us an indication of numbers.)<br />
<br />
{| class="wikitable"<br />
!Nickname<br />
!Real Name<br />
!Affiliation<br />
!Mobile<br />
!Accommodation?<br />
|-<br />
| liyang<br />
| Liyang HU<br />
| Tsuru Capital LLC<br />
| +81 80 4361 1307<br />
| lives in Tokyo<br />
|-<br />
| kfish<br />
| Conrad Parker<br />
| Tsuru Capital SG Pte Ltd<br />
| -<br />
| no<br />
|}</div>Liyanghttps://wiki.haskell.org/index.php?title=HakkuTaikai&diff=41642HakkuTaikai2011-08-16T11:08:20Z<p>Liyang: New page: = HakkuTaikai: Haskell Hackathon = Sunday, 2011-09-25, National Institute of Informatics, Tokyo, Japan (Page under construction. Please direct questions to liyang on FreeNode IRC in the ...</p>
<hr />
<div>= HakkuTaikai: Haskell Hackathon =<br />
<br />
Sunday, 2011-09-25, National Institute of Informatics, Tokyo, Japan<br />
<br />
(Page under construction. Please direct questions to liyang on FreeNode IRC<br />
in the meantime.)<br />
<br />
== About ==<br />
<br />
The Haskell Hackathon is an international, grassroots collaborative coding<br />
festival with a simple focus: build and improve Haskell libraries, tools,<br />
and infrastructure.<br />
<br />
HakkuTaikai (aka Gotta Hack 'Em All, Hakkushima & other rejected names) will<br />
be held on the Sunday after ICFP/HIM/CUFP has concluded.<br />
<br />
<br />
== News ==<br />
<br />
* IRC channel: #haskathon (freenode)<br />
* Twitter HashTag: #haskathon http://twitter.com/search/%23haskathon<br />
<br />
<br />
== Registration ==<br />
<br />
If you will (likely) be attending, please [[/Attendees|list yourself as an<br />
attendee]]. Then check out the [[/Projects|projects page]].<br />
<br />
<br />
== Whe(n|re) ==<br />
<br />
* Time: from 09:00, on Sunday the 25th of September, 2011.<br />
* Location: National Institute of Informatics, Hitotsubashi 2-1-2, Chiyoda-ku, Tokyo-to 〒101-8430<br />
* アクセス: 〒101-8430 東京都千代田区一ツ橋2-1-2 国立情報学研究所<br />
* Google Maps: http://maps.google.com/maps?q=東京都千代田区一ツ橋2-1-2<br />
* Room: to be confirmed.<br />
<br />
<br />
== Accommodation ==<br />
<br />
Let us know if your accommodation costs for the hackathon would not be<br />
covered as part of the conference, and you would like somewhere to crash<br />
or help with finding low-cost hostels & c.<br />
<br />
If you live locally and can offer accommodation (e.g. a floor or sofa bed or<br />
spare futon to crash on), do let us know too.<br />
<br />
<br />
== Preparations ==<br />
<br />
=== What to bring ===<br />
<br />
* A laptop with wireless facilities, and appropriate power adaptors for Japan.<br />
* Ethernet access will be difficult. We can probably set up our own wired LAN if necessary. Please let us know if you think you need wired access.<br />
<br />
<br />
=== Before you arrive ===<br />
<br />
* Pick out a couple of projects to work on and familiarise yourself with them, or bring your own project(s) to work on. See the [[/Projects|projects page]] for a list of projects others plan to work on. If you plan to work on your own project, be sure to list it on the [[/Projects|projects page]] and set up a public repository if you don't already have one, so that other people can help hack on your project.<br />
<br />
* Install an up-to-date Haskell toolchain: at least the latest haskell-platform and cabal-install, or preferably the latest GHC (7.2.1 at time of writing). If you don't already have these installed (or need to install from scratch on the laptop you're bringing), the easiest way is the [http://hackage.haskell.org/platform/ Haskell Platform].<br />
<br />
<br />
== Organisers ==<br />
<br />
* Liyang HU <haskathon★liyang.hu>, +81 80 4361 1307<br />
* Zhenjiang HU <hu★nii.ac.jp><br />
* Conrad Parker (kfish) <conrad★tsurucapital.com><br />
<br />
<br />
[[Category:Community]]<br />
[[Category:Events]]<br />
[[Category:Hackathon]]</div>Liyanghttps://wiki.haskell.org/index.php?title=Liyang/collatz.hs&diff=15555Liyang/collatz.hs2007-09-13T00:16:46Z<p>Liyang: </p>
<hr />
<div>== Lengths of [http://en.wikipedia.org/wiki/Collatz_conjecture Collatz sequences] ==<br />
<haskell><br />
module Main where<br />
<br />
import Prelude hiding ( sequence_ )<br />
import Control.Applicative<br />
import Control.Monad ( ap )<br />
import Control.Monad.State ( State )<br />
import qualified Control.Monad.State as State<br />
import Data.Map ( Map )<br />
import qualified Data.Map as Map<br />
import Data.Foldable<br />
import Data.Traversable<br />
import System.Environment<br />
import Text.Printf<br />
<br />
instance Applicative (State alpha) where<br />
pure = return<br />
(<*>) = ap<br />
<br />
collatz :: Integer -> State (Map Integer Integer) Integer<br />
collatz n = case n of<br />
1 -> return 0<br />
_ -> do<br />
mm <- State.gets (Map.lookup n)<br />
case mm of<br />
Just m -> return m<br />
Nothing -> do<br />
m <- succ `fmap` collatz<br />
(if even n then n `div` 2 else 3 * n + 1)<br />
State.modify (Map.insert n m)<br />
return m<br />
<br />
main :: IO ()<br />
main = getArgs >>= mainArgs<br />
<br />
mainArgs :: [String] -> IO ()<br />
mainArgs [a, b] | kosher ra && kosher rb && na <= nb && na > 0 = do<br />
let ns = [na .. nb]<br />
let ms = State.evalState (traverse collatz ns) Map.empty<br />
sequence_ (zipWith (printf "%d %d\n") ns ms) -- for Grapher.app<br />
-- sequence_ (zipWith (printf "%d takes %d iterations to reach 1\n") ns ms)<br />
where<br />
ra@ ~[(na, _)] = reads a<br />
rb@ ~[(nb, _)] = reads b<br />
kosher r = case r of<br />
[_] -> True<br />
_ -> False<br />
mainArgs _ = return ()<br />
</haskell></div>Liyanghttps://wiki.haskell.org/index.php?title=Sudoku&diff=15396Sudoku2007-09-03T21:48:03Z<p>Liyang: /* Concurrent STM Solver */</p>
<hr />
<div>[[Category:Code]]<br />
<br />
Here are a few Sudoku solvers coded up in Haskell...<br />
<br />
== Monadic non-deterministic solver ==<br />
<br />
Here is a solver by CaleGibbard. It possibly looks even more naïve than it actually is. This does a backtracking search, trying possibilities until it finds one which works, and backtracking when it can no longer make a legal move.<br />
<br />
<haskell><br />
import MonadNondet (option)<br />
import Sudoku<br />
import System<br />
import Control.Monad<br />
<br />
forM = flip mapM<br />
<br />
solve = forM [(i,j) | i <- [1..9], j <- [1..9]] $ \(i,j) -> do<br />
v <- valAt (i,j) -- ^ for each board position<br />
when (v == 0) $ do -- if it's empty (we represent that with a 0)<br />
a <- option [1..9] -- pick a number<br />
place (i,j) a -- and try to put it there<br />
<br />
main = do<br />
[f] <- getArgs<br />
xs <- readFile f<br />
putStrLn . evalSudoku $ do { readSudoku xs; solve; showSudoku }<br />
</haskell><br />
<br />
Now, to the meat of the thing, the monad which makes the above look so nice. We construct a monad which is suitable for maintaining Sudoku grids and trying options nondeterministically. Note that outside of this module, it's impossible to create a state which has an invalid Sudoku grid, since the only way to update the state handles the check to ensure that the move is legal.<br />
<br />
<haskell><br />
{-# OPTIONS_GHC -fglasgow-exts #-}<br />
module Sudoku <br />
(Sudoku,<br />
readSudoku,<br />
runSudoku,<br />
evalSudoku,<br />
execSudoku,<br />
showSudoku,<br />
valAt, rowAt, colAt, boxAt,<br />
place)<br />
where<br />
import Data.Array.Diff<br />
import MonadNondet<br />
import Control.Monad.State<br />
<br />
-- Nondet here is a drop-in replacement for [] (the list monad) which just runs a little faster.<br />
newtype Sudoku a = Sudoku (StateT (DiffUArray (Int,Int) Int) Nondet a)<br />
deriving (Functor, Monad, MonadPlus)<br />
<br />
{- -- That is, we could also use the following, which works exactly the same way.<br />
newtype Sudoku a = Sudoku (StateT (DiffUArray (Int,Int) Int) [] a)<br />
deriving (Functor, Monad, MonadPlus)<br />
-}<br />
<br />
initialSudokuArray = listArray ((1,1),(9,9)) [0,0..]<br />
<br />
runSudoku (Sudoku k) = runNondet (runStateT k initialSudokuArray)<br />
<br />
evalSudoku = fst . runSudoku<br />
execSudoku = snd . runSudoku<br />
<br />
showSudoku = Sudoku $ do<br />
a <- get<br />
return $ unlines [unwords [show (a ! (i,j)) | j <- [1..9]] | i <- [1..9]]<br />
<br />
readSudoku :: String -> Sudoku ()<br />
readSudoku xs = sequence_ $ do<br />
(i,ys) <- zip [1..9] (lines xs)<br />
(j,n) <- zip [1..9] (words ys)<br />
return $ place (i,j) (read n)<br />
<br />
valAt' (i,j) = do<br />
a <- get<br />
return (a ! (i,j))<br />
<br />
rowAt' (i,j) = mapM valAt' [(i, k) | k <- [1..9]]<br />
<br />
colAt' (i,j) = mapM valAt' [(k, j) | k <- [1..9]] <br />
<br />
boxAt' (i,j) = mapM valAt' [(i' + u, j' + v) | u <- [1..3], v <- [1..3]]<br />
where i' = ((i-1) `div` 3) * 3<br />
j' = ((j-1) `div` 3) * 3<br />
<br />
valAt = Sudoku . valAt'<br />
rowAt = Sudoku . rowAt'<br />
colAt = Sudoku . colAt'<br />
boxAt = Sudoku . boxAt'<br />
<br />
-- This is the least trivial part.<br />
-- It just guards to make sure that the move is legal,<br />
-- and updates the array in the state if it is.<br />
place :: (Int,Int) -> Int -> Sudoku ()<br />
place (i,j) n = Sudoku $ do<br />
v <- valAt' (i,j)<br />
when (v == 0 && n /= 0) $ do<br />
rs <- rowAt' (i,j)<br />
cs <- colAt' (i,j)<br />
bs <- boxAt' (i,j)<br />
guard $ not . any (== n) $ rs ++ cs ++ bs<br />
a <- get<br />
put (a // [((i,j),n)])<br />
</haskell><br />
<br />
This is a fast NonDeterminism monad. It's a drop-in replacement for the list monad in this case. It's twice as fast when compiled with optimisations but a little slower without. You can also find it on the wiki at NonDeterminism.<br />
<br />
I've made a few small modifications to this one to hopefully make it more concretely readable.<br />
<br />
<haskell><br />
{-# OPTIONS_GHC -fglasgow-exts #-}<br />
<br />
module MonadNondet where<br />
<br />
import Control.Monad<br />
import Control.Monad.Trans<br />
<br />
import Control.Monad.Identity<br />
<br />
newtype NondetT m a<br />
= NondetT { foldNondetT :: (forall b. (a -> m b -> m b) -> m b -> m b) }<br />
<br />
runNondetT :: (Monad m) => NondetT m a -> m a<br />
runNondetT m = foldNondetT m (\x xs -> return x) (error "No solution found.")<br />
<br />
instance (Functor m) => Functor (NondetT m) where<br />
fmap f (NondetT g) = NondetT (\cons nil -> g (cons . f) nil)<br />
<br />
instance (Monad m) => Monad (NondetT m) where<br />
return a = NondetT (\cons nil -> cons a nil)<br />
m >>= k = NondetT (\cons nil -> foldNondetT m (\x -> foldNondetT (k x) cons) nil)<br />
<br />
instance (Monad m) => MonadPlus (NondetT m) where<br />
mzero = NondetT (\cons nil -> nil)<br />
m1 `mplus` m2 = NondetT (\cons -> foldNondetT m1 cons . foldNondetT m2 cons)<br />
<br />
instance MonadTrans NondetT where<br />
lift m = NondetT (\cons nil -> m >>= \a -> cons a nil)<br />
<br />
newtype Nondet a = Nondet (NondetT Identity a) deriving (Functor, Monad, MonadPlus)<br />
runNondet (Nondet x) = runIdentity (runNondetT x)<br />
<br />
foldNondet :: Nondet a -> (a -> b -> b) -> b -> b<br />
foldNondet (Nondet nd) cons nil =<br />
runIdentity $ foldNondetT nd (\x xs -> return (cons x (runIdentity xs))) (return nil)<br />
<br />
option :: (MonadPlus m) => [a] -> m a<br />
option = msum . map return<br />
</haskell><br />
<br />
<br />
<br />
<br />
== Simple solver ==<br />
<br />
By AlsonKemp. This solver is probably similar to Cale's but I don't grok the non-deterministic monad...<br />
<br />
Note: this solver is exhaustive and will output all of the solutions, not just the first one. In order to make it non-exhaustive, add a case statement to solve' in order to check "r" and branch on the result.<br />
<br />
<haskell><br />
import System<br />
import Control.Monad<br />
import Data.List<br />
import Data.Array.IO<br />
<br />
type SodokuBoard = IOArray Int Int<br />
<br />
main = do<br />
[f] <- getArgs<br />
a <- newArray (1, 81) 0<br />
readFile f >>= readSodokuBoard a<br />
putStrLn "Original:"<br />
printSodokuBoard a<br />
putStrLn "Solutions:"<br />
solve a (1,1)<br />
<br />
readSodokuBoard a xs = sequence_ $ do (i,ys) <- zip [1..9] (lines xs)<br />
(j,n) <- zip [1..9] (words ys)<br />
return $ writeBoard a (j,i) (read n)<br />
<br />
printSodokuBoard a =<br />
let printLine a y =<br />
mapM (\x -> readBoard a (x,y)) [1..9] >>= mapM_ (putStr . show) in<br />
putStrLn "-----------" >> <br />
mapM_ (\y -> putStr "|" >> printLine a y >> putStrLn "|") [1..9] >> <br />
putStrLn "-----------"<br />
<br />
-- the meat of the program. Checks the current square.<br />
-- If 0, then get the list of nums and try to "solve' "<br />
-- Otherwise, go to the next square.<br />
solve :: SodokuBoard -> (Int, Int) -> IO (Maybe SodokuBoard)<br />
solve a (10,y) = solve a (1,y+1)<br />
solve a (_, 10)= printSodokuBoard a >> return (Just a)<br />
solve a (x,y) = do v <- readBoard a (x,y)<br />
case v of<br />
0 -> availableNums a (x,y) >>= solve' a (x,y)<br />
_ -> solve a (x+1,y)<br />
-- solve' handles the backtacking<br />
where solve' a (x,y) [] = return Nothing<br />
solve' a (x,y) (v:vs) = do writeBoard a (x,y) v -- put a guess onto the board<br />
r <- solve a (x+1,y)<br />
writeBoard a (x,y) 0 -- remove the guess from the board<br />
solve' a (x,y) vs -- recurse over the remainder of the list<br />
<br />
-- get the "taken" numbers from a row, col or box.<br />
getRowNums a y = sequence [readBoard a (x',y) | x' <- [1..9]]<br />
getColNums a x = sequence [readBoard a (x,y') | y' <- [1..9]]<br />
getBoxNums a (x,y) = sequence [readBoard a (x'+u, y'+v) | u <- [0..2], v <- [0..2]] <br />
where x' = (3 * ((x-1) `quot` 3)) + 1<br />
y' = (3 * ((y-1) `quot` 3)) + 1<br />
<br />
-- return the numbers that are available for a particular square<br />
availableNums a (x,y) = do r <- getRowNums a y <br />
c <- getColNums a x<br />
b <- getBoxNums a (x,y)<br />
return $ [0..9] \\ (r `union` c `union` b) <br />
<br />
-- aliases of read and write array that flatten the index<br />
readBoard a (x,y) = readArray a (x+9*(y-1))<br />
writeBoard a (x,y) e = writeArray a (x+9*(y-1)) e<br />
</haskell><br />
<br />
== Complete decision tree ==<br />
<br />
By Henning Thielemann.<br />
<br />
<haskell><br />
module Sudoku where<br />
<br />
{-<br />
This is inspired by John Hughes "Why Functional Programming Matters".<br />
We build a complete decision tree.<br />
That is, all alternatives in a certain depth<br />
have the same number of determined values.<br />
At the bottom of the tree all possible solutions can be found.<br />
Actually the algorithm is very stupid:<br />
In each depth we look for the field with the least admissible choices of numbers<br />
and prune the alternative branches for the other fields.<br />
-}<br />
<br />
import Data.Char (ord, chr)<br />
import Data.Array (Array, range, (!), (//))<br />
import Data.Tree (Tree)<br />
import qualified Data.Tree as Tree<br />
import Data.List (sort, minimumBy)<br />
import Data.Maybe (catMaybes, isNothing, fromMaybe, fromJust)<br />
import qualified Data.Array as Array<br />
<br />
{-<br />
Example:<br />
<br />
ghci -Wall Sudoku.hs<br />
<br />
*Sudoku> mapM putCLn (solutions exampleHawiki0)<br />
-}<br />
<br />
<br />
{- [[ATree]] contains a list of possible alternatives for each position -}<br />
data ATree a = ANode T [[ATree a]]<br />
<br />
type Coord = Int<br />
type Address = (Int,Int,Int,Int)<br />
type Element = Int<br />
<br />
type T = Array Address (Maybe Element)<br />
type Complete = Array Address Element<br />
<br />
fieldBounds :: (Address, Address)<br />
fieldBounds = ((0,0,0,0), (2,2,2,2))<br />
<br />
squareRange :: [(Coord, Coord)]<br />
squareRange = range ((0,0), (2,2))<br />
<br />
alphabet :: [Element]<br />
alphabet = [1..9]<br />
<br />
<br />
<br />
{- * solution -}<br />
<br />
{-<br />
Given two sorted lists,<br />
remove the elements of the first list from the second one.<br />
-}<br />
deleteSorted :: Ord a => [a] -> [a] -> [a]<br />
deleteSorted [] ys = ys<br />
deleteSorted _ [] = []<br />
deleteSorted (x:xs) (y:ys) =<br />
case compare x y of<br />
EQ -> deleteSorted xs ys<br />
LT -> deleteSorted xs (y:ys)<br />
GT -> y : deleteSorted (x:xs) ys<br />
<br />
admissibleNumbers :: [[Maybe Element]] -> [Element]<br />
admissibleNumbers =<br />
foldl (flip deleteSorted) alphabet .<br />
map (sort . catMaybes)<br />
<br />
admissibleAdditions :: T -> Address -> [Element]<br />
admissibleAdditions sudoku (i,j,k,l) =<br />
admissibleNumbers (map ($ sudoku)<br />
[selectRow (i,k),<br />
selectColumn (j,l),<br />
selectSquare (i,j)])<br />
<br />
allAdmissibleAdditions :: T -> [(Address, [Element])]<br />
allAdmissibleAdditions sudoku =<br />
let adds addr =<br />
(addr, admissibleAdditions sudoku addr)<br />
in map adds<br />
(map fst (filter (isNothing . snd)<br />
(Array.assocs sudoku)))<br />
<br />
<br />
<br />
solutionTree :: T -> ATree T<br />
solutionTree sudoku =<br />
let new (addr,elms) =<br />
map (\elm -> solutionTree (sudoku // [(addr, Just elm)])) elms<br />
in ANode sudoku (map new (allAdmissibleAdditions sudoku))<br />
<br />
treeAltToStandard :: ATree T -> Tree T<br />
treeAltToStandard (ANode sudoku subs) =<br />
Tree.Node sudoku (concatMap (map treeAltToStandard) subs)<br />
<br />
{- Convert a tree with alternatives for each position (ATree)<br />
into a normal tree by choosing one position and its alternative values.<br />
We need to consider only one position per level<br />
because the remaining positions are processed in the sub-levels.<br />
With other words: Choosing more than one position<br />
would lead to multiple reports of the same solution.<br />
<br />
For reasons of efficiency<br />
we choose the position with the least number of alternatives.<br />
If this number is zero, the numbers tried so far are wrong.<br />
If this number is one, then the choice is unique, but maybe still wrong.<br />
If the number of alternatives is larger,<br />
we have to check each alternative.<br />
-}<br />
treeAltToStandardOptimize :: ATree T -> Tree T<br />
treeAltToStandardOptimize (ANode sudoku subs) =<br />
let chooseMinLen [] = []<br />
chooseMinLen xs = minimumBy compareLength xs<br />
in Tree.Node sudoku (chooseMinLen<br />
(map (map treeAltToStandardOptimize) subs))<br />
<br />
maybeComplete :: T -> Maybe Complete<br />
maybeComplete sudoku =<br />
fmap (Array.array fieldBounds)<br />
(mapM (uncurry (fmap . (,))) (Array.assocs sudoku))<br />
<br />
{- All leafs are at the same depth,<br />
namely the number of undetermined fields.<br />
That's why we can safely select all Sudokus at the lowest level. -}<br />
solutions :: T -> [Complete]<br />
solutions sudoku =<br />
let err = error "The lowest level should contain complete Sudokus only."<br />
{- "last'" is more efficient than "last" here<br />
because the program does not have to check<br />
whether deeper levels exist.<br />
We know that the tree is as deep<br />
as the number of undefined fields.<br />
This means that dropMatch returns a singleton list.<br />
We don't check that<br />
because then we would lose the efficiency again. -}<br />
last' = head . dropMatch (filter isNothing (Array.elems sudoku))<br />
in map (fromMaybe err . maybeComplete)<br />
(last' (Tree.levels<br />
(treeAltToStandardOptimize (solutionTree sudoku))))<br />
<br />
<br />
<br />
{- * transformations (can be used for construction, too) -}<br />
<br />
standard :: Complete<br />
standard =<br />
Array.listArray fieldBounds<br />
(map (\(i,j,k,l) -> mod (j+k) 3 * 3 + mod (i+l) 3 + 1)<br />
(range fieldBounds))<br />
<br />
<br />
exampleHawiki0, exampleHawiki1 :: T<br />
exampleHawiki0 = fromString (unlines [<br />
" 5 6 1",<br />
" 48 7 ",<br />
"8 52",<br />
"2 57 3 ",<br />
" ",<br />
" 3 69 5",<br />
"79 8",<br />
" 1 65 ",<br />
"5 3 6 "<br />
])<br />
<br />
exampleHawiki1 = fromString (unlines [<br />
" 6 8 ",<br />
" 2 ",<br />
" 1 ",<br />
" 7 1 2",<br />
"5 3 ",<br />
" 4 ",<br />
" 42 1 ",<br />
"3 7 6 ",<br />
" 5 "<br />
])<br />
<br />
<br />
<br />
<br />
check :: Complete -> Bool<br />
check sudoku =<br />
let checkParts select =<br />
all (\addr -> sort (select addr sudoku) == alphabet) squareRange<br />
in all checkParts [selectRow, selectColumn, selectSquare]<br />
<br />
selectRow, selectColumn, selectSquare ::<br />
(Coord,Coord) -> Array Address element -> [element]<br />
selectRow (i,k) sudoku =<br />
map (sudoku!) (range ((i,0,k,0), (i,2,k,2)))<br />
-- map (sudoku!) (map (\(j,l) -> (i,j,k,l)) squareRange)<br />
selectColumn (j,l) sudoku =<br />
map (sudoku!) (range ((0,j,0,l), (2,j,2,l)))<br />
selectSquare (i,j) sudoku =<br />
map (sudoku!) (range ((i,j,0,0), (i,j,2,2)))<br />
<br />
<br />
{- * conversion from and to strings -}<br />
<br />
put, putLn :: T -> IO ()<br />
put sudoku = putStr (toString sudoku)<br />
putLn sudoku = putStrLn (toString sudoku)<br />
<br />
putC, putCLn :: Complete -> IO ()<br />
putC sudoku = putStr (toString (fmap Just sudoku))<br />
putCLn sudoku = putStrLn (toString (fmap Just sudoku))<br />
<br />
fromString :: String -> T<br />
fromString str =<br />
Array.array fieldBounds (concat<br />
(zipWith (\(i,k) -> map (\((j,l),x) -> ((i,j,k,l),x)))<br />
squareRange<br />
(map (zip squareRange . map charToElem) (lines str))))<br />
<br />
toString :: T -> String<br />
toString sudoku =<br />
unlines<br />
(map (\(i,k) -> map (\(j,l) -> elemToChar (sudoku!(i,j,k,l)))<br />
squareRange)<br />
squareRange)<br />
<br />
charToElem :: Char -> Maybe Element<br />
charToElem c =<br />
toMaybe ('0'<=c && c<='9') (ord c - ord '0')<br />
<br />
elemToChar :: Maybe Element -> Char<br />
elemToChar =<br />
maybe ' ' (\c -> chr (ord '0' + c))<br />
<br />
<br />
{- * helper functions -}<br />
<br />
nest :: Int -> (a -> a) -> a -> a<br />
nest 0 _ x = x<br />
nest n f x = f (nest (n-1) f x)<br />
<br />
toMaybe :: Bool -> a -> Maybe a<br />
toMaybe False _ = Nothing<br />
toMaybe True x = Just x<br />
<br />
compareLength :: [a] -> [b] -> Ordering<br />
compareLength (_:xs) (_:ys) = compareLength xs ys<br />
compareLength [] [] = EQ<br />
compareLength (_:_) [] = GT<br />
compareLength [] (_:_) = LT<br />
<br />
{- | Drop as many elements as the first list is long -}<br />
dropMatch :: [b] -> [a] -> [a]<br />
dropMatch xs ys =<br />
map fromJust (dropWhile isNothing<br />
(zipWith (toMaybe . null) (iterate (drop 1) xs) ys))<br />
</haskell><br />
<br />
<br />
== No guessing ==<br />
<br />
By Simon Peyton Jones.<br />
<br />
Since this page is here I thought I'd add a solver I wrote sometime last year. The main constraint I imposed is that it never guesses, and that it outputs a human-comprehensible explanation of every step of its reasoning. That means there are some puzzles it can't solve. I'd be interested to know if there are any puzzles that it gets stuck on where there is a no-guessing way forward. I made no attempt to make it fast.<br />
<br />
There are two files: [[Media:SudokuPJ.hs]] and [[Media:TestPJ.hs]]. The latter just contains a bunch of test cases; I was too lazy to write a proper parser.<br />
<br />
The main entry point is:<br />
<pre><br />
run1 :: Verbosity -> [String] -> Doc<br />
data Verbosity = All | Terse | Final<br />
</pre><br />
The <tt>[String]</tt> the starting board configuration (see the tests file).<br />
<br />
== Just guessing ==<br />
<br />
By ChrisKuklewicz<br />
<br />
This solver is an implementation of Knuth's "Dancing Links" algorithm for solving binary-cover problems. This algorithm represents the constraints as a sparse binary matrix, with 1's as linked nodes. The nodes are in a vertical and a horizontal doubly linked list, and each vertical list is headed by another node that represents one of the constraints. It is interesting as an example of the rare beast in Haskell: a mutable data structure. The code has been rewritten and cleaned up here [[Media:DancingSudoku.lhs]]. Its main routine is designed to handle the input from [http://www.csse.uwa.edu.au/~gordon/sudoku17 sudoku17] on stdin. Currently it only returns the first solution or calls an error, it can be modified (see comments in the file) to return all solutions in a list. An earlier version used ST.Lazy instead of ST.Strict which made operating on puzzles with many solutions more tractable.<br />
<br />
Other trivia: It uses "mdo" and lazyness to initialize some of the doubly linked lists.<br />
<br />
== Very smart, with only a little guessing ==<br />
<br />
by ChrisKuklewicz<br />
<br />
This solver does its best to avoid the branch and guess approach. On the 36628 puzzles of [http://www.csse.uwa.edu.au/~gordon/sudokumin.php length 17] it resorts to guessing on only 164. This extra strength comes from examining the constraints that can only be solved in exactly two ways, and how these constraints overlap and interact with each other and remaining possibilities.<br />
<br />
The [http://evenmere.org/~chrisk/chris-sudoku-deduce.tar.gz source code] compiles to take a list of puzzles as input and produces a description of the number of (good and total) guesses required, as well as a shuffled version of the input. If there was guessing, then the shuffled version could be sent back into the solver to see how the difficulty depended on luck. The list of 164 hard puzzles is included with the source code. The Deduce.hs file contains comments.<br />
<br />
The data is stored in a 9x9x9 boolean array, and the only operations are turning off possibilities and branching. For performance the array is thawed, mutated, and frozen. On the set of 36628 puzzles the speed averages 9.4 puzzles solved per second on a 1.33 GHz G4 (ghc-6.4.1 on OS X). I liked the 9x9x9 array since it emphasized the symmetry of the problem.<br />
<br />
== Generalized solver ==<br />
<br />
By Thorkil Naur<br />
<br />
This Su Doku solver is able to solve classes of Su Doku puzzles that extend the ordinary 9*9 puzzles. The [[SuDokuThorkilNaurDocument|documentation]] describes the solver and also some (to the present author at least) surprising properties of various reduction strategies used when solving Su Doku puzzles.<br />
<br />
The following files comprise the Su Doku solver and related code:<br />
<br />
[[Media:Format.hs]]<br />
[[Media:Merge.hs]]<br />
[[Media:SdkMSol2.hs]]<br />
[[Media:SortByF.hs]]<br />
[[Media:SuDoku.hs]]<br />
[[Media:t40.hs]]<br />
[[Media:t44.hs]]<br />
[[Media:Test.hs]]<br />
<br />
For an example of use, the command<br />
<br />
<pre><br />
runhugs SdkMSol2 \<br />
tn1 \<br />
Traditional 3 \<br />
-#123456789 \<br />
1-53---9- \<br />
---6----- \<br />
------271 \<br />
82------- \<br />
---487--- \<br />
------53- \<br />
23------- \<br />
--7-59--- \<br />
--6---8-4<br />
</pre><br />
<br />
produces output that, among other things, contain<br />
<br />
<pre><br />
tn1: Solutions:<br />
1 7 5 3 2 8 4 9 6<br />
9 4 2 6 7 1 3 8 5<br />
3 6 8 5 9 4 2 7 1<br />
8 2 9 1 3 5 6 4 7<br />
6 5 3 4 8 7 9 1 2<br />
7 1 4 9 6 2 5 3 8<br />
2 3 1 8 4 6 7 5 9<br />
4 8 7 2 5 9 1 6 3<br />
5 9 6 7 1 3 8 2 4<br />
</pre><br />
<br />
== Simple small solver ==<br />
I haven't looked at the other solvers in detail yet, so I'm not sure what is good or bad about mine, but here it is:<br />
<br />
http://darcs.brianweb.net/sudoku/Sudoku.pdf<br />
http://darcs.brianweb.net/sudoku/src/Sudoku.lhs<br />
<br />
-Brian Alliet <brian@brianweb.net><br />
<br />
== Backtrack monad solver ==<br />
<br />
This is a simple but fast solver that uses standard<br />
monads from the [[MonadTemplateLibrary]] in the [[StandardLibraries]].<br />
<br />
Besides being Yet Another Example of a Sudoko solver,<br />
I think it is also a nice somewhat-nontrivial example of<br />
monads in practice.<br />
<br />
The idea is that the monad StateT s [] does backtracking.<br />
It means "iterate over a list while keeping state,<br />
but re-initialize to the original state on each iteration".<br />
<br />
I have several (Unix command line) front-ends to this<br />
module, available upon request. The one I use most creates<br />
and prints six new Sudoku puzzles on a page, with<br />
fine-grain control over the difficulty of the puzzle.<br />
This has made me quite popular among friends and<br />
extended family.<br />
<br />
- [[YitzGale]]<br />
<br />
<haskell><br />
{-# OPTIONS_GHC -fglasgow-exts #-}<br />
<br />
-- Solve a Sudoku puzzle<br />
<br />
module Sudoku where<br />
<br />
import Control.Monad.State<br />
import Data.Maybe (maybeToList)<br />
import Data.List (delete)<br />
<br />
type Value = Int<br />
type Cell = (Int, Int) -- One-based coordinates<br />
<br />
type Puzzle = [[Maybe Value]]<br />
type Solution = [[Value]]<br />
<br />
-- The size of the puzzle.<br />
sqrtSize :: Int<br />
sqrtSize = 3<br />
size = sqrtSize * sqrtSize<br />
<br />
-- Besides the rows and columns, a Sudoku puzzle contains s blocks<br />
-- of s cells each, where s = size.<br />
blocks :: [[Cell]]<br />
blocks = [[(x + i, y + j) | i <- [1..sqrtSize], j <- [1..sqrtSize]] |<br />
x <- [0,sqrtSize..size-sqrtSize],<br />
y <- [0,sqrtSize..size-sqrtSize]]<br />
<br />
-- The one-based number of the block that a cell is contained in.<br />
blockNum :: Cell -> Int<br />
blockNum (row, col) = row - (row - 1) `mod` sqrtSize + (col - 1) `div` sqrtSize<br />
<br />
-- When a Sudoku puzzle has been partially filled in, the following<br />
-- data structure represents the remaining options for how to proceed.<br />
data Options = Options {<br />
cellOpts :: [[[Value]]], -- For each cell, a list of possible values<br />
rowOpts :: [[[Cell ]]], -- For each row and value, a list of cells<br />
colOpts :: [[[Cell ]]], -- For each column and value, a list of cells<br />
blkOpts :: [[[Cell ]]] -- For each block and value, a list of cells<br />
} deriving Show<br />
modifyCellOpts f = do {opts <- get; put $ opts {cellOpts = f $ cellOpts opts}}<br />
modifyRowOpts f = do {opts <- get; put $ opts {rowOpts = f $ rowOpts opts}}<br />
modifyColOpts f = do {opts <- get; put $ opts {colOpts = f $ colOpts opts}}<br />
modifyBlkOpts f = do {opts <- get; put $ opts {blkOpts = f $ blkOpts opts}}<br />
<br />
-- The full set of initial options, before any cells are constrained<br />
initOptions :: Options<br />
initOptions = Options {<br />
cellOpts = [[[1..size] | _ <- [1..size]] | _ <- [1..size]],<br />
rowOpts = [[[(r, c) | c <- [1..size]] | _ <- [1..size]] | r <- [1..size]],<br />
colOpts = [[[(r, c) | r <- [1..size]] | _ <- [1..size]] | c <- [1..size]],<br />
blkOpts = [[b | _ <- [1..size]] | b <- blocks]}<br />
<br />
solve :: Puzzle -> [Solution]<br />
solve puz = evalStateT (initPuzzle >> solutions) initOptions<br />
where<br />
initPuzzle =<br />
sequence_ [fixCell v (r, c) | (row, r) <- zip puz [1..],<br />
(val, c) <- zip row [1..],<br />
v <- maybeToList val]<br />
<br />
-- Build a list of all possible solutions given the current options.<br />
-- We use a list monad INSIDE a state monad. That way,<br />
-- the state is re-initialized on each element of the list iteration,<br />
-- allowing backtracking when an attempt fails (with mzero).<br />
solutions :: StateT Options [] Solution<br />
solutions = solveFromRow 1<br />
where<br />
solveFromRow r<br />
| r > size = return []<br />
| otherwise = do<br />
row <- solveRowFromCol r 1<br />
rows <- solveFromRow $ r + 1<br />
return $ row : rows<br />
solveRowFromCol r c<br />
| c > size = return []<br />
| otherwise = do<br />
vals <- gets $ (!! (c - 1)) . (!! (r - 1)) . cellOpts<br />
val <- lift vals<br />
fixCell val (r, c)<br />
row <- solveRowFromCol r (c + 1)<br />
return $ val : row<br />
<br />
-- Fix the value of a cell.<br />
-- More specifically - update Options to reflect the given value at<br />
-- the given cell, or mzero if that is not possible.<br />
fixCell :: (MonadState Options m, MonadPlus m) =><br />
Value -> Cell -> m ()<br />
fixCell val cell@(row, col) = do<br />
vals <- gets $ (!! (col - 1)) . (!! (row - 1)) . cellOpts<br />
guard $ val `elem` vals<br />
modifyCellOpts $ replace2 row col [val]<br />
modifyRowOpts $ replace2 row val [cell]<br />
modifyColOpts $ replace2 col val [cell]<br />
modifyBlkOpts $ replace2 blk val [cell]<br />
sequence_ [constrainCell v cell | v <- [1..size], v /= val]<br />
sequence_ [constrainCell val (row, c) | c <- [1..size], c /= col]<br />
sequence_ [constrainCell val (r, col) | r <- [1..size], r /= row]<br />
sequence_ [constrainCell val c | c <- blocks !! (blk - 1), c /= cell]<br />
where<br />
blk = blockNum cell<br />
<br />
-- Assert that the given value cannot occur in the given cell.<br />
-- Fail with mzero if that means that there are no options left.<br />
constrainCell :: (MonadState Options m, MonadPlus m) =><br />
Value -> Cell -> m ()<br />
constrainCell val cell@(row, col) = do<br />
constrainOpts row col val cellOpts modifyCellOpts (flip fixCell cell)<br />
constrainOpts row val cell rowOpts modifyRowOpts (fixCell val)<br />
constrainOpts col val cell colOpts modifyColOpts (fixCell val)<br />
constrainOpts blk val cell blkOpts modifyBlkOpts (fixCell val)<br />
where<br />
blk = blockNum cell<br />
constrainOpts x y z getOpts modifyOpts fixOpts = do<br />
zs <- gets $ (!! (y - 1)) . (!! (x - 1)) . getOpts<br />
case zs of<br />
[z'] -> guard (z' /= z)<br />
[_,_] -> when (z `elem` zs) $ fixOpts (head $ delete z zs)<br />
(_:_) -> modifyOpts $ replace2 x y (delete z zs)<br />
_ -> mzero<br />
<br />
-- Replace one element of a list.<br />
-- Coordinates are 1-based.<br />
replace :: Int -> a -> [a] -> [a]<br />
replace i x (y:ys)<br />
| i > 1 = y : replace (i - 1) x ys<br />
| otherwise = x : ys<br />
replace _ _ _ = []<br />
<br />
-- Replace one element of a 2-dimensional list.<br />
-- Coordinates are 1-based.<br />
replace2 :: Int -> Int -> a -> [[a]] -> [[a]]<br />
replace2 i j x (y:ys)<br />
| i > 1 = y : replace2 (i - 1) j x ys<br />
| otherwise = replace j x y : ys<br />
replace2 _ _ _ _ = []<br />
</haskell><br />
<br />
== In-flight entertainment ==<br />
<br />
By Lennart Augustsson<br />
<br />
When on a Lufthansa trans-atlantic flight in 2005 I picked up the in-flight magazine and found a Sudoku puzzle. I decided to finally try one. After solving half of it by hand I got bored. Surely, this mechanical task is better performed by a machine? So I pulled out my laptop and wrote a Haskell program.<br />
<br />
The program below is what I wrote on the plane, except for some comments that I've added. I have made no attempt as making it fast, so the nefarious test puzzle below takes a minute to solve.<br />
<br />
First, the solver without user interface:<br />
<haskell><br />
module Sudoku(Square, Board, ColDigit, RowDigit, BoxDigit, Digit, initialBoard, getBoard, mkSquare, setSquare, solveMany) where<br />
import Char(intToDigit, digitToInt)<br />
import List ((\\), sortBy)<br />
<br />
-- A board is just a list of Squares. It always has all the squares.<br />
data Board = Board [Square]<br />
deriving (Show)<br />
<br />
-- A Square contains its column (ColDigit), row (RowDigit), and<br />
-- which 3x3 box it belongs to (BoxDigit). The box can be computed<br />
-- from the row and column, but is kept for speed.<br />
-- A Square also contains it's status: either a list of possible<br />
-- digits that can be placed in the square OR a fixed digit (i.e.,<br />
-- the square was given by a clue or has been solved).<br />
data Square = Square ColDigit RowDigit BoxDigit (Either [Digit] Digit)<br />
deriving (Show)<br />
<br />
type ColDigit = Digit<br />
type RowDigit = Digit<br />
type BoxDigit = Digit<br />
type Digit = Char -- '1' .. '9'<br />
<br />
-- The initial board, no clues given so all digits are possible in all squares.<br />
initialBoard :: Board<br />
initialBoard = Board [ Square col row (boxDigit col row) (Left allDigits) |<br />
row <- allDigits, col <- allDigits ]<br />
<br />
-- Return a list of rows of a solved board.<br />
-- If used on an unsolved board the return value is unspecified.<br />
getBoard :: Board -> [[Char]]<br />
getBoard (Board sqs) = [ [ getDigit d | Square _ row' _ d <- sqs, row' == row ] | row <- allDigits ]<br />
where getDigit (Right d) = d<br />
getDigit _ = '0'<br />
<br />
allDigits :: [Char]<br />
allDigits = ['1' .. '9']<br />
<br />
-- Compute the box from a column and row.<br />
boxDigit :: ColDigit -> RowDigit -> BoxDigit<br />
boxDigit c r = intToDigit $ (digitToInt c - 1) `div` 3 + (digitToInt r - 1) `div` 3 * 3 + 1<br />
<br />
-- Given a column, row, and a digit make a (solved) square representing this.<br />
mkSquare :: ColDigit -> RowDigit -> Digit -> Square<br />
mkSquare col row c | col `elem` allDigits && row `elem` allDigits && c `elem` allDigits <br />
= Square col row (boxDigit col row) (Right c)<br />
mkSquare _ _ _ = error "Bad mkSquare"<br />
<br />
-- Place a given Square on a Board and return the new Board.<br />
-- Illegal setSquare calls will just error out. The main work here<br />
-- is to remove the placed digit from the other Squares on the board<br />
-- that are in the same column, row, or box.<br />
setSquare :: Square -> Board -> Board<br />
setSquare sq@(Square scol srow sbox (Right d)) (Board sqs) = Board (map set sqs)<br />
where set osq@(Square col row box ds) =<br />
if col == scol && row == srow then sq<br />
else if col == scol || row == srow || box == sbox then (Square col row box (sub ds))<br />
else osq<br />
sub (Left ds) = Left (ds \\ [d])<br />
sub (Right d') | d == d' = error "Impossible setSquare"<br />
sub dd = dd<br />
setSquare _ _ = error "Bad setSquare"<br />
<br />
-- Get the unsolved Squares from a Board.<br />
getLeftSquares :: Board -> [Square]<br />
getLeftSquares (Board sqs) = [ sq | sq@(Square _ _ _ (Left _)) <- sqs ]<br />
<br />
-- Given an initial Board return all the possible solutions starting<br />
-- from that Board.<br />
-- Note, this all happens in the list monad and makes use of lazy evaluation<br />
-- to avoid work. Using the list monad automatically handles all the backtracking<br />
-- and enumeration of solutions.<br />
solveMany :: Board -> [Board]<br />
solveMany brd =<br />
case getLeftSquares brd of<br />
[] -> return brd -- Nothing unsolved remains, we are done.<br />
sqs -> do<br />
-- Sort the unsolved Squares by the ascending length of the possible<br />
-- digits. Pick the first of those so we always solve forced Squares<br />
-- first.<br />
let Square c r b (Left ds) : _ = sortBy leftLen sqs<br />
leftLen (Square _ _ _ (Left ds1)) (Square _ _ _ (Left ds2)) = compare (length ds1) (length ds2)<br />
leftLen _ _ = error "bad leftLen"<br />
sq <- [ Square c r b (Right d) | d <- ds ] -- Try all possible moves<br />
solveMany (setSquare sq brd) -- And solve the extended Board.<br />
</haskell><br />
<br />
Second, a simple user interface (a different user interface that I have is an Excell addin):<br />
<haskell><br />
module Main where<br />
import Sudoku<br />
<br />
-- Col Row Digit<br />
solve :: [((Char, Char), Char)] -> [[Char]]<br />
solve crds =<br />
let brd = foldr add initialBoard crds<br />
add ((c, r), d) = setSquare (mkSquare c r d)<br />
in case solveMany brd of<br />
[] -> error "No solutions"<br />
b : _ -> getBoard b<br />
<br />
-- The parse assumes that squares without a clue<br />
-- contain '0'.<br />
main = interact $<br />
unlines . -- turn it into lines<br />
map (concatMap (:" ")) . -- add a space after each digit for readability<br />
solve . -- solve the puzzle<br />
filter ((`elem` ['1'..'9']) . snd) . -- get rid of non-clues<br />
zip [ (c, r) | r <- ['1'..'9'], c <- ['1'..'9'] ] . -- pair up the digits with their coordinates<br />
filter (`elem` ['0'..'9']) -- get rid of non-digits<br />
</haskell><br />
<br />
<br />
== Sudoku incrementally, à la Bird ==<br />
<br />
:As part of a new [http://cs.nott.ac.uk/~gmh/afp.html Advanced Functional Programming] course in Nottingham, [http://cs.nott.ac.uk/~gmh/ Graham Hutton] presented a Haskell approach to solving Sudoku puzzles, based upon notes from [http://web.comlab.ox.ac.uk/oucl/work/richard.bird/ Richard Bird]. The approach is classic Bird: start with a simple but impractical solver, whose efficiency is then improved in a series of steps. The end result is an elegant program that is able to solve any Sudoku puzzle in an instant. Its also an excellent example of what has been termed wholemeal programming focusing on entire data structures rather than their elements. (Transplanted from [http://lambda-the-ultimate.org/node/772 LtU].)<br />
<br />
A full talk-through of the evolution of the code may be found [http://cs.nott.ac.uk/~gmh/sudoku.lhs under the course page]. --[[User:Liyang|Liyang]] 13:35, 27 July 2006 (UTC)<br />
<br />
I've also written [[Media:sudokuWss.hs]], a parallel version of this solver. It uses STM to prune the boxes, columns, and rows simultaneously, which is kind of cool. I'm pretty sure it can be optimized quite a bit... --WouterSwierstra, August 2007.<br />
<br />
== 607 bytes / 12 lines ==<br />
<br />
A super quick attempt at a smallest solution, based on the<br />
[http://web.math.unifi.it/users/maggesi/haskell_sudoku_solver.html 707 byte sudoku] solver:<br />
<br />
<haskell><br />
import List<br />
<br />
main = putStr . unlines . map disp . solve . return . input =<< getContents<br />
<br />
solve s = foldr (\p l -> [mark (p,n) s | s <- l, n <- s p]) s idx<br />
<br />
mark (p@(i,j),n) s q@(x,y)<br />
| p == q = [n]<br />
| x == i || y == j || e x i && e y j = delete n (s q)<br />
| otherwise = s q<br />
where e a b = div (a-1) 3 == div (b-1) 3<br />
<br />
disp s = unlines [unwords [show $ head $ s (i,j) | j <- [1..9]] | i <- [1..9]]<br />
<br />
input s = foldr mark (const [1..9]) $<br />
[(p,n) | (p,n) <- zip idx $ map read $ lines s >>= words, n>0]<br />
<br />
idx = [(i,j) | i <- [1..9], j <- [1..9]]<br />
</haskell><br />
<br />
dons 07:54, 2 December 2006 (UTC)<br />
<br />
== A parallel solver ==<br />
<br />
A parallel version of Richard Bird's function pearl solver by Wouter<br />
Swierstra:<br />
<br />
http://www.haskell.org/sitewiki/images/1/12/SudokuWss.hs<br />
<br />
== Another simple solver ==<br />
<br />
One day I wrote a completely naive sudoku solver which tried all possibilities to try arrays in Haskell. It works, however I doubt that I'll see it actually solve a puzzle during my remaining lifetime.<br />
<br />
So I set out to improve it. The new version still tries all possibilities, but it starts with the cell that has a minimal number of possibilities.<br />
<br />
<haskell><br />
import Array<br />
import List<br />
import System<br />
<br />
-- ([Possible Entries], #Possible Entries)<br />
type Field = Array (Int,Int) ([Int], Int)<br />
<br />
-- Fields are Strings of Numbers with 0 in empty cells<br />
readField ::String -> Field<br />
readField f = listArray ((1,1),(9,9)) (map (\j -> let n=read [j]::Int in if n==0 then ([0..9],9) else ([n],0)) f)<br />
<br />
-- x y wrong way -> reading wrong? no effect on solution though<br />
showField :: Field -> String<br />
showField f = unlines [concat [show $ entry (f!(y,x))|x<-[1..9]]|y<-[1..9]]<br />
<br />
printField :: Maybe Field -> String<br />
printField (Just f) = concat [concat [show $ entry f!(y,x))|x<-[1..9]]|y<-[1..9]]<br />
printField Nothing = "No solution"<br />
<br />
-- true if cell is empty<br />
isEmpty :: ([Int],Int) -> Bool<br />
isEmpty (xs,_) = xs == [0]<br />
<br />
entry :: ([Int],Int) -> Int<br />
entry = head.fst<br />
<br />
-- 0 possibilties left, no emtpy fields<br />
done :: Field -> Bool<br />
done a = let l=elems a in 0==foldr (\(_,x) y -> x+y) 0 l && all (not.isEmpty) l<br />
<br />
--return column/row/square containing coords (x,y), excluding (x,y)<br />
column::Field ->(Int,Int) -> [Int]<br />
column a ~(x,y)= [entry $ a!(i,y)|i<-[1..9],i/=x]<br />
<br />
row :: Field -> (Int,Int) -> [Int]<br />
row a ~(x,y)= [entry $ a!(x,j)|j<-[1..9],j/=y]<br />
<br />
square :: Field -> (Int, Int)-> [Int]<br />
square a ~(x,y) = block <br />
where <br />
n = head $ dropWhile (<x-3) [0,3,6]<br />
m = head $ dropWhile (<y-3) [0,3,6]<br />
block = [entry $ a!(i+n,j+m)|i<-[1..3],j<-[1..3],x/=i+n || y/=j+m]<br />
<br />
-- remove invalid possibilities<br />
remPoss :: Field -> Field<br />
remPoss f =array ((1,1),(9,9)) $ map remPoss' (assocs f)<br />
where <br />
others xy= filter (/=0) $ row f xy ++ column f xy ++ square f xy<br />
remPoss' ~(i,(xs,n))<br />
| n/=0 = let nxs= filter ( flip notElem (others i) ) xs in (i,(nxs,length $ filter (/=0) nxs))<br />
| otherwise = (i,(xs,n))<br />
<br />
-- remove invalid fields, i.e. contains empty cell without filling possibilities<br />
remInv :: [Field] -> [Field]<br />
remInv = filter (all (\(_,(x,_)) -> x/=[0]).assocs)<br />
<br />
<br />
genMoves :: (Int,Int) -> Field -> [Field]<br />
genMoves xy f = remInv $ map remPoss [f // [(xy,([poss!!i],0))]|i<-[0..num-1]]<br />
where <br />
poss = tail $ fst (f!xy)<br />
num = snd (f!xy)<br />
<br />
--always try the entry with least possibilties first<br />
moves :: Field -> [Field]<br />
moves f = genMoves bestOne f<br />
where<br />
-- remove all with 0 possibilities, select the one with minimum possibilities<br />
bestOne =fst $ minimumBy (\(_,(_,n)) (_,(_,m)) -> compare n m) list <br />
list = ((filter (\(_,(_,x)) -> x/=0).assocs) f)<br />
<br />
play :: [Field] -> Maybe Field<br />
play (f:a)<br />
| done f= Just f<br />
| otherwise = play (moves f++a)<br />
play [] = Nothing<br />
<br />
-- reads a file with puzzles, path as argument<br />
main :: IO ()<br />
main = do <br />
path <- getArgs<br />
inp<-readFile (path!!0)<br />
let x=lines inp<br />
let erg=map (printField.play) (map ((\x->[x]).remPoss.readField) x)<br />
writeFile "./out.txt" (unlines erg)<br />
</haskell><br />
<br />
I let it run on the 41747 minimal puzzles. On a 2.66 GHz Intel Xeon it took 15441m1.920s, which is about 22 seconds per puzzle. It could probably be further improved by making remPoss smarter. At the time of writing this the naive version from which I started is crunching for 20 ''days'' on a simple puzzle with 32 hints. I'd say that's quite a performance improvement.<br />
<br />
== Solving Every Sudoku Puzzle ==<br />
<br />
By Manu<br />
<br />
This is an attempt to implement in Haskell, Peter Norvig's sudoku solver :<br />
more explanations here : http://norvig.com/sudoku.html<br />
<br />
This program greatly benefited from Daniel Fischer's refactoring (80 times faster !).<br />
It takes just above 1 second, on a MacBook Pro 2.33GHz Intel Core 2 Duo, to solve the 95 puzzles found here : http://norvig.com/top95.txt<br />
<br />
<haskell><br />
module Main where<br />
<br />
import Data.List hiding (lookup)<br />
import Data.Array<br />
import Control.Monad<br />
import Data.Maybe<br />
<br />
--------------------------------------------------<br />
-- Types<br />
type Digit = Char<br />
type Square = (Char,Char)<br />
type Unit = [Square]<br />
<br />
-- We represent our grid as an array<br />
type Grid = Array Square [Digit]<br />
<br />
<br />
--------------------------------------------------<br />
-- Setting Up the Problem<br />
<br />
rows = "ABCDEFGHI"<br />
cols = "123456789"<br />
digits = "123456789"<br />
box = (('A','1'),('I','9'))<br />
<br />
cross :: String -> String -> [Square]<br />
cross rows cols = [ (r,c) | r <- rows, c <- cols ]<br />
<br />
squares :: [Square]<br />
squares = cross rows cols -- [('A','1'),('A','2'),('A','3'),...]<br />
<br />
peers :: Array Square [Square]<br />
peers = array box [(s, set (units!s)) | s <- squares ]<br />
where<br />
set = nub . concat<br />
<br />
unitlist :: [Unit]<br />
unitlist = [ cross rows [c] | c <- cols ] ++<br />
[ cross [r] cols | r <- rows ] ++<br />
[ cross rs cs | rs <- ["ABC","DEF","GHI"], <br />
cs <- ["123","456","789"]]<br />
<br />
-- this could still be done more efficiently, but what the heck...<br />
units :: Array Square [Unit]<br />
units = array box [(s, [filter (/= s) u | u <- unitlist, elem s u ]) | <br />
s <- squares]<br />
<br />
<br />
allPossibilities :: Grid<br />
allPossibilities = array box [ (s,digits) | s <- squares ]<br />
<br />
--------------------------------------------------<br />
-- Parsing a grid into an Array<br />
<br />
parsegrid :: String -> Maybe Grid<br />
parsegrid g = do regularGrid g<br />
foldM assign allPossibilities (zip squares g)<br />
<br />
where regularGrid :: String -> Maybe String<br />
regularGrid g = if all (\c -> (elem c "0.-123456789")) g<br />
then (Just g)<br />
else Nothing<br />
<br />
--------------------------------------------------<br />
-- Propagating Constraints<br />
<br />
assign :: Grid -> (Square, Digit) -> Maybe Grid<br />
assign g (s,d) = if (elem d digits)<br />
-- check that we are assigning a digit and not a '.'<br />
then do<br />
let ds = g ! s<br />
toDump = delete d ds<br />
foldM eliminate g (zip (repeat s) toDump)<br />
else return g<br />
<br />
eliminate :: Grid -> (Square, Digit) -> Maybe Grid<br />
eliminate g (s,d) = <br />
let cell = g ! s in<br />
if not (elem d cell) then return g -- already eliminated<br />
-- else d is deleted from s' values<br />
else do let newCell = delete d cell<br />
newV = g // [(s,newCell)]<br />
newV2 <- case newCell of<br />
-- contradiction : Nothing terminates the computation<br />
[] -> Nothing<br />
-- if there is only one value left in s, remove it from peers<br />
[d'] -> do let peersOfS = peers ! s<br />
foldM eliminate newV (zip peersOfS (repeat d'))<br />
-- else : return the new grid<br />
_ -> return newV<br />
-- Now check the places where d appears in the peers of s<br />
foldM (locate d) newV2 (units ! s)<br />
<br />
locate :: Digit -> Grid -> Unit -> Maybe Grid<br />
locate d g u = case filter (elem d . (g !)) u of<br />
[] -> Nothing<br />
[s] -> assign g (s,d)<br />
_ -> return g<br />
<br />
--------------------------------------------------<br />
-- Search<br />
<br />
search :: Grid -> Maybe Grid<br />
search g = <br />
case [(l,(s,xs)) | (s,xs) <- assocs g, let l = length xs, l /= 1] of<br />
[] -> return g<br />
ls -> do let (_,(s,ds)) = minimum ls<br />
msum [assign g (s,d) >>= search | d <- ds]<br />
<br />
solve :: String -> Maybe Grid<br />
solve str = do<br />
grd <- parsegrid str<br />
search grd<br />
<br />
--------------------------------------------------<br />
-- Display solved grid<br />
<br />
printGrid :: Grid -> IO ()<br />
printGrid = putStrLn . gridToString<br />
<br />
gridToString :: Grid -> String<br />
gridToString g =<br />
let l0 = elems g<br />
-- [("1537"),("4"),...] <br />
l1 = (map (\s -> " " ++ s ++ " ")) l0<br />
-- ["1 "," 2 ",...] <br />
l2 = (map concat . sublist 3) l1<br />
-- ["1 2 3 "," 4 5 6 ", ...]<br />
l3 = (sublist 3) l2<br />
-- [["1 2 3 "," 4 5 6 "," 7 8 9 "],...] <br />
l4 = (map (concat . intersperse "|")) l3<br />
-- ["1 2 3 | 4 5 6 | 7 8 9 ",...]<br />
l5 = (concat . intersperse [line] . sublist 3) l4<br />
in unlines l5 <br />
where sublist n [] = []<br />
sublist n xs = take n xs : sublist n (drop n xs)<br />
line = hyphens ++ "+" ++ hyphens ++ "+" ++ hyphens<br />
hyphens = take 9 (repeat '-')<br />
<br />
--------------------------------------------------<br />
<br />
main :: IO ()<br />
main = do<br />
grids <- fmap lines $ readFile "top95.txt"<br />
mapM_ printGrid $ mapMaybe solve grids<br />
</haskell><br />
<br />
== Concurrent STM Solver ==<br />
<br />
[[Liyang]] wrote some [[Liyang/sudoku.hs|applicative functor porn utilising STM]]. It's pretty but slow. Suggestions for speeding it up would be very welcome.<br />
<br />
== Add your own ==<br />
<br />
If you have a Sudoku solver you're proud of, put it here. This ought to be a good way of helping people learn some fun, intermediate-advanced techniques in Haskell.<br />
<br />
== Test boards ==<br />
<br />
Here's an input file to test the solvers on. Zeroes represent blanks.<br />
<pre><br />
0 5 0 0 6 0 0 0 1<br />
0 0 4 8 0 0 0 7 0<br />
8 0 0 0 0 0 0 5 2<br />
2 0 0 0 5 7 0 3 0<br />
0 0 0 0 0 0 0 0 0<br />
0 3 0 6 9 0 0 0 5<br />
7 9 0 0 0 0 0 0 8<br />
0 1 0 0 0 6 5 0 0<br />
5 0 0 0 3 0 0 6 0<br />
</pre><br />
<br />
A nefarious one:<br />
<br />
<pre><br />
0 0 0 0 6 0 0 8 0<br />
0 2 0 0 0 0 0 0 0<br />
0 0 1 0 0 0 0 0 0<br />
0 7 0 0 0 0 1 0 2<br />
5 0 0 0 3 0 0 0 0<br />
0 0 0 0 0 0 4 0 0<br />
0 0 4 2 0 1 0 0 0<br />
3 0 0 7 0 0 6 0 0<br />
0 0 0 0 0 0 0 5 0 <br />
</pre><br />
<br />
Chris Kuklewicz writes, "You can go get the 41,747 distict minimal puzzles from<br />
[http://www.csse.uwa.edu.au/~gordon/sudokumin.php csse.uwa.edu] that have only 17 clues. Then you can run all of them through your program to locate the most evil ones, and use them on your associates."</div>Liyanghttps://wiki.haskell.org/index.php?title=Liyang/sudoku.hs&diff=15395Liyang/sudoku.hs2007-09-03T21:46:30Z<p>Liyang: first public version</p>
<hr />
<div>It's slow. That makes me sad.<br />
<br />
== sudoku.hs ==<br />
<br />
<haskell><br />
{-# OPTIONS -cpp -fglasgow-exts -fno-monomorphism-restriction #-}<br />
{- -}<br />
<br />
#define EXHAUSTIVE 0<br />
#define FORK_WORKERS 1<br />
#define FORK_GUESSES 2<br />
#define FORK_OS 4<br />
<br />
#define FLAG(flag) (1 << flag)<br />
#define OPTION(flag) (OPTIONS & FLAG(flag))<br />
<br />
#ifndef OPTIONS<br />
# define OPTIONS ( FLAG(FORK_WORKERS) )<br />
{- |FLAG(FORK_GUESSES) |FLAG(EXHAUSTIVE) -}<br />
#endif<br />
<br />
module Main where<br />
<br />
import Prelude hiding ( all, any, concat, elem, foldl, pi )<br />
import Control.Arrow ( (***), (&&&) )<br />
import Control.Applicative<br />
import Control.Monad<br />
import Control.Concurrent<br />
import Control.Concurrent.STM<br />
import Control.Exception<br />
import Data.Bits<br />
import Data.Char<br />
import Data.List ( intersperse, unfoldr )<br />
import Data.Maybe<br />
import Data.Monoid<br />
import Data.Foldable<br />
import Data.Traversable<br />
import Data.Ix<br />
<br />
--{{{ Tensor/Cartesian product on collections.<br />
tensor :: (Applicative f, Applicative g) => (alpha -> beta -> gamma) -> f alpha -> g beta -> f (g gamma)<br />
tensor f a b = (\ x -> f <$> pure x <*> b) <$> a<br />
--}}}<br />
<br />
--{{{ Indexable collections.<br />
class Indexable f i | f -> i where<br />
indexModify :: i -> (alpha -> (beta, alpha)) -> f alpha -> (beta, f alpha)<br />
<br />
-- Sometimes we only want to index.<br />
pi :: Indexable f i => i -> f alpha -> alpha<br />
pi i = fst . indexModify i (id &&& id)<br />
<br />
-- Or to just modify.<br />
modify :: Indexable f i => i -> (alpha -> alpha) -> (f alpha -> f alpha)<br />
modify i f = snd . indexModify i (id &&& f)<br />
--}}}<br />
<br />
--{{{ Three is the magic number: base three ordinals.<br />
data Ti = T0 | T1 | T2 deriving (Show, Read, Bounded, Eq, Enum, Ord, Ix)<br />
type TiTi = (Ti, Ti)<br />
type Coord = (TiTi, TiTi)<br />
<br />
boundedSize :: (Bounded alpha, Ix alpha) => alpha -> Int<br />
boundedSize = rangeSize . (m0 &&& m1) where<br />
m0, m1 :: Bounded alpha => alpha -> alpha<br />
m0 w = minBound; m1 w = maxBound<br />
<br />
fromPair :: (Bounded alpha, Ix alpha, Enum alpha) =><br />
(beta -> Int) -> (beta, alpha) -> Int<br />
fromPair f (y, x) = boundedSize x * f y + fromEnum x<br />
<br />
toPair :: (Bounded alpha, Ix alpha, Enum alpha) =><br />
(Int -> beta) -> Int -> (beta, alpha)<br />
toPair f n = result where -- this is sick:<br />
result = (f *** toEnum) (n `divMod` boundedSize (snd result))<br />
<br />
instance<br />
( Bounded alpha, Ix alpha, Enum alpha<br />
, Bounded beta, Ix beta, Enum beta )<br />
=> Enum (beta, alpha) where<br />
fromEnum = fromPair fromEnum<br />
toEnum = toPair toEnum<br />
--}}}<br />
<br />
--{{{ Triple: 3.<br />
data Triple alpha = T alpha alpha alpha deriving (Show, Bounded, Eq, Ord, Ix)<br />
<br />
instance Functor Triple where<br />
fmap = fmapDefault<br />
instance Foldable Triple where<br />
foldMap = foldMapDefault<br />
instance Traversable Triple where<br />
traverse f (T x y z) = T <$> f x <*> f y <*> f z<br />
<br />
iTriple = T T0 T1 T2<br />
instance Indexable Triple Ti where<br />
indexModify i f (T a b c) = case i of<br />
T0 -> (x, T a' b c ) where (x, a') = f a<br />
T1 -> (x, T a b' c ) where (x, b') = f b<br />
T2 -> (x, T a b c' ) where (x, c') = f c<br />
<br />
instance Applicative Triple where<br />
pure x = T x x x<br />
T f g h <*> T x y z = T (f x) (g y) (h z)<br />
<br />
instance (Bounded alpha, Ix alpha, Enum alpha) => Enum (Triple alpha) where<br />
fromEnum (T a b c) = (fromPair . fromPair) fromEnum ((a, b), c)<br />
toEnum n = T a b c where ((a, b), c) = (toPair . toPair) toEnum n<br />
<br />
instance Read alpha => Read (Triple alpha) where<br />
readsPrec _ s = [ (T a b c, v) |<br />
(a, t) <- reads s, (b, u) <- reads t, (c, v) <- reads u ]<br />
<br />
showTriple :: String -> (alpha -> String) -> Triple alpha -> String<br />
showTriple d s = concat . intersperse d . toList . fmap s<br />
--}}}<br />
<br />
--{{{ Region: 3x3; aka rows, cols, boxes, cell constraints... whatever.<br />
newtype Region alpha = Region { unRegion :: Triple (Triple alpha) }<br />
deriving Eq<br />
<br />
instance Functor Region where<br />
fmap = fmapDefault<br />
instance Foldable Region where<br />
foldMap = foldMapDefault<br />
instance Traversable Region where<br />
traverse f (Region tt) = Region <$> traverse (traverse f) tt<br />
<br />
iRegion = Region (tensor (,) iTriple iTriple)<br />
instance Indexable Region TiTi where<br />
indexModify (j, i) f (Region tt) = (id *** Region) $<br />
indexModify j (indexModify i f) tt<br />
<br />
instance Applicative Region where<br />
pure = Region . pure . pure<br />
Region ttf <*> Region ttx = Region ((<*>) <$> ttf <*> ttx)<br />
<br />
instance Read alpha => Read (Region alpha) where<br />
readsPrec p s = (Region *** id) <$> readsPrec p s<br />
<br />
instance Show alpha => Show (Region alpha) where<br />
showsPrec _ = (++) . showTriple " " (showTriple " " show) . unRegion<br />
--}}}<br />
<br />
--{{{ Cell: 3x3; different Read/Show, but otherwise identical to Regions.<br />
newtype Cell alpha = Cell { unCell :: Region alpha }<br />
deriving Eq<br />
<br />
instance Functor Cell where<br />
fmap = fmapDefault<br />
instance Foldable Cell where<br />
foldMap = foldMapDefault<br />
instance Traversable Cell where<br />
traverse f (Cell r) = Cell <$> traverse f r<br />
<br />
iCell = Cell iRegion<br />
instance Indexable Cell TiTi where<br />
indexModify ji f (Cell r) = (id *** Cell) (indexModify ji f r)<br />
<br />
instance Applicative Cell where<br />
pure = Cell . pure<br />
Cell rf <*> Cell rx = Cell (rf <*> rx)<br />
<br />
instance Read (Cell Bool) where<br />
readsPrec _ s = case dropWhile isSpace s of<br />
'{' : '-' : c : '-' : '}' : t -> reads (c : t)<br />
'{' : a : b : c : '}' : t | all isOctDigit mask -><br />
[(partialCell, t)] where<br />
mask = T a b c<br />
partialCell = (Cell . Region . fmap (toEnum . digitToInt)) mask<br />
c : t | c `elem` ".0_-?" -><br />
[(emptyCell, t)] where<br />
emptyCell = (Cell . Region . pure . pure) True<br />
c : t | c >= '1' && c <= '9' -><br />
[(fullCell, t)] where<br />
fullCell = (Cell . Region . toEnum . (2 ^) . (8 -) . pred . read) [c]<br />
_ -> []<br />
<br />
instance Show (Cell Bool) where<br />
show cell@(Cell (Region tt)) = case solutions cell of<br />
[n] -> "{-" ++ show (fromEnum n + 1) ++ "-}"<br />
_ -> "{" ++ showTriple "" (show . fromEnum) tt ++ "}"<br />
--}}}<br />
<br />
--{{{ Grid: 3x3 x 3x3<br />
newtype Grid alpha = Grid { unGrid :: Region (Region alpha) }<br />
deriving Eq<br />
<br />
instance Functor Grid where<br />
fmap = fmapDefault<br />
instance Foldable Grid where<br />
foldMap = foldMapDefault<br />
instance Traversable Grid where<br />
traverse f (Grid rr) = Grid <$> traverse (traverse f) rr<br />
<br />
iGrid = Grid (tensor (,) iRegion iRegion)<br />
instance Indexable Grid Coord where<br />
indexModify (lk, ji) f (Grid rr) = (id *** Grid) $<br />
indexModify lk (indexModify ji f) rr<br />
<br />
instance Applicative Grid where<br />
pure = Grid . pure . pure<br />
Grid rrf <*> Grid rrx = Grid ((<*>) <$> rrf <*> rrx)<br />
<br />
instance Read alpha => Read (Grid alpha) where<br />
readsPrec p s = (Grid *** id) <$> readsPrec p s<br />
<br />
instance Show alpha => Show (Grid alpha) where<br />
show = showTriple "\n\n" (showTriple "\n" show) . unRegion . unGrid where<br />
--}}}<br />
<br />
--{{{ Cube: 3x3 x 3x3 x 3x3; grids with cell constraints.<br />
newtype Cube alpha = Cube { unCube :: Grid (Cell alpha) }<br />
deriving Eq<br />
<br />
instance Functor Cube where<br />
fmap = fmapDefault<br />
instance Foldable Cube where<br />
foldMap = foldMapDefault<br />
instance Traversable Cube where<br />
traverse f (Cube gc) = Cube <$> traverse (traverse f) gc<br />
<br />
instance Applicative Cube where<br />
pure = Cube . pure . pure<br />
Cube gcf <*> Cube gcx = Cube ((<*>) <$> gcf <*> gcx)<br />
<br />
instance Read (Cube Bool) where<br />
readsPrec p s = (Cube *** id) <$> readsPrec p s<br />
<br />
instance Show (Cube Bool) where<br />
show = show . unCube<br />
--}}}<br />
<br />
--{{{ views: returns alternative representations of the grid.<br />
type Auto alpha = alpha -> alpha<br />
type Rank6 t alpha = t (t (t (t (t (t alpha)))))<br />
<br />
views :: Cube alpha -> Region (Cube alpha)<br />
views cube = (assemble . ($ disassemble cube)) <$> mkViews where<br />
mkViews :: (Applicative t, Traversable t) => Region (Auto (Rank6 t alpha))<br />
mkViews = (fmap traversals . Region) $ T<br />
-- 0 1 2 3 4 5<br />
-- J I l k n m -- row<br />
-- l k J I n m -- col<br />
-- l k n m J I -- bit<br />
(T [0,1] [2,3] [4,5])<br />
-- J l I k n m -- box<br />
-- l k J n I m -- ?<br />
-- I l k n J m -- ?<br />
(T [0,2] [2,4] [4,0])<br />
-- l J k I n m -- ?<br />
-- l k n J m I -- ?<br />
-- l I k n m J -- ?<br />
(T [1,3] [3,5] [5,1])<br />
<br />
disassemble :: Cube alpha -> Rank6 Triple alpha<br />
disassemble = unRegion . fmap unRegion . unGrid . fmap (unRegion . unCell) . unCube<br />
assemble :: Rank6 Triple alpha -> Cube alpha<br />
assemble = Cube . fmap (Cell . Region) . Grid . fmap Region . Region<br />
<br />
traversals :: (Applicative t, Traversable t) => [Int] -> Auto (Rank6 t alpha)<br />
traversals = appEndo . fold . fmap (trs !!) . reverse . reindex where<br />
trs :: (Applicative t, Traversable t) => [Endo (Rank6 t alpha)]<br />
trs = Endo <$> [tr0, tr1, tr2, tr3, tr4, tr5] where<br />
tr0 = id :: (Applicative t, Traversable t) => Auto (t alpha)<br />
tr1 = traverse tr0 :: (Applicative t, Traversable t) => Auto (t (t alpha))<br />
tr2 = traverse tr1 :: (Applicative t, Traversable t) => Auto (t (t (t alpha)))<br />
tr3 = traverse tr2 :: (Applicative t, Traversable t) => Auto (t (t (t (t alpha))))<br />
tr4 = traverse tr3 :: (Applicative t, Traversable t) => Auto (t (t (t (t (t alpha)))))<br />
tr5 = traverse tr4 :: (Applicative t, Traversable t) => Auto (t (t (t (t (t (t alpha))))))<br />
<br />
-- Calculate the traversals needed to obtain the required reindexing.<br />
-- Not always the most efficient in terms of operations needed...<br />
reindex :: [Int] -> [Int]<br />
reindex = unfoldr shifts . reverse where<br />
shifts l = case l of<br />
[] -> Nothing<br />
0:t -> shifts t<br />
1:0:t -> shifts t<br />
h:t -> Just (h, flip fmap t $ \ d -> if h > d then d + 1 else d)<br />
<br />
-- Just the rows, columns and boxes plzkthx.<br />
decompose :: Cube alpha -> Triple (Cube alpha)<br />
decompose grid = flip pi vs <$> T (T0, T0) (T0, T1) (T1, T0) where<br />
vs = views grid<br />
<br />
-- Select the relevalt row/col/box, given an (y, x) offset.<br />
select :: Triple (Cube alpha) -> Coord -> Triple (Region (Cell alpha))<br />
select rcbs ((l, k), (j, i)) = pi <$><br />
T (l, k) (j, i) (l, j) <*> (unGrid . unCube <$> rcbs)<br />
--}}}<br />
<br />
--{{{ solutions: produce a list of candidates, given a cell.<br />
solutions :: Cell Bool -> [TiTi]<br />
solutions = foldl (\ l (i, b) -> if b then i:l else l) [] . (fmap (,) iCell <*>)<br />
--}}}<br />
<br />
--{{{ collapse: locate first non-solved cell with fewest possibilities and collapse it down.<br />
collapse :: (Functor f, Foldable f, Enum i, Indexable f i) =><br />
f (Bool, Cell Bool) -> Maybe [f (Cell Bool)]<br />
collapse cells = makeGrids <$> collapseMin cells where<br />
makeGrids (sols, coord) =<br />
[ modify coord (const cell) (snd <$> cells) | cell <- sols ]<br />
<br />
collapseMin :: (Functor f, Foldable f, Enum i, Indexable f i) =><br />
f (Bool, Cell Bool) -> Maybe ([Cell Bool], i)<br />
collapseMin = uncurry (fmap . const . fmap toEnum) . snd .<br />
foldl minCell (0, (undefined, Nothing)) . fmap collapseCell where<br />
-- undefined? Madness! But I want Ord (Maybe Int) on length and the<br />
-- (fmap . const . fmap . toEnum) ensures the insanity never escapes<br />
<br />
-- (counter :: Int, ((solutions :: [Cell Bool], index :: Int), length :: Maybe Int))<br />
minCell :: (Int, (([Cell Bool], Int), Maybe Int)) -><br />
Maybe [Cell Bool] -> (Int, (([Cell Bool], Int), Maybe Int))<br />
minCell (i, min@(_, lenThat)) = (,) (succ i) . maybe min choose where<br />
choose this = case lenThis > lenThat of<br />
True -> ((this, i), lenThis)<br />
False -> min<br />
where<br />
-- |Ord alpha => Ord (Maybe alpha)| considers Nothing to be $\bot$,<br />
-- rather than $\top$. We get the latter by flipping the ordering<br />
-- on |alpha| (and swapping |(<)| with |(>)|), hence the |negate|.<br />
lenThis = case length this of<br />
1 -> Nothing<br />
n -> Just (negate n) -- zero slips through!<br />
<br />
collapseCell :: (Bool, Cell Bool) -> Maybe [Cell Bool]<br />
collapseCell (marked, cell) = case marked of<br />
True -> Nothing<br />
False -> Just (flip pi masks <$> solutions cell) where<br />
masks = Cell <$> tensor (==) iRegion iRegion<br />
--}}}<br />
<br />
--{{{ Software Transactional Memory; forking.<br />
instance Applicative STM where<br />
pure = return<br />
(<*>) = ap<br />
<br />
type TBool = TVar Bool<br />
<br />
#if FORK_OS<br />
fork = forkOS<br />
#else<br />
fork = forkIO<br />
#endif<br />
--}}}<br />
<br />
--{{{ eliminator: mark non-solutions from cells in the same row/col/box.<br />
type Eliminator = TiTi -> STM ()<br />
<br />
-- Make an eliminator, given a cell and its associated row/col/box.<br />
-- Be careful not to mark the solution itself though.<br />
eliminator :: Cell TBool -> Triple (Region (Cell TBool)) -> Eliminator<br />
eliminator solution rcb n = elimRCB ((pi n <$>) <$> rcb) where<br />
elimRCB :: Triple (Region TBool) -> STM ()<br />
elimRCB = traverse_ . traverse_ $ \ tflag -> do<br />
unless (pi n solution == tflag) $ do<br />
flag <- readTVar tflag<br />
when flag (writeTVar tflag False)<br />
--}}}<br />
<br />
--{{{ worker: check each cell for changes in constraints.<br />
worker :: TBool -> Cell TBool -> Eliminator -> STM ()<br />
worker tsolved tcell elim = do<br />
cell <- traverse readTVar tcell<br />
case solutions cell of<br />
[] -> do -- Bad End.<br />
#if OPTION(FORK_WORKERS)<br />
return ()<br />
#else<br />
retry<br />
#endif<br />
[n] -> do elim n; writeTVar tsolved True<br />
_ -> retry<br />
--}}}<br />
<br />
--{{{ launchMissiles, waitMissiles: constraint propagation.<br />
type State alpha = (Grid alpha, Cube alpha)<br />
<br />
#if OPTION(FORK_WORKERS)<br />
waitMissiles :: State TBool -> STM ()<br />
waitMissiles (tsolved, Cube tgrid) = do<br />
let boo tmarked tcell = do<br />
marked <- readTVar tmarked<br />
cell <- solutions <$> traverse readTVar tcell<br />
case cell of<br />
[] -> return False<br />
[_] -> do unless marked retry; return True<br />
_ -> return True<br />
let elseThen e t b = case b of<br />
True -> t<br />
False -> e<br />
foldrM (elseThen (return False)) True (boo <$> tsolved <*> tgrid :: Grid (STM Bool))<br />
return ()<br />
#endif<br />
<br />
launchMissiles :: State Bool -> IO (State Bool)<br />
launchMissiles (solved, cube) = do<br />
tsolved <- atomically $ traverse newTVar solved<br />
tcube@(Cube tgrid) <- atomically $ traverse newTVar cube<br />
<br />
let tcubes = decompose tcube :: Triple (Cube TBool)<br />
let elims = {-# SCC "elims" #-} eliminator <$> tgrid <*> (select tcubes <$> iGrid) :: Grid Eliminator<br />
<br />
let workers = {-# SCC "workers" #-} worker <$> tsolved <*> tgrid <*> elims :: Grid (STM ())<br />
#if OPTION(FORK_WORKERS)<br />
let whip done w = {-# SCC "whip" #-} case done of<br />
True -> return Nothing<br />
False -> Just <$> fork (atomically w)<br />
<br />
tids <- {-# SCC "whipping" #-} sequenceA (whip <$> solved <*> workers)<br />
<br />
-- Wait for all the missiles to hit their target. Or any to malfunction.<br />
atomically (waitMissiles (tsolved, tcube))<br />
traverse_ (traverse_ killThread) tids<br />
#else<br />
tdone <- atomically (newTVar False)<br />
let whip rest (tdone, w) = do<br />
done <- readTVar tdone<br />
case done of<br />
True -> rest<br />
False -> w `orElse` rest<br />
let loop = do<br />
atomically (foldl whip (writeTVar tdone True) ((,) <$> tsolved <*> workers))<br />
done <- atomically (readTVar tdone)<br />
unless done loop<br />
loop<br />
#endif<br />
<br />
cube' <- atomically (traverse readTVar tcube)<br />
solved' <- atomically (traverse readTVar tsolved)<br />
return (solved', cube')<br />
--}}}<br />
<br />
--{{{ mad: make guesses.<br />
mad :: State Bool -> IO Bool<br />
mad boo = do<br />
(solved', cube') <- launchMissiles boo<br />
case fmap Cube <$> collapse ((,) <$> solved' <*> unCube cube') of<br />
Nothing -> do<br />
print cube'<br />
return True<br />
Just next -> case next of<br />
[] -> return False -- Bad End.<br />
_ -> do<br />
#if OPTION(FORK_GUESSES)<br />
children <- for next $ \ c -> do<br />
sem <- atomically (newTVar Nothing)<br />
tid <- fork $ mad (solved', c) >>= atomically . writeTVar sem . Just<br />
return (sem, tid)<br />
let wait = do<br />
done <- atomically (traverse (readTVar . fst) children)<br />
# if OPTION(EXHAUSTIVE)<br />
case any isNothing done of<br />
True -> wait<br />
False -> return (any (fromMaybe False) done)<br />
# else<br />
case any (fromMaybe False) done of<br />
True -> do<br />
traverse_ (killThread . snd) children<br />
return True<br />
False -> case any isNothing done of<br />
True -> wait<br />
False -> return False<br />
# endif<br />
wait<br />
#else<br />
# if OPTION(EXHAUSTIVE)<br />
traverse_ (mad . (,) solved') next<br />
return True -- don't care<br />
# else<br />
let cow done c = case done of<br />
True -> return True<br />
False -> mad (solved', c)<br />
foldlM cow False next<br />
# endif<br />
#endif<br />
--}}}<br />
<br />
--{{{ go, main: solver entry point.<br />
go :: Cube Bool -> IO Bool<br />
go = mad . (,) (pure False)<br />
<br />
main :: IO ()<br />
main = do<br />
go . read =<< getContents<br />
return ()<br />
--}}}<br />
<br />
--{{{ easy, gentle, diabolical, unsolvable, minimal :: Cube Bool<br />
easy, gentle, diabolical, unsolvable, minimal :: Cube Bool<br />
<br />
easy = read "\<br />
2....1.38\<br />
........5\<br />
.7...6...\<br />
.......13\<br />
.981..257\<br />
31....8..\<br />
9..8...2.\<br />
.5..69784\<br />
4..25...."<br />
<br />
gentle = read "\<br />
.1.42...5\<br />
..2.71.39\<br />
.......4.\<br />
2.71....6\<br />
....4....\<br />
6....74.3\<br />
.7.......\<br />
12.73.5..\<br />
3...82.7."<br />
<br />
diabolical = read "\<br />
.9.7..86.\<br />
.31..5.2.\<br />
8.6......\<br />
..7.5...6\<br />
...3.7...\<br />
5...1.7..\<br />
......1.9\<br />
.2.6..35.\<br />
.54..8.7."<br />
<br />
unsolvable = read "\<br />
1..9.7..3\<br />
.8.....7.\<br />
..9...6..\<br />
..72.94..\<br />
41.....95\<br />
..85.43..\<br />
..3...7..\<br />
.5.....4.\<br />
2..8.6..9"<br />
<br />
minimal = read "\<br />
.98......\<br />
....7....\<br />
....15...\<br />
1........\<br />
...2....9\<br />
...9.6.82\<br />
.......3.\<br />
5.1......\<br />
...4...2."<br />
--}}}<br />
</haskell><br />
<br />
== Makefile ==<br />
<br />
<pre><br />
TARGETS := sudoku<br />
HSFLAGS := $(DEFINES) -O3<br />
<br />
.PHONY: all alternatives<br />
all: $(TARGETS)<br />
<br />
%: %.hs<br />
ghc $(HSFLAGS) -threaded -o $@ --make $<<br />
<br />
%: %.lhs<br />
ghc $(HSFLAGS) -threaded -o $@ --make $<<br />
<br />
profile-%: %.hs<br />
ghc $(HSFLAGS) -prof -auto-all -o $@ --make $<<br />
<br />
profile-%.prof: profile-%<br />
./$< +RTS -p -i0.02 -RTS<br />
<br />
.PHONY: clean<br />
clean:<br />
rm -f $(TARGETS:=.o) $(TARGETS:=.hi) $(TARGETS)<br />
</pre><br />
<br />
== build-alternatives ==<br />
<br />
<pre><br />
#! /bin/bash<br />
<br />
NAME=sudoku<br />
<br />
for ((i = 0; i < 16; i++)) ; do<br />
EXT=""<br />
[ "$(($i & 1))" = "0" ] || EXT="$EXT-exhaustive"<br />
[ "$(($i & 2))" = "0" ] || EXT="$EXT-fork_workers"<br />
[ "$(($i & 4))" = "0" ] || EXT="$EXT-fork_guesses"<br />
[ "$(($i & 8))" = "0" ] || EXT="$EXT-forkOS"<br />
EXT="${EXT:--boring}"<br />
make clean<br />
make DEFINES="-DOPTIONS=$i" "$NAME"<br />
mv "$NAME" "$NAME$EXT"<br />
done<br />
</pre></div>Liyanghttps://wiki.haskell.org/index.php?title=AngloHaskell/2007&diff=5111AngloHaskell/20072006-08-02T00:08:41Z<p>Liyang: Moved note about nametags.</p>
<hr />
<div>On June the 9th, Microsoft Research sent out an advert for a job. This job involves maintaining the Glorious Glasgow Compiler, and created quite a stir in the Haskell community: It's the job we've all been hoping for! After a while the CV's were sent, and Microsoft Research has now invited several Haskellers for an interview at Cambridge, UK.<br />
<br />
This event has been recognized as a great opportunity for a Haskell gathering and we hereby invite all Haskellers (and other cool people) to a fun couple of days in Cambridge.<br />
<br />
Date:<br />
* Friday the 4th and Saturday the 5th of August.<br />
<br />
Contact person:<br />
Shae Erisson - +46 70 3915045<br />
<br />
Local contact:<br />
Ganesh Sittampalam - 07968 253467 (+44 7968 253467 from a non-UK phone)<br />
<br />
If you're coming into Cambridge by train and want to join in the fun, call Shae at the number above.<br />
<br />
== Directions to MSR ==<br />
<br />
MSR has [http://research.microsoft.com/aboutmsr/visitmsr/cambridge/directions.aspx some directions], which can be best summarised as ‘get a taxi’. Here is (hopefully) a [http://earth.google.com/ Google Earth] [[Media:Microsoft_Research,_Cambridge.kmz|location]] of MSR, as well as a [http://maps.google.com/maps?q=CB3+0FB&ll=52.211499,0.117073&spn=0.02677,0.086517 Google Maps link]. (J J Thomson Avenue is immediately west of Clerk Maxwell Road.)<br />
<br />
If you do take a taxi and the driver doesn't know where it is, tell him or her to drive down Madingley Road until you reach the West Cambridge site, J J Thomson Avenue. The Computer Laboratory (next door) has [http://www.cl.cam.ac.uk/UoCCL/contacts/#gettinghere marginally better instructions].<br />
<br />
The fastest way to MSR (on foot and public transport) from the station is to [http://maps.google.com/maps?saddr=CB1+2JW&daddr=Trumpington+Road,+Cambridge cut through to Trumpington Road via Bateman Street] (don't follow the driving directions!), and take the Citi 4 or Uni 4. There's a bus stop just across the road from Bateman Street.<br />
<br />
To get to the city centre by bus, take the Citi 1 or Citi 3. Do ask to make sure they're going in the right direction though! There are also a number of clearly marked shuttle busses between the centre and station running during the day every 10 minutes or so.<br />
<br />
To walk to the centre (20 minutes not carrying luggage), go straight down the road facing you when you come out of the station, bear right when the road ends at some traffic lights / a WW1 memorial / the botanic gardens, and keep walking straight (Hills Road / Regent St / St Andrews St) for quite a while until you reach a pedestrianised bit, at which point you are in the centre.<br />
<br />
From the city centre to MSR, you can catch the number 77 Madingley Road Park and Ride which goes from bus stop M on Emma St. (Or find your way to Pembroke or Silver Street, and catch the Citi 4 / Uni 4 from there.)<br />
<br />
== Attendees ==<br />
<br />
All attendees, '''please bring or make a nametag''' that identifies you by your real name and/or IRC name.<br />
<br />
=== Definite ===<br />
<br />
* Simon Peyton-Jones and Simon Marlow (Friday only)<br />
* Lemmih (will arrive the 2nd and leave the 6th)<br />
* PhilippaCowderoy (barring emergencies, can hang around)<br />
* [http://www.scannedinavian.com/hope/ ShaeErisson] [B0EF20CC] (shapr) (will arrive the 2nd and leave the 5th)<br />
* Peter Nuttall (am around from the 26 July onwards, baring the 3rd when I'm in ipswitch)<br />
* genneth (am in Cambridge anyway)<br />
* GaneshSittampalam (Heffalump) (for at least some of the time)<br />
* Neil Mitchell - ndm (will arrive 4pm on the 5th)<br />
* Liyang HU<br />
* Robin Green (greenrd)<br />
* Dana N Xu<br />
* Duncan Coutts (dcoutts)<br />
* Edwin Brady (From about 2:30pm on Friday)<br />
<br />
=== Possible ===<br />
<br />
* xerox (depends on the date)<br />
* GK (depends on the date; it'd be great to meet some of the wonderful Haskell community folks)<br />
* vincenz (depends on the date, preferably a day or two, partially weekend)<br />
** Would need details in advance to reserve ticket for EUROSTAR<br />
* Paul Johnson (paj) (paul at cogito dot org dot uk)<br />
** Almost certain. Looking for crash space or pointer to nearby cheap hotel<br />
* eivuokko<br />
* Alexander Jacobson<br />
<br />
== Lodging ==<br />
<br />
* Are there places we can crash, rooms we can share?<br />
** Bring your own sleeping bag, if using one of the crash spaces below!<br />
** dcoutts has offered floor space to a few, however, there may not be any left.<br />
** psnl (Pete Nuttall) has 14 sq metres of floor crash space in a college.<br />
** Ganesh Sittampalam has several places worth of crash space left. Ask me on IRC (Heffalump)<br />
<br />
== Programme ==<br />
<br />
Planning is taking place on IRC: #anglohaskell on irc.freenode.net<br />
<br />
=== Friday Talks ===<br />
<br />
* Stop Press! We will have a projector ''and'' a whiteboard!<br />
* Lemmih could give a short talk on breakpoints in GHC<br />
* Liyang is prepared to wave his arms in the air while not making much sense about ''idiomatic programming'' (and '''not just''' the ''applicative idioms'' you've witnessed previously...) with an additional helping of ''memoisation''.<br />
* Paul Johnson will give a talk on '''discrete event simulation'''.<br />
* Ganesh Sittampalam might talk about recent '''Darcs''' work involving patch theory<br />
<br />
==== Formal verification and dependent types ====<br />
<br />
* Dana N Xu will talk about '''Extended Static Checking''' for Haskell (ESC/Haskell)<br />
* Edwin Brady might "introduce '''dependent types''' then talk about [his] pet '''[http://www.dcs.st-and.ac.uk/~eb/Ivor/ theorem prover]'''"<br />
* Robin Green is preparing a talk about simulating '''dependent types''' in Haskell, and using them for "categorical programming" (programming based on '''category theory''') and proving properties of code<br />
<br />
=== Rest of Friday ===<br />
<br />
* Is there anything other than talks for Friday while we're still at MSR? If not, are there enough talks to warrant a morning start?<br />
* Where's lunch?<br />
* We're expecting to hit a pub or two after MSR before we all find our crashspace?<br />
* No doubt there're possibilities while at a pub other than beer and chat?<br />
* There's been mention of Go?<br />
* And other games that take less time to learn to play?<br />
* Do we have enough people who think they know the rules to get the Chairman's Game going? Can we avoid it turning turing complete?<br />
<br />
=== Saturday Stuff ===<br />
<br />
* some kind of '''coding / pair programming'''? Maybe on Saturday when we're not going to be at MSR (we haven't figured out where we will be yet)<br />
* We don't know what we're doing on Saturday yet!<br />
* Perhaps colonise a '''café''' in the morning 'til everyone's reasonably awake, then head for a '''pub''' or similar with '''wi-fi''' (perhaps the connection is less important?) for coding and/or more social geeking as per everyone's taste?<br />
<br />
== Wireless internet ==<br />
<br />
MSR is willling to provide wireless internet to everyone who gives their name and email address.<br />
<br />
* David Himmelstrup, lemmih AT gmail.com<br />
* Ian Lynagh, igloo AT earth.li<br />
* Shae Erisson, shae AT ScannedInAvian.com<br />
* Edwin Brady, eb AT dcs.st-and.ac.uk<br />
* Liyang HU, msrc AT liyang.hu<br />
* Ganesh Sittampalam, ganesh AT earth.li<br />
<br />
[[Category:Events]]</div>Liyanghttps://wiki.haskell.org/index.php?title=AngloHaskell/2007&diff=5110AngloHaskell/20072006-08-01T19:29:31Z<p>Liyang: /* Wireless internet */</p>
<hr />
<div>On June the 9th, Microsoft Research sent out an advert for a job. This job involves maintaining the Glorious Glasgow Compiler, and created quite a stir in the Haskell community: It's the job we've all been hoping for! After a while the CV's were sent, and Microsoft Research has now invited several Haskellers for an interview at Cambridge, UK.<br />
<br />
This event has been recognized as a great opportunity for a Haskell gathering and we hereby invite all Haskellers (and other cool people) to a fun couple of days in Cambridge.<br />
<br />
Date:<br />
* Friday the 4th and Saturday the 5th of August.<br />
<br />
Contact person:<br />
Shae Erisson - +46 70 3915045<br />
<br />
Local contact:<br />
Ganesh Sittampalam - 07968 253467 (+44 7968 253467 from a non-UK phone)<br />
<br />
If you're coming into Cambridge by train and want to join in the fun, call Shae at the number above.<br />
<br />
== Directions to MSR ==<br />
<br />
MSR has [http://research.microsoft.com/aboutmsr/visitmsr/cambridge/directions.aspx some directions], which can be best summarised as ‘get a taxi’. Here is (hopefully) a [http://earth.google.com/ Google Earth] [[Media:Microsoft_Research,_Cambridge.kmz|location]] of MSR, as well as a [http://maps.google.com/maps?q=CB3+0FB&ll=52.211499,0.117073&spn=0.02677,0.086517 Google Maps link]. (J J Thomson Avenue is immediately west of Clerk Maxwell Road.)<br />
<br />
If you do take a taxi and the driver doesn't know where it is, tell him or her to drive down Madingley Road until you reach the West Cambridge site, J J Thomson Avenue. The Computer Laboratory (next door) has [http://www.cl.cam.ac.uk/UoCCL/contacts/#gettinghere marginally better instructions].<br />
<br />
The fastest way to MSR (on foot and public transport) from the station is to [http://maps.google.com/maps?saddr=CB1+2JW&daddr=Trumpington+Road,+Cambridge cut through to Trumpington Road via Bateman Street] (don't follow the driving directions!), and take the Citi 4 or Uni 4. There's a bus stop just across the road from Bateman Street.<br />
<br />
To get to the city centre by bus, take the Citi 1 or Citi 3. Do ask to make sure they're going in the right direction though! There are also a number of clearly marked shuttle busses between the centre and station running during the day every 10 minutes or so.<br />
<br />
To walk to the centre (20 minutes not carrying luggage), go straight down the road facing you when you come out of the station, bear right when the road ends at some traffic lights / a WW1 memorial / the botanic gardens, and keep walking straight (Hills Road / Regent St / St Andrews St) for quite a while until you reach a pedestrianised bit, at which point you are in the centre.<br />
<br />
From the city centre to MSR, you can catch the number 77 Madingley Road Park and Ride which goes from bus stop M on Emma St. (Or find your way to Pembroke or Silver Street, and catch the Citi 4 / Uni 4 from there.)<br />
<br />
== Attendees ==<br />
<br />
=== Definite ===<br />
<br />
* Simon Peyton-Jones and Simon Marlow (Friday only)<br />
* Lemmih (will arrive the 2nd and leave the 6th)<br />
* PhilippaCowderoy (barring emergencies, can hang around)<br />
* [http://www.scannedinavian.com/hope/ ShaeErisson] [B0EF20CC] (shapr) (will arrive the 2nd and leave the 5th)<br />
* Peter Nuttall (am around from the 26 July onwards, baring the 3rd when I'm in ipswitch)<br />
* genneth (am in Cambridge anyway)<br />
* GaneshSittampalam (Heffalump) (for at least some of the time)<br />
* Neil Mitchell - ndm (will arrive 4pm on the 5th)<br />
* Liyang HU<br />
* Robin Green (greenrd)<br />
* Dana N Xu<br />
* Duncan Coutts (dcoutts)<br />
* Edwin Brady (From about 2:30pm on Friday)<br />
<br />
=== Possible ===<br />
<br />
* xerox (depends on the date)<br />
* GK (depends on the date; it'd be great to meet some of the wonderful Haskell community folks)<br />
* vincenz (depends on the date, preferably a day or two, partially weekend)<br />
** Would need details in advance to reserve ticket for EUROSTAR<br />
* Paul Johnson (paj) (paul at cogito dot org dot uk)<br />
** Almost certain. Looking for crash space or pointer to nearby cheap hotel<br />
* eivuokko<br />
* Alexander Jacobson<br />
<br />
== Lodging ==<br />
<br />
* Are there places we can crash, rooms we can share?<br />
** Bring your own sleeping bag, if using one of the crash spaces below!<br />
** dcoutts has offered floor space to a few, however, there may not be any left.<br />
** psnl (Pete Nuttall) has 14 sq metres of floor crash space in a college.<br />
** Ganesh Sittampalam has several places worth of crash space left. Ask me on IRC (Heffalump)<br />
<br />
== Programme ==<br />
<br />
Planning is taking place on IRC: #anglohaskell on irc.freenode.net<br />
<br />
=== Friday Talks ===<br />
<br />
* Stop Press! We will have a projector ''and'' a whiteboard!<br />
* Lemmih could give a short talk on breakpoints in GHC<br />
* Liyang is prepared to wave his arms in the air while not making much sense about ''idiomatic programming'' (and '''not just''' the ''applicative idioms'' you've witnessed previously...) with an additional helping of ''memoisation''.<br />
* Paul Johnson will give a talk on '''discrete event simulation'''.<br />
* Ganesh Sittampalam might talk about recent '''Darcs''' work involving patch theory<br />
<br />
==== Formal verification and dependent types ====<br />
<br />
* Dana N Xu will talk about '''Extended Static Checking''' for Haskell (ESC/Haskell)<br />
* Edwin Brady might "introduce '''dependent types''' then talk about [his] pet '''[http://www.dcs.st-and.ac.uk/~eb/Ivor/ theorem prover]'''"<br />
* Robin Green is preparing a talk about simulating '''dependent types''' in Haskell, and using them for "categorical programming" (programming based on '''category theory''') and proving properties of code<br />
<br />
=== Rest of Friday ===<br />
<br />
* Is there anything other than talks for Friday while we're still at MSR? If not, are there enough talks to warrant a morning start?<br />
* Where's lunch?<br />
* We're expecting to hit a pub or two after MSR before we all find our crashspace?<br />
* No doubt there're possibilities while at a pub other than beer and chat?<br />
* There's been mention of Go?<br />
* And other games that take less time to learn to play?<br />
* Do we have enough people who think they know the rules to get the Chairman's Game going? Can we avoid it turning turing complete?<br />
<br />
=== Saturday Stuff ===<br />
<br />
* some kind of '''coding / pair programming'''? Maybe on Saturday when we're not going to be at MSR (we haven't figured out where we will be yet)<br />
* We don't know what we're doing on Saturday yet!<br />
* Perhaps colonise a '''café''' in the morning 'til everyone's reasonably awake, then head for a '''pub''' or similar with '''wi-fi''' (perhaps the connection is less important?) for coding and/or more social geeking as per everyone's taste?<br />
<br />
<br />
== Miscellaneous ==<br />
<br />
* Please could everyone bring or make a nametag that identifies you by your real name and/or IRC name.<br />
<br />
== Wireless internet ==<br />
<br />
MSR is willling to provide wireless internet to everyone who gives their name and email address.<br />
<br />
* David Himmelstrup, lemmih AT gmail.com<br />
* Ian Lynagh, igloo AT earth.li<br />
* Shae Erisson, shae AT ScannedInAvian.com<br />
* Edwin Brady, eb AT dcs.st-and.ac.uk<br />
* Liyang HU, msrc AT liyang.hu<br />
* Ganesh Sittampalam, ganesh AT earth.li<br />
<br />
[[Category:Events]]</div>Liyanghttps://wiki.haskell.org/index.php?title=AngloHaskell/2007&diff=5100AngloHaskell/20072006-08-01T13:20:15Z<p>Liyang: </p>
<hr />
<div>On June the 9th, Microsoft Research sent out an advert for a job. This job involves maintaining the Glorious Glasgow Compiler, and created quite a stir in the Haskell community: It's the job we've all been hoping for! After a while the CV's were sent, and Microsoft Research has now invited several Haskellers for an interview at Cambridge, UK.<br />
<br />
This event has been recognized as a great opportunity for a Haskell gathering and we hereby invite all Haskellers (and other cool people) to a fun couple of days in Cambridge.<br />
<br />
Date:<br />
* Friday the 4th and Saturday the 5th of August.<br />
<br />
Contact person:<br />
Shae Erisson - +46 70 3915045<br />
<br />
Local contact:<br />
Ganesh Sittampalam - 07968 253467 (+44 7968 253467 from a non-UK phone)<br />
<br />
If you're coming into Cambridge by train and want to join in the fun, call Shae at the number above.<br />
<br />
== Directions to MSR ==<br />
<br />
MSR has [http://research.microsoft.com/aboutmsr/visitmsr/cambridge/directions.aspx some directions], which can be best summarised as ‘get a taxi’. Here is (hopefully) a [http://earth.google.com/ Google Earth] [[Media:Microsoft_Research,_Cambridge.kmz|location]] of MSR, as well as a [http://maps.google.com/maps?q=CB3+0FB&ll=52.211499,0.117073&spn=0.02677,0.086517 Google Maps link]. (J J Thomson Avenue is immediately west of Clerk Maxwell Road.)<br />
<br />
If you do take a taxi and the driver doesn't know where it is, tell him or her to drive down Madingley Road until you reach the West Cambridge site, J J Thomson Avenue. The Computer Laboratory (next door) has [http://www.cl.cam.ac.uk/UoCCL/contacts/#gettinghere marginally better instructions].<br />
<br />
The fastest way to MSR (on foot and public transport) from the station is to [http://maps.google.com/maps?saddr=CB1+2JW&daddr=Trumpington+Road,+Cambridge cut through to Trumpington Road via Bateman Street] (don't follow the driving directions!), and take the Citi 4 or Uni 4. There's a bus stop just across the road from Bateman Street.<br />
<br />
To get to the city centre by bus, take the Citi 1 or Citi 3. Do ask to make sure they're going in the right direction though! There are also a number of clearly marked shuttle busses between the centre and station running during the day every 10 minutes or so.<br />
<br />
To walk to the centre (20 minutes not carrying luggage), go straight down the road facing you when you come out of the station, bear right when the road ends at some traffic lights / a WW1 memorial / the botanic gardens, and keep walking straight (Hills Road / Regent St / St Andrews St) for quite a while until you reach a pedestrianised bit, at which point you are in the centre.<br />
<br />
From the city centre to MSR, you can catch the number 77 Madingley Road Park and Ride which goes from bus stop M on Emma St. (Or find your way to Pembroke or Silver Street, and catch the Citi 4 / Uni 4 from there.)<br />
<br />
== Attendees ==<br />
<br />
=== Definite ===<br />
<br />
* Simon Peyton-Jones and Simon Marlow (Friday only)<br />
* Lemmih (will arrive the 2nd and leave the 6th)<br />
* PhilippaCowderoy (barring emergencies, can hang around)<br />
* [http://www.scannedinavian.com/hope/ ShaeErisson] (shapr) (will arrive the 2nd and leave the 5th)<br />
* Peter Nuttall (am around from the 26 July onwards, baring the 3rd when I'm in ipswitch)<br />
* genneth (am in Cambridge anyway)<br />
* GaneshSittampalam (Heffalump) (for at least some of the time)<br />
* Neil Mitchell - ndm (will arrive 4pm on the 5th)<br />
* Liyang HU<br />
* Robin Green (greenrd)<br />
* Dana N Xu<br />
* Duncan Coutts (dcoutts)<br />
* Edwin Brady (From about 2:30pm on Friday)<br />
<br />
=== Possible ===<br />
<br />
* xerox (depends on the date)<br />
* GK (depends on the date; it'd be great to meet some of the wonderful Haskell community folks)<br />
* vincenz (depends on the date, preferably a day or two, partially weekend)<br />
** Would need details in advance to reserve ticket for EUROSTAR<br />
* Paul Johnson (paj) (paul at cogito dot org dot uk)<br />
** Almost certain. Looking for crash space or pointer to nearby cheap hotel<br />
<br />
== Lodging ==<br />
<br />
* Are there places we can crash, rooms we can share?<br />
** Bring your own sleeping bag, if using one of the crash spaces below!<br />
** dcoutts has offered floor space to a few, however, there may not be any left.<br />
** psnl (Pete Nuttall) has 14 sq metres of floor crash space in a college.<br />
<br />
== Programme ==<br />
<br />
Planning is taking place on IRC: #anglohaskell on irc.freenode.net<br />
<br />
=== Friday Talks ===<br />
<br />
* Lemmih could give a short talk on breakpoints in GHC<br />
* Liyang is prepared to wave his arms in the air while not making much sense about ''idiomatic programming'' (and '''not just''' the ''applicative idioms'' you've witnessed previously...) with an additional helping of ''memoisation''.<br />
* Paul Johnson will give a talk on '''discrete event simulation'''.<br />
* Ganesh Sittampalam might talk about recent '''Darcs''' work involving patch theory<br />
<br />
==== Formal verification and dependent types ====<br />
<br />
* Dana N Xu will talk about '''Extended Static Checking''' for Haskell (ESC/Haskell)<br />
* edwinb might "introduce '''dependent types''' then talk about [his] pet '''[http://www.dcs.st-and.ac.uk/~eb/Ivor/ theorem prover]'''"<br />
* Robin Green is preparing a talk about simulating '''dependent types''' in Haskell, and using them for "categorical programming" (programming based on '''category theory''') and proving properties of code<br />
<br />
=== Rest of Friday ===<br />
<br />
* Is there anything other than talks for Friday while we're still at MSR? If not, are there enough talks to warrant a morning start?<br />
* Where's lunch?<br />
* We're expecting to hit a pub or two after MSR before we all find our crashspace?<br />
* No doubt there're possibilities while at a pub other than beer and chat?<br />
* There's been mention of Go?<br />
* And other games that take less time to learn to play?<br />
* Do we have enough people who think they know the rules to get the Chairman's Game going? Can we avoid it turning turing complete?<br />
<br />
=== Saturday Stuff ===<br />
<br />
* some kind of '''coding / pair programming'''? Maybe on Saturday when we're not going to be at MSR (we haven't figured out where we will be yet)<br />
* We don't know what we're doing on Saturday yet!<br />
* Perhaps colonise a '''café''' in the morning 'til everyone's reasonably awake, then head for a '''pub''' or similar with '''wi-fi''' (perhaps the connection is less important?) for coding and/or more social geeking as per everyone's taste?<br />
<br />
<br />
== Miscellaneous ==<br />
<br />
* Please could everyone bring or make a nametag that identifies you by your real name and/or IRC name.<br />
<br />
== Wireless internet ==<br />
<br />
MSR is willling to provide wireless internet to everyone who gives their name and email address.<br />
<br />
* David Himmelstrup, lemmih AT gmail.com<br />
* Ian Lynagh, igloo AT earth.li<br />
* Shae Erisson, shae AT ScannedInAvian.com<br />
* Edwin Brady, eb AT dcs.st-and.ac.uk<br />
* Liyang HU, msrc @ liyang.hu<br />
<br />
[[Category:Events]]</div>Liyanghttps://wiki.haskell.org/index.php?title=AngloHaskell/2007&diff=5075AngloHaskell/20072006-07-30T18:55:21Z<p>Liyang: Directions and formatting</p>
<hr />
<div>On June the 9th, Microsoft Research sent out an advert for a job. This job involves maintaining the Glorious Glasgow Compiler, and created quite a stir in the Haskell community: It's the job we've all been hoping for! After a while the CV's were sent, and Microsoft Research has now invited several Haskellers for an interview at Cambridge, UK.<br />
<br />
This event has been recognized as a great opportunity for a Haskell gathering and we hereby invite all Haskellers (and other cool people) to a fun couple of days in Cambridge.<br />
<br />
Date:<br />
* Friday the 4th and Saturday the 5th of August.<br />
<br />
Contact person:<br />
Shae Erisson - +46 70 3915045<br />
<br />
Local contact:<br />
Ganesh Sittampalam - 07968 253467 (+44 7968 253467 from a non-UK phone)<br />
<br />
If you're coming into Cambridge by train and want to join in the fun, call Shae at the number above.<br />
<br />
== Directions to MSR ==<br />
<br />
MSR has [http://research.microsoft.com/aboutmsr/visitmsr/cambridge/directions.aspx some directions], which can be best summarised as ‘get a taxi’. Here is (hopefully) a [http://earth.google.com/ Google Earth] [[Media:Microsoft_Research,_Cambridge.kmz|location]] of MSR, as well as a [http://maps.google.com/maps?q=CB3+0FB&ll=52.211499,0.117073&spn=0.02677,0.086517 Google Maps link]. (J J Thomson Avenue is immediately west of Clerk Maxwell Road.)<br />
<br />
If you do take a taxi and the driver doesn't know where it is, tell him or her to drive down Madingley Road until you reach the West Cambridge site, J J Thomson Avenue. The Computer Laboratory (next door) has [http://www.cl.cam.ac.uk/UoCCL/contacts/#gettinghere marginally better instructions].<br />
<br />
The fastest way to MSR (on foot and public transport) from the station is to [http://maps.google.com/maps?saddr=CB1+2JW&daddr=Trumpington+Road,+Cambridge cut through to Trumpington Road via Bateman Street] (don't follow the driving directions!), and take the Citi 4 or Uni 4. There's a bus stop just across the road from Bateman Street.<br />
<br />
To get to the city centre by bus, take the Citi 1 or Citi 3. Do ask to make sure they're going in the right direction though! There are also a number of clearly marked shuttle busses between the centre and station running during the day every 10 minutes or so.<br />
<br />
To walk to the centre (20 minutes not carrying luggage), go straight down the road facing you when you come out of the station, bear right when the road ends at some traffic lights / a WW1 memorial / the botanic gardens, and keep walking straight (Hills Road / Regent St / St Andrews St) for quite a while until you reach a pedestrianised bit, at which point you are in the centre.<br />
<br />
From the city centre to MSR, you can catch the number 77 Madingley Road Park and Ride which goes from bus stop M on Emma St. (Or find your way to Pembroke or Silver Street, and catch the Citi 4 / Uni 4 from there.)<br />
<br />
== Attendees ==<br />
<br />
=== Definite ===<br />
<br />
* Simon Peyton-Jones and Simon Marlow (Friday only)<br />
* Lemmih (will arrive the 2nd and leave the 6th)<br />
* PhilippaCowderoy (barring emergencies, can hang around)<br />
* ShaeErisson (can stay for a couple of days)<br />
* Peter Nuttall (am around from the 26 July onwards, baring the 3rd when I'm in ipswitch)<br />
* genneth (am in Cambridge anyway)<br />
* GaneshSittampalam (Heffalump) (for at least some of the time)<br />
* Neil Mitchell - ndm (can come for the 5th, if I can have some floor space)<br />
* Liyang HU<br />
* Robin Green (greenrd)<br />
<br />
=== Possible ===<br />
<br />
* dcoutts (depends on the date)<br />
* xerox (depends on the date)<br />
* GK (depends on the date; it'd be great to meet some of the wonderful Haskell community folks)<br />
* EdwinBrady (depends on the date; would probably stay a couple of days)<br />
* vincenz (depends on the date, preferably a day or two, partially weekend)<br />
** Would need details in advance to reserve ticket for EUROSTAR<br />
* Paul Johnson (paj) (paul at cogito dot org dot uk)<br />
** Almost certain. Looking for crash space or pointer to nearby cheap hotel<br />
<br />
== Lodging ==<br />
<br />
* Are there places we can crash, rooms we can share?<br />
** Bring your own sleeping bag, if using one of the crash spaces below!<br />
** dcoutts has offered floor space to a few, however, there may not be any left.<br />
** I (psnl) have 14 sq metres of floor crash space in a college.<br />
<br />
== Programme ==<br />
<br />
Planning is taking place on IRC: #anglohaskell on irc.freenode.net<br />
<br />
=== Friday Talks ===<br />
<br />
* edwinb might "introduce '''dependent types''' then talk about [his] pet '''[http://www.dcs.st-and.ac.uk/~eb/Ivor/ theorem prover]'''"<br />
* greenrd is preparing a talk about simulating '''dependent types''' in Haskell, and using them for "categorical programming" (programming based on '''category theory''') and proving properties of code<br />
* Lemmih could give a short talk on breakpoints in GHC<br />
* Liyang is prepared to wave his arms in the air while not making much sense about ''idiomatic programming'' (and '''not just''' the ''applicative idioms'' you've witnessed previously...) with an additional helping of ''memoisation''.<br />
* Paul Johnson may give a talk (details TBC)<br />
* Ganesh Sittampalam might talk about recent '''Darcs''' work involving patch theory<br />
<br />
=== Rest of Friday ===<br />
<br />
* Is there anything other than talks for Friday while we're still at MSR? If not, are there enough talks to warrant a morning start?<br />
* We're expecting to hit a pub or two after MSR before we all find our crashspace?<br />
* No doubt there're possibilities while at a pub other than beer and chat?<br />
* There's been mention of Go?<br />
* And other games that take less time to learn to play?<br />
* Do we have enough people who think they know the rules to get the Chairman's Game going? Can we avoid it turning turing complete?<br />
<br />
=== Saturday Stuff ===<br />
<br />
* some kind of '''coding / pair programming'''? Maybe on Saturday when we're not going to be at MSR (we haven't figured out where we will be yet)<br />
* We don't know what we're doing on Saturday yet!<br />
* Perhaps colonise a '''café''' in the morning 'til everyone's reasonably awake, then head for a '''pub''' or similar with '''wi-fi''' (perhaps the connection is less important?) for coding and/or more social geeking as per everyone's taste?<br />
<br />
<br />
== Miscellaneous ==<br />
<br />
* Please could everyone bring or make a nametag that identifies you by your real name and/or IRC name.</div>Liyanghttps://wiki.haskell.org/index.php?title=Sudoku&diff=5032Sudoku2006-07-27T13:35:02Z<p>Liyang: Writing a Sudoku solver incrementally, à la Bird</p>
<hr />
<div>[[Category:Idioms]]<br />
<br />
Here are a few Sudoku solvers coded up in Haskell...<br />
<br />
== Serious, Non-Deterministic Solver ==<br />
<br />
Here is a solver by CaleGibbard [http://www.haskell.org/hawiki/CaleGibbard/BSDLicense]. It possibly looks even more naïve than it actually is. This does a backtracking search, trying possibilities until it finds one which works, and backtracking when it can no longer make a legal move.<br />
<br />
<haskell><br />
import MonadNondet (option)<br />
import Sudoku<br />
import System<br />
import Control.Monad<br />
<br />
forM = flip mapM<br />
<br />
solve = forM [(i,j) | i <- [1..9], j <- [1..9]] $ \(i,j) -> do<br />
v <- valAt (i,j) -- ^ for each board position<br />
when (v == 0) $ do -- if it's empty (we represent that with a 0)<br />
a <- option [1..9] -- pick a number<br />
place (i,j) a -- and try to put it there<br />
<br />
main = do<br />
[f] <- getArgs<br />
xs <- readFile f<br />
putStrLn $ evalSudoku $ do { readSudoku xs; solve; showSudoku }<br />
</haskell><br />
<br />
Now, to the meat of the thing, the monad which makes the above look so nice. We construct a monad which is suitable for maintaining Sudoku grids and trying options nondeterministically. Note that outside of this module, it's impossible to create a state which has an invalid Sudoku grid, since the only way to update the state handles the check to ensure that the move is legal.<br />
<br />
<haskell><br />
{-# OPTIONS_GHC -fglasgow-exts #-}<br />
module Sudoku <br />
(Sudoku,<br />
readSudoku,<br />
runSudoku,<br />
evalSudoku,<br />
execSudoku,<br />
showSudoku,<br />
valAt, rowAt, colAt, boxAt,<br />
place)<br />
where<br />
import Data.Array.Diff<br />
import MonadNondet<br />
import Control.Monad.State<br />
<br />
-- Nondet here is a drop-in replacement for [] (the list monad) which just runs a little faster.<br />
newtype Sudoku a = Sudoku (StateT (DiffUArray (Int,Int) Int) Nondet a)<br />
deriving (Functor, Monad, MonadPlus)<br />
<br />
{- -- That is, we could also use the following, which works exactly the same way.<br />
newtype Sudoku a = Sudoku (StateT (DiffUArray (Int,Int) Int) [] a)<br />
deriving (Functor, Monad, MonadPlus)<br />
-}<br />
<br />
initialSudokuArray = listArray ((1,1),(9,9)) [0,0..]<br />
<br />
runSudoku (Sudoku k) = runNondet (runStateT k initialSudokuArray)<br />
<br />
evalSudoku = fst . runSudoku<br />
execSudoku = snd . runSudoku<br />
<br />
showSudoku = Sudoku $ do<br />
a <- get<br />
return $ unlines [unwords [show (a ! (i,j)) | j <- [1..9]] | i <- [1..9]]<br />
<br />
readSudoku :: String -> Sudoku ()<br />
readSudoku xs = sequence_ $ do<br />
(i,ys) <- zip [1..9] (lines xs)<br />
(j,n) <- zip [1..9] (words ys)<br />
return $ place (i,j) (read n)<br />
<br />
valAt' (i,j) = do<br />
a <- get<br />
return (a ! (i,j))<br />
<br />
rowAt' (i,j) = mapM valAt' [(i, k) | k <- [1..9]]<br />
<br />
colAt' (i,j) = mapM valAt' [(k, j) | k <- [1..9]] <br />
<br />
boxAt' (i,j) = mapM valAt' [(i' + u, j' + v) | u <- [1..3], v <- [1..3]]<br />
where i' = ((i-1) `div` 3) * 3<br />
j' = ((j-1) `div` 3) * 3<br />
<br />
valAt = Sudoku . valAt'<br />
rowAt = Sudoku . rowAt'<br />
colAt = Sudoku . colAt'<br />
boxAt = Sudoku . boxAt'<br />
<br />
-- This is the least trivial part.<br />
-- It just guards to make sure that the move is legal,<br />
-- and updates the array in the state if it is.<br />
place :: (Int,Int) -> Int -> Sudoku ()<br />
place (i,j) n = Sudoku $ do<br />
v <- valAt' (i,j)<br />
when (v == 0 && n /= 0) $ do<br />
rs <- rowAt' (i,j)<br />
cs <- colAt' (i,j)<br />
bs <- boxAt' (i,j)<br />
guard $ not . any (== n) $ rs ++ cs ++ bs<br />
a <- get<br />
put (a // [((i,j),n)])<br />
</haskell><br />
<br />
This is a fast NonDeterminism monad. It's a drop-in replacement for the list monad in this case. It's twice as fast when compiled with optimisations but a little slower without. You can also find it on the wiki at NonDeterminism.<br />
<br />
I've made a few small modifications to this one to hopefully make it more concretely readable.<br />
<br />
<haskell><br />
{-# OPTIONS_GHC -fglasgow-exts #-}<br />
<br />
module MonadNondet where<br />
<br />
import Control.Monad<br />
import Control.Monad.Trans<br />
<br />
import Control.Monad.Identity<br />
<br />
newtype NondetT m a<br />
= NondetT { foldNondetT :: (forall b. (a -> m b -> m b) -> m b -> m b) }<br />
<br />
runNondetT :: (Monad m) => NondetT m a -> m a<br />
runNondetT m = foldNondetT m (\x xs -> return x) (error "No solution found.")<br />
<br />
instance (Functor m) => Functor (NondetT m) where<br />
fmap f (NondetT g) = NondetT (\cons nil -> g (cons . f) nil)<br />
<br />
instance (Monad m) => Monad (NondetT m) where<br />
return a = NondetT (\cons nil -> cons a nil)<br />
m >>= k = NondetT (\cons nil -> foldNondetT m (\x -> foldNondetT (k x) cons) nil)<br />
<br />
instance (Monad m) => MonadPlus (NondetT m) where<br />
mzero = NondetT (\cons nil -> nil)<br />
m1 `mplus` m2 = NondetT (\cons -> foldNondetT m1 cons . foldNondetT m2 cons)<br />
<br />
instance MonadTrans NondetT where<br />
lift m = NondetT (\cons nil -> m >>= \a -> cons a nil)<br />
<br />
newtype Nondet a = Nondet (NondetT Identity a) deriving (Functor, Monad, MonadPlus)<br />
runNondet (Nondet x) = runIdentity (runNondetT x)<br />
<br />
foldNondet :: Nondet a -> (a -> b -> b) -> b -> b<br />
foldNondet (Nondet nd) cons nil =<br />
runIdentity $ foldNondetT nd (\x xs -> return (cons x (runIdentity xs))) (return nil)<br />
<br />
option :: (MonadPlus m) => [a] -> m a<br />
option = msum . map return<br />
</haskell><br />
<br />
<br />
<br />
<br />
== Simple Solver ==<br />
<br />
By AlsonKemp. This solver is probably similar to Cale's but I don't grok the non-deterministic monad...<br />
<br />
Note: this solver is exhaustive and will output all of the solutions, not just the first one. In order to make it non-exchaustive, add a case statement to solve' in order to check "r" and branch on the result.<br />
<br />
<haskell><br />
import System<br />
import Control.Monad<br />
import Data.List<br />
import Data.Array.IO<br />
<br />
type SodokuBoard = IOArray Int Int<br />
<br />
main = do<br />
[f] <- getArgs<br />
a <- newArray (1, 81) 0<br />
readFile f >>= readSodokuBoard a<br />
putStrLn "Original:"<br />
printSodokuBoard a<br />
putStrLn "Solutions:"<br />
solve a (1,1)<br />
<br />
readSodokuBoard a xs = sequence_ $ do (i,ys) <- zip [1..9] (lines xs)<br />
(j,n) <- zip [1..9] (words ys)<br />
return $ writeBoard a (j,i) (read n)<br />
<br />
printSodokuBoard a =<br />
let printLine a y =<br />
mapM (\x -> readBoard a (x,y)) [1..9] >>= mapM_ (putStr . show) in<br />
putStrLn "-----------" >> <br />
mapM_ (\y -> putStr "|" >> printLine a y >> putStrLn "|") [1..9] >> <br />
putStrLn "-----------"<br />
<br />
-- the meat of the program. Checks the current square.<br />
-- If 0, then get the list of nums and try to "solve' "<br />
-- Otherwise, go to the next square.<br />
solve :: SodokuBoard -> (Int, Int) -> IO (Maybe SodokuBoard)<br />
solve a (10,y) = solve a (1,y+1)<br />
solve a (_, 10)= printSodokuBoard a >> return (Just a)<br />
solve a (x,y) = do v <- readBoard a (x,y)<br />
case v of<br />
0 -> availableNums a (x,y) >>= solve' a (x,y)<br />
_ -> solve a (x+1,y)<br />
-- solve' handles the backtacking<br />
where solve' a (x,y) [] = return Nothing<br />
solve' a (x,y) (v:vs) = do writeBoard a (x,y) v -- put a guess onto the board<br />
r <- solve a (x+1,y)<br />
writeBoard a (x,y) 0 -- remove the guess from the board<br />
solve' a (x,y) vs -- recurse over the remainder of the list<br />
<br />
-- get the "taken" numbers from a row, col or box.<br />
getRowNums a y = sequence [readBoard a (x',y) | x' <- [1..9]]<br />
getColNums a x = sequence [readBoard a (x,y') | y' <- [1..9]]<br />
getBoxNums a (x,y) = sequence [readBoard a (x'+u, y'+v) | u <- [0..2], v <- [0..2]] <br />
where x' = (3 * ((x-1) `quot` 3)) + 1<br />
y' = (3 * ((y-1) `quot` 3)) + 1<br />
<br />
-- return the numbers that are available for a particular square<br />
availableNums a (x,y) = do r <- getRowNums a y <br />
c <- getColNums a x<br />
b <- getBoxNums a (x,y)<br />
return $ [0..9] \\ (r `union` c `union` b) <br />
<br />
-- aliases of read and write array that flatten the index<br />
readBoard a (x,y) = readArray a (x+9*(y-1))<br />
writeBoard a (x,y) e = writeArray a (x+9*(y-1)) e<br />
</haskell><br />
<br />
== Complete decision tree ==<br />
<br />
By Henning Thielemann.<br />
<br />
<haskell><br />
module Sudoku where<br />
<br />
{-<br />
This is inspired by John Hughes "Why Functional Programming Matters".<br />
We build a complete decision tree.<br />
That is, all alternatives in a certain depth<br />
have the same number of determined values.<br />
At the bottom of the tree all possible solutions can be found.<br />
Actually the algorithm is very stupid:<br />
In each depth we look for the field with the least admissible choices of numbers<br />
and prune the alternative branches for the other fields.<br />
-}<br />
<br />
import Data.Char (ord, chr)<br />
import Data.Array (Array, range, (!), (//))<br />
import Data.Tree (Tree)<br />
import qualified Data.Tree as Tree<br />
import Data.List (sort, minimumBy)<br />
import Data.Maybe (catMaybes, isNothing, fromMaybe, fromJust)<br />
import qualified Data.Array as Array<br />
<br />
{-<br />
Example:<br />
<br />
ghci -Wall Sudoku.hs<br />
<br />
*Sudoku> mapM putCLn (solutions exampleHawiki0)<br />
-}<br />
<br />
<br />
{- [[ATree]] contains a list of possible alternatives for each position -}<br />
data ATree a = ANode T [[ATree a]]<br />
<br />
type Coord = Int<br />
type Address = (Int,Int,Int,Int)<br />
type Element = Int<br />
<br />
type T = Array Address (Maybe Element)<br />
type Complete = Array Address Element<br />
<br />
fieldBounds :: (Address, Address)<br />
fieldBounds = ((0,0,0,0), (2,2,2,2))<br />
<br />
squareRange :: [(Coord, Coord)]<br />
squareRange = range ((0,0), (2,2))<br />
<br />
alphabet :: [Element]<br />
alphabet = [1..9]<br />
<br />
<br />
<br />
{- * solution -}<br />
<br />
{-<br />
Given two sorted lists,<br />
remove the elements of the first list from the second one.<br />
-}<br />
deleteSorted :: Ord a => [a] -> [a] -> [a]<br />
deleteSorted [] ys = ys<br />
deleteSorted _ [] = []<br />
deleteSorted (x:xs) (y:ys) =<br />
case compare x y of<br />
EQ -> deleteSorted xs ys<br />
LT -> deleteSorted xs (y:ys)<br />
GT -> y : deleteSorted (x:xs) ys<br />
<br />
admissibleNumbers :: [[Maybe Element]] -> [Element]<br />
admissibleNumbers =<br />
foldl (flip deleteSorted) alphabet .<br />
map (sort . catMaybes)<br />
<br />
admissibleAdditions :: T -> Address -> [Element]<br />
admissibleAdditions sudoku (i,j,k,l) =<br />
admissibleNumbers (map ($ sudoku)<br />
[selectRow (i,k),<br />
selectColumn (j,l),<br />
selectSquare (i,j)])<br />
<br />
allAdmissibleAdditions :: T -> [(Address, [Element])]<br />
allAdmissibleAdditions sudoku =<br />
let adds addr =<br />
(addr, admissibleAdditions sudoku addr)<br />
in map adds<br />
(map fst (filter (isNothing . snd)<br />
(Array.assocs sudoku)))<br />
<br />
<br />
<br />
solutionTree :: T -> ATree T<br />
solutionTree sudoku =<br />
let new (addr,elms) =<br />
map (\elm -> solutionTree (sudoku // [(addr, Just elm)])) elms<br />
in ANode sudoku (map new (allAdmissibleAdditions sudoku))<br />
<br />
treeAltToStandard :: ATree T -> Tree T<br />
treeAltToStandard (ANode sudoku subs) =<br />
Tree.Node sudoku (concatMap (map treeAltToStandard) subs)<br />
<br />
{- Convert a tree with alternatives for each position (ATree)<br />
into a normal tree by choosing one position and its alternative values.<br />
We need to consider only one position per level<br />
because the remaining positions are processed in the sub-levels.<br />
With other words: Choosing more than one position<br />
would lead to multiple reports of the same solution.<br />
<br />
For reasons of efficiency<br />
we choose the position with the least number of alternatives.<br />
If this number is zero, the numbers tried so far are wrong.<br />
If this number is one, then the choice is unique, but maybe still wrong.<br />
If the number of alternatives is larger,<br />
we have to check each alternative.<br />
-}<br />
treeAltToStandardOptimize :: ATree T -> Tree T<br />
treeAltToStandardOptimize (ANode sudoku subs) =<br />
let chooseMinLen [] = []<br />
chooseMinLen xs = minimumBy compareLength xs<br />
in Tree.Node sudoku (chooseMinLen<br />
(map (map treeAltToStandardOptimize) subs))<br />
<br />
maybeComplete :: T -> Maybe Complete<br />
maybeComplete sudoku =<br />
fmap (Array.array fieldBounds)<br />
(mapM (uncurry (fmap . (,))) (Array.assocs sudoku))<br />
<br />
{- All leafs are at the same depth,<br />
namely the number of undetermined fields.<br />
That's why we can safely select all Sudokus at the lowest level. -}<br />
solutions :: T -> [Complete]<br />
solutions sudoku =<br />
let err = error "The lowest level should contain complete Sudokus only."<br />
{- "last'" is more efficient than "last" here<br />
because the program does not have to check<br />
whether deeper levels exist.<br />
We know that the tree is as deep<br />
as the number of undefined fields.<br />
This means that dropMatch returns a singleton list.<br />
We don't check that<br />
because then we would lose the efficiency again. -}<br />
last' = head . dropMatch (filter isNothing (Array.elems sudoku))<br />
in map (fromMaybe err . maybeComplete)<br />
(last' (Tree.levels<br />
(treeAltToStandardOptimize (solutionTree sudoku))))<br />
<br />
<br />
<br />
{- * transformations (can be used for construction, too) -}<br />
<br />
standard :: Complete<br />
standard =<br />
Array.listArray fieldBounds<br />
(map (\(i,j,k,l) -> mod (j+k) 3 * 3 + mod (i+l) 3 + 1)<br />
(range fieldBounds))<br />
<br />
<br />
exampleHawiki0, exampleHawiki1 :: T<br />
exampleHawiki0 = fromString (unlines [<br />
" 5 6 1",<br />
" 48 7 ",<br />
"8 52",<br />
"2 57 3 ",<br />
" ",<br />
" 3 69 5",<br />
"79 8",<br />
" 1 65 ",<br />
"5 3 6 "<br />
])<br />
<br />
exampleHawiki1 = fromString (unlines [<br />
" 6 8 ",<br />
" 2 ",<br />
" 1 ",<br />
" 7 1 2",<br />
"5 3 ",<br />
" 4 ",<br />
" 42 1 ",<br />
"3 7 6 ",<br />
" 5 "<br />
])<br />
<br />
<br />
<br />
<br />
check :: Complete -> Bool<br />
check sudoku =<br />
let checkParts select =<br />
all (\addr -> sort (select addr sudoku) == alphabet) squareRange<br />
in all checkParts [selectRow, selectColumn, selectSquare]<br />
<br />
selectRow, selectColumn, selectSquare ::<br />
(Coord,Coord) -> Array Address element -> [element]<br />
selectRow (i,k) sudoku =<br />
map (sudoku!) (range ((i,0,k,0), (i,2,k,2)))<br />
-- map (sudoku!) (map (\(j,l) -> (i,j,k,l)) squareRange)<br />
selectColumn (j,l) sudoku =<br />
map (sudoku!) (range ((0,j,0,l), (2,j,2,l)))<br />
selectSquare (i,j) sudoku =<br />
map (sudoku!) (range ((i,j,0,0), (i,j,2,2)))<br />
<br />
<br />
{- * conversion from and to strings -}<br />
<br />
put, putLn :: T -> IO ()<br />
put sudoku = putStr (toString sudoku)<br />
putLn sudoku = putStrLn (toString sudoku)<br />
<br />
putC, putCLn :: Complete -> IO ()<br />
putC sudoku = putStr (toString (fmap Just sudoku))<br />
putCLn sudoku = putStrLn (toString (fmap Just sudoku))<br />
<br />
fromString :: String -> T<br />
fromString str =<br />
Array.array fieldBounds (concat<br />
(zipWith (\(i,k) -> map (\((j,l),x) -> ((i,j,k,l),x)))<br />
squareRange<br />
(map (zip squareRange . map charToElem) (lines str))))<br />
<br />
toString :: T -> String<br />
toString sudoku =<br />
unlines<br />
(map (\(i,k) -> map (\(j,l) -> elemToChar (sudoku!(i,j,k,l)))<br />
squareRange)<br />
squareRange)<br />
<br />
charToElem :: Char -> Maybe Element<br />
charToElem c =<br />
toMaybe ('0'<=c && c<='9') (ord c - ord '0')<br />
<br />
elemToChar :: Maybe Element -> Char<br />
elemToChar =<br />
maybe ' ' (\c -> chr (ord '0' + c))<br />
<br />
<br />
{- * helper functions -}<br />
<br />
nest :: Int -> (a -> a) -> a -> a<br />
nest 0 _ x = x<br />
nest n f x = f (nest (n-1) f x)<br />
<br />
toMaybe :: Bool -> a -> Maybe a<br />
toMaybe False _ = Nothing<br />
toMaybe True x = Just x<br />
<br />
compareLength :: [a] -> [b] -> Ordering<br />
compareLength (_:xs) (_:ys) = compareLength xs ys<br />
compareLength [] [] = EQ<br />
compareLength (_:_) [] = GT<br />
compareLength [] (_:_) = LT<br />
<br />
{- | Drop as many elements as the first list is long -}<br />
dropMatch :: [b] -> [a] -> [a]<br />
dropMatch xs ys =<br />
map fromJust (dropWhile isNothing<br />
(zipWith (toMaybe . null) (iterate (drop 1) xs) ys))<br />
</haskell><br />
<br />
<br />
== No guessing ==<br />
<br />
By Simon Peyton Jones.<br />
<br />
Since this page is here I thought I'd add a solver I wrote sometime last year. The main constraint I imposed is that it never guesses, and that it outputs a human-comprehensible explanation of every step of its reasoning. That means there are some puzzles it can't solve. I'd be interested to know if there are any puzzles that it gets stuck on where there is a no-guessing way forward. I made no attempt to make it fast.<br />
<br />
There are two files: [[Media:SudokuPJ.hs]] and [[Media:TestPJ.hs]]. The latter just contains a bunch of test cases; I was too lazy to write a proper parser.<br />
<br />
The main entry point is:<br />
<pre><br />
run1 :: Verbosity -> [String] -> Doc<br />
data Verbosity = All | Terse | Final<br />
</pre><br />
The <tt>[String]</tt> the starting board configuration (see the tests file).<br />
<br />
== Just guessing ==<br />
<br />
By ChrisKuklewicz<br />
<br />
This solver is an implementation of Knuth's "Dancing Links" algorithm for solving binary-cover problems. This algorithm represents the constraints as a sparse binary matrix, with 1's as linked nodes. The nodes are in a vertical and a horizontal doubly linked list, and each vertical list is headed by another node that represents one of the constraints. It is interesting as an example of the rare beast in Haskell: a mutable data structure. The code has been rewritten and cleaned up here [[Media:DancingSudoku.lhs]]. Its main routine is designed to handle the input from [http://www.csse.uwa.edu.au/~gordon/sudoku17 sudoku17] on stdin. Currently it only returns the first solution or calls an error, it can be modified (see comments in the file) to return all solutions in a list. An earlier version used ST.Lazy instead of ST.Strict which made operating on puzzles with many solutions more tractable.<br />
<br />
Other trivia: It uses "mdo" and lazyness to initialize some of the doubly linked lists.<br />
<br />
== Very Smart, with only a little guessing ==<br />
<br />
by ChrisKuklewicz<br />
<br />
This solver does its best to avoid the branch and guess approach. On the 36628 puzzles of [http://www.csse.uwa.edu.au/~gordon/sudokumin.php length 17] it resorts to guessing on only 164. This extra strength comes from examining the constraints that can only be solved in exactly two ways, and how these constraints overlap and interact with each other and remaining possibilities.<br />
<br />
The [http://evenmere.org/~chrisk/chris-sudoku-deduce.tar.gz source code] compiles to take a list of puzzles as input and produces a description of the number of (good and total) guesses required, as well as a shuffled version of the input. If there was guessing, then the shuffled version could be sent back into the solver to see how the difficulty depended on luck. The list of 164 hard puzzles is included with the source code. The Deduce.hs file contains comments.<br />
<br />
The data is stored in a 9x9x9 boolean array, and the only operations are turning off possibilities and branching. For performance the array is thawed, mutated, and frozen. On the set of 36628 puzzles the speed averages 9.4 puzzles solved per second on a 1.33 GHz G4 (ghc-6.4.1 on OS X). I liked the 9x9x9 array since it emphasized the symmetry of the problem.<br />
<br />
== Generalized solver ==<br />
<br />
By Thorkil Naur<br />
<br />
This Su Doku solver is able to solve classes of Su Doku puzzles that extend the ordinary 9*9 puzzles. The [[SuDokuThorkilNaurDocument|documentation]] describes the solver and also some (to the present author at least) surprising properties of various reduction strategies used when solving Su Doku puzzles.<br />
<br />
The following files comprise the Su Doku solver and related code:<br />
<br />
[[Media:Format.hs]]<br />
[[Media:Merge.hs]]<br />
[[Media:SdkMSol2.hs]]<br />
[[Media:SortByF.hs]]<br />
[[Media:SuDoku.hs]]<br />
[[Media:t40.hs]]<br />
[[Media:t44.hs]]<br />
[[Media:Test.hs]]<br />
<br />
For an example of use, the command<br />
<br />
<pre><br />
runhugs SdkMSol2 \<br />
tn1 \<br />
Traditional 3 \<br />
-#123456789 \<br />
1-53---9- \<br />
---6----- \<br />
------271 \<br />
82------- \<br />
---487--- \<br />
------53- \<br />
23------- \<br />
--7-59--- \<br />
--6---8-4<br />
</pre><br />
<br />
produces output that, among other things, contain<br />
<br />
<pre><br />
tn1: Solutions:<br />
1 7 5 3 2 8 4 9 6<br />
9 4 2 6 7 1 3 8 5<br />
3 6 8 5 9 4 2 7 1<br />
8 2 9 1 3 5 6 4 7<br />
6 5 3 4 8 7 9 1 2<br />
7 1 4 9 6 2 5 3 8<br />
2 3 1 8 4 6 7 5 9<br />
4 8 7 2 5 9 1 6 3<br />
5 9 6 7 1 3 8 2 4<br />
</pre><br />
<br />
== Simple Small Solver ==<br />
I haven't looked at the other solvers in detail yet, so I'm not sure what is good or bad about mine, but here it is:<br />
<br />
http://darcs.brianweb.net/sudoku/Sudoku.pdf<br />
http://darcs.brianweb.net/sudoku/src/Sudoku.lhs<br />
<br />
-Brian Alliet <brian@brianweb.net><br />
<br />
== Backtrack Monad Solver ==<br />
<br />
This is a simple but fast solver that uses standard<br />
monads from the [[MonadTemplateLibrary]] in the [[StandardLibraries]].<br />
<br />
Besides being Yet Another Example of a Sudoko solver,<br />
I think it is also a nice somewhat-nontrivial example of<br />
monads in practice.<br />
<br />
The idea is that the monad StateT s [] does backtracking.<br />
It means "iterate over a list while keeping state,<br />
but re-initialize to the original state on each iteration".<br />
<br />
I have several (Unix command line) front-ends to this<br />
module, available upon request. The one I use most creates<br />
and prints six new Sudoku puzzles on a page, with<br />
fine-grain control over the difficulty of the puzzle.<br />
This has made me quite popular among friends and<br />
extended family.<br />
<br />
- [[YitzGale]]<br />
<br />
<haskell><br />
{-# OPTIONS_GHC -fglasgow-exts #-}<br />
<br />
-- Solve a Sudoku puzzle<br />
<br />
module Sudoku where<br />
<br />
import Control.Monad.State<br />
import Data.Maybe (maybeToList)<br />
import Data.List (delete)<br />
<br />
type Value = Int<br />
type Cell = (Int, Int) -- One-based coordinates<br />
<br />
type Puzzle = [[Maybe Value]]<br />
type Solution = [[Value]]<br />
<br />
-- The size of the puzzle.<br />
sqrtSize :: Int<br />
sqrtSize = 3<br />
size = sqrtSize * sqrtSize<br />
<br />
-- Besides the rows and columns, a Sudoku puzzle contains s blocks<br />
-- of s cells each, where s = size.<br />
blocks :: [[Cell]]<br />
blocks = [[(x + i, y + j) | i <- [1..sqrtSize], j <- [1..sqrtSize]] |<br />
x <- [0,sqrtSize..size-sqrtSize],<br />
y <- [0,sqrtSize..size-sqrtSize]]<br />
<br />
-- The one-based number of the block that a cell is contained in.<br />
blockNum :: Cell -> Int<br />
blockNum (row, col) = row - (row - 1) `mod` sqrtSize + (col - 1) `div` sqrtSize<br />
<br />
-- When a Sudoku puzzle has been partially filled in, the following<br />
-- data structure represents the remaining options for how to proceed.<br />
data Options = Options {<br />
cellOpts :: [[[Value]]], -- For each cell, a list of possible values<br />
rowOpts :: [[[Cell ]]], -- For each row and value, a list of cells<br />
colOpts :: [[[Cell ]]], -- For each column and value, a list of cells<br />
blkOpts :: [[[Cell ]]] -- For each block and value, a list of cells<br />
} deriving Show<br />
modifyCellOpts f = do {opts <- get; put $ opts {cellOpts = f $ cellOpts opts}}<br />
modifyRowOpts f = do {opts <- get; put $ opts {rowOpts = f $ rowOpts opts}}<br />
modifyColOpts f = do {opts <- get; put $ opts {colOpts = f $ colOpts opts}}<br />
modifyBlkOpts f = do {opts <- get; put $ opts {blkOpts = f $ blkOpts opts}}<br />
<br />
-- The full set of initial options, before any cells are constrained<br />
initOptions :: Options<br />
initOptions = Options {<br />
cellOpts = [[[1..size] | _ <- [1..size]] | _ <- [1..size]],<br />
rowOpts = [[[(r, c) | c <- [1..size]] | _ <- [1..size]] | r <- [1..size]],<br />
colOpts = [[[(r, c) | r <- [1..size]] | _ <- [1..size]] | c <- [1..size]],<br />
blkOpts = [[b | _ <- [1..size]] | b <- blocks]}<br />
<br />
solve :: Puzzle -> [Solution]<br />
solve puz = evalStateT (initPuzzle >> solutions) initOptions<br />
where<br />
initPuzzle =<br />
sequence_ [fixCell v (r, c) | (row, r) <- zip puz [1..],<br />
(val, c) <- zip row [1..],<br />
v <- maybeToList val]<br />
<br />
-- Build a list of all possible solutions given the current options.<br />
-- We use a list monad INSIDE a state monad. That way,<br />
-- the state is re-initialized on each element of the list iteration,<br />
-- allowing backtracking when an attempt fails (with mzero).<br />
solutions :: StateT Options [] Solution<br />
solutions = solveFromRow 1<br />
where<br />
solveFromRow r<br />
| r > size = return []<br />
| otherwise = do<br />
row <- solveRowFromCol r 1<br />
rows <- solveFromRow $ r + 1<br />
return $ row : rows<br />
solveRowFromCol r c<br />
| c > size = return []<br />
| otherwise = do<br />
vals <- gets $ (!! (c - 1)) . (!! (r - 1)) . cellOpts<br />
val <- lift vals<br />
fixCell val (r, c)<br />
row <- solveRowFromCol r (c + 1)<br />
return $ val : row<br />
<br />
-- Fix the value of a cell.<br />
-- More specifically - update Options to reflect the given value at<br />
-- the given cell, or mzero if that is not possible.<br />
fixCell :: (MonadState Options m, MonadPlus m) =><br />
Value -> Cell -> m ()<br />
fixCell val cell@(row, col) = do<br />
vals <- gets $ (!! (col - 1)) . (!! (row - 1)) . cellOpts<br />
guard $ val `elem` vals<br />
modifyCellOpts $ replace2 row col [val]<br />
modifyRowOpts $ replace2 row val [cell]<br />
modifyColOpts $ replace2 col val [cell]<br />
modifyBlkOpts $ replace2 blk val [cell]<br />
sequence_ [constrainCell v cell | v <- [1..size], v /= val]<br />
sequence_ [constrainCell val (row, c) | c <- [1..size], c /= col]<br />
sequence_ [constrainCell val (r, col) | r <- [1..size], r /= row]<br />
sequence_ [constrainCell val c | c <- blocks !! (blk - 1), c /= cell]<br />
where<br />
blk = blockNum cell<br />
<br />
-- Assert that the given value cannot occur in the given cell.<br />
-- Fail with mzero if that means that there are no options left.<br />
constrainCell :: (MonadState Options m, MonadPlus m) =><br />
Value -> Cell -> m ()<br />
constrainCell val cell@(row, col) = do<br />
constrainOpts row col val cellOpts modifyCellOpts (flip fixCell cell)<br />
constrainOpts row val cell rowOpts modifyRowOpts (fixCell val)<br />
constrainOpts col val cell colOpts modifyColOpts (fixCell val)<br />
constrainOpts blk val cell blkOpts modifyBlkOpts (fixCell val)<br />
where<br />
blk = blockNum cell<br />
constrainOpts x y z getOpts modifyOpts fixOpts = do<br />
zs <- gets $ (!! (y - 1)) . (!! (x - 1)) . getOpts<br />
case zs of<br />
[z'] -> guard (z' /= z)<br />
[_,_] -> when (z `elem` zs) $ fixOpts (head $ delete z zs)<br />
(_:_) -> modifyOpts $ replace2 x y (delete z zs)<br />
_ -> mzero<br />
<br />
-- Replace one element of a list.<br />
-- Coordinates are 1-based.<br />
replace :: Int -> a -> [a] -> [a]<br />
replace i x (y:ys)<br />
| i > 1 = y : replace (i - 1) x ys<br />
| otherwise = x : ys<br />
replace _ _ _ = []<br />
<br />
-- Replace one element of a 2-dimensional list.<br />
-- Coordinates are 1-based.<br />
replace2 :: Int -> Int -> a -> [[a]] -> [[a]]<br />
replace2 i j x (y:ys)<br />
| i > 1 = y : replace2 (i - 1) j x ys<br />
| otherwise = replace j x y : ys<br />
replace2 _ _ _ _ = []<br />
</haskell><br />
<br />
== In-flight entertainment ==<br />
<br />
By Lennart Augustsson<br />
<br />
When on a Lufthansa trans-atlantic flight in 2005 I picked up the in-flight magazine and found a Sudoku puzzle. I decided to finally try one. After solving half of it by hand I got bored. Surely, this mechanical task is better performed by a machine? So I pulled out my laptop and wrote a Haskell program.<br />
<br />
The program below is what I wrote on the plane, except for some comments that I've added. I have made no attempt as making it fast, so the nefarious test puzzle below takes a minute to solve.<br />
<br />
First, the solver without user interface:<br />
<haskell><br />
module Sudoku(Square, Board, ColDigit, RowDigit, BoxDigit, Digit, initialBoard, getBoard, mkSquare, setSquare, solveMany) where<br />
import Char(intToDigit, digitToInt)<br />
import List ((\\), sortBy)<br />
<br />
-- A board is just a list of Squares. It always has all the squares.<br />
data Board = Board [Square]<br />
deriving (Show)<br />
<br />
-- A Square contains its column (ColDigit), row (RowDigit), and<br />
-- which 3x3 box it belongs to (BoxDigit). The box can be computed<br />
-- from the row and column, but is kept for speed.<br />
-- A Square also contains it's status: either a list of possible<br />
-- digits that can be placed in the square OR a fixed digit (i.e.,<br />
-- the square was given by a clue or has been solved).<br />
data Square = Square ColDigit RowDigit BoxDigit (Either [Digit] Digit)<br />
deriving (Show)<br />
<br />
type ColDigit = Digit<br />
type RowDigit = Digit<br />
type BoxDigit = Digit<br />
type Digit = Char -- '1' .. '9'<br />
<br />
-- The initial board, no clues given so all digits are possible in all squares.<br />
initialBoard :: Board<br />
initialBoard = Board [ Square col row (boxDigit col row) (Left allDigits) |<br />
row <- allDigits, col <- allDigits ]<br />
<br />
-- Return a list of rows of a solved board.<br />
-- If used on an unsolved board the return value is unspecified.<br />
getBoard :: Board -> [[Char]]<br />
getBoard (Board sqs) = [ [ getDigit d | Square _ row' _ d <- sqs, row' == row ] | row <- allDigits ]<br />
where getDigit (Right d) = d<br />
getDigit _ = '0'<br />
<br />
allDigits :: [Char]<br />
allDigits = ['1' .. '9']<br />
<br />
-- Compute the box from a column and row.<br />
boxDigit :: ColDigit -> RowDigit -> BoxDigit<br />
boxDigit c r = intToDigit $ (digitToInt c - 1) `div` 3 + (digitToInt r - 1) `div` 3 * 3 + 1<br />
<br />
-- Given a column, row, and a digit make a (solved) square representing this.<br />
mkSquare :: ColDigit -> RowDigit -> Digit -> Square<br />
mkSquare col row c | col `elem` allDigits && row `elem` allDigits && c `elem` allDigits <br />
= Square col row (boxDigit col row) (Right c)<br />
mkSquare _ _ _ = error "Bad mkSquare"<br />
<br />
-- Place a given Square on a Board and return the new Board.<br />
-- Illegal setSquare calls will just error out. The main work here<br />
-- is to remove the placed digit from the other Squares on the board<br />
-- that are in the same column, row, or box.<br />
setSquare :: Square -> Board -> Board<br />
setSquare sq@(Square scol srow sbox (Right d)) (Board sqs) = Board (map set sqs)<br />
where set osq@(Square col row box ds) =<br />
if col == scol && row == srow then sq<br />
else if col == scol || row == srow || box == sbox then (Square col row box (sub ds))<br />
else osq<br />
sub (Left ds) = Left (ds \\ [d])<br />
sub (Right d') | d == d' = error "Impossible setSquare"<br />
sub dd = dd<br />
setSquare _ _ = error "Bad setSquare"<br />
<br />
-- Get the unsolved Squares from a Board.<br />
getLeftSquares :: Board -> [Square]<br />
getLeftSquares (Board sqs) = [ sq | sq@(Square _ _ _ (Left _)) <- sqs ]<br />
<br />
-- Given an initial Board return all the possible solutions starting<br />
-- from that Board.<br />
-- Note, this all happens in the list monad and makes use of lazy evaluation<br />
-- to avoid work. Using the list monad automatically handles all the backtracking<br />
-- and enumeration of solutions.<br />
solveMany :: Board -> [Board]<br />
solveMany brd =<br />
case getLeftSquares brd of<br />
[] -> return brd -- Nothing unsolved remains, we are done.<br />
sqs -> do<br />
-- Sort the unsolved Squares by the ascending length of the possible<br />
-- digits. Pick the first of those so we always solve forced Squares<br />
-- first.<br />
let Square c r b (Left ds) : _ = sortBy leftLen sqs<br />
leftLen (Square _ _ _ (Left ds1)) (Square _ _ _ (Left ds2)) = compare (length ds1) (length ds2)<br />
leftLen _ _ = error "bad leftLen"<br />
sq <- [ Square c r b (Right d) | d <- ds ] -- Try all possible moves<br />
solveMany (setSquare sq brd) -- And solve the extended Board.<br />
</haskell><br />
<br />
Second, a simple user interface (a different user interface that I have is an Excell addin):<br />
<haskell><br />
module Main where<br />
import Sudoku<br />
<br />
-- Col Row Digit<br />
solve :: [((Char, Char), Char)] -> [[Char]]<br />
solve crds =<br />
let brd = foldr add initialBoard crds<br />
add ((c, r), d) = setSquare (mkSquare c r d)<br />
in case solveMany brd of<br />
[] -> error "No solutions"<br />
b : _ -> getBoard b<br />
<br />
-- The parse assumes that squares without a clue<br />
-- contain '0'.<br />
main = interact $<br />
unlines . -- turn it into lines<br />
map (concatMap (:" ")) . -- add a space after each digit for readability<br />
solve . -- solve the puzzle<br />
filter ((`elem` ['1'..'9']) . snd) . -- get rid of non-clues<br />
zip [ (c, r) | r <- ['1'..'9'], c <- ['1'..'9'] ] . -- pair up the digits with their coordinates<br />
filter (`elem` ['0'..'9']) -- get rid of non-digits<br />
</haskell><br />
<br />
<br />
== Sudoku incrementally, à la Bird ==<br />
<br />
:“As part of a new [http://cs.nott.ac.uk/~gmh/afp.html Advanced Functional Programming] course in Nottingham, [http://cs.nott.ac.uk/~gmh/ Graham Hutton] presented a Haskell approach to solving Sudoku puzzles, based upon notes from [http://web.comlab.ox.ac.uk/oucl/work/richard.bird/ Richard Bird]. The approach is classic Bird: start with a simple but impractical solver, whose efficiency is then improved in a series of steps. The end result is an elegant program that is able to solve any Sudoku puzzle in an instant. It’s also an excellent example of what has been termed “wholemeal programming” — focusing on entire data structures rather than their elements.” (Transplanted from [http://lambda-the-ultimate.org/node/772 LtU].)<br />
<br />
A full talk-through of the evolution of the code may be found [http://cs.nott.ac.uk/~gmh/sudoku.lhs under the course page]. --[[User:Liyang|Liyang]] 13:35, 27 July 2006 (UTC)<br />
<br />
== Add Your Own ==<br />
<br />
If you have a Sudoku solver you're proud of, put it here. This ought to be a good way of helping people learn some fun, intermediate-advanced techniques in Haskell.<br />
<br />
== Test Boards ==<br />
<br />
Here's an input file to test the solvers on. Zeroes represent blanks.<br />
<pre><br />
0 5 0 0 6 0 0 0 1<br />
0 0 4 8 0 0 0 7 0<br />
8 0 0 0 0 0 0 5 2<br />
2 0 0 0 5 7 0 3 0<br />
0 0 0 0 0 0 0 0 0<br />
0 3 0 6 9 0 0 0 5<br />
7 9 0 0 0 0 0 0 8<br />
0 1 0 0 0 6 5 0 0<br />
5 0 0 0 3 0 0 6 0<br />
</pre><br />
<br />
A nefarious one:<br />
<br />
<pre><br />
0 0 0 0 6 0 0 8 0<br />
0 2 0 0 0 0 0 0 0<br />
0 0 1 0 0 0 0 0 0<br />
0 7 0 0 0 0 1 0 2<br />
5 0 0 0 3 0 0 0 0<br />
0 0 0 0 0 0 4 0 0<br />
0 0 4 2 0 1 0 0 0<br />
3 0 0 7 0 0 6 0 0<br />
0 0 0 0 0 0 0 5 0 <br />
</pre><br />
<br />
Chris Kuklewicz writes, "You can go get the 36,628 distict minimal puzzles from<br />
[http://www.csse.uwa.edu.au/~gordon/sudokumin.php csse.uwa.edu] that have only 17 clues. Then you can run all of them through your program to locate the most evil ones, and use them on your associates."</div>Liyanghttps://wiki.haskell.org/index.php?title=AngloHaskell/2007&diff=5022AngloHaskell/20072006-07-27T00:42:45Z<p>Liyang: </p>
<hr />
<div>On June the 9th, Microsoft Research sent out an advert for job. This job involves maintaining the Glorious Glasgow Compiler, and created quite a stir in the Haskell community: It's the job we've all been hoping for! After a while the CV's were sent, and Microsoft Research has now invited several Haskellers for an interview at Cambridge, UK.<br />
<br />
This event has been recognized as a great opportunity for a Haskell gathering and we hereby invite all Haskellers (and other cool people) to a fun couple of days in Cambridge.<br />
<br />
Date:<br />
* Friday the 4th and Saturday the 5th of August.<br />
<br />
Contact person:<br />
Shae Erisson - +46 70 3915045<br />
<br />
If you're coming into Cambridge by train and want to join in the fun, call Shae at the number above.<br />
<br />
Definite attendees:<br />
* Simon Peyton-Jones and Simon Marlow (Friday only)<br />
* Lemmih (will arrive the 2nd and leave the 6th)<br />
* PhilippaCowderoy (barring emergencies, can hang around)<br />
* ShaeErisson (can stay for a couple of days)<br />
* Peter Nuttall (am around from the 26 July onwards, baring the 3rd when I'm in ipswitch)<br />
* genneth (am in Cambridge anyway)<br />
* GaneshSittampalam (for at least some of the time)<br />
* Neil Mitchell - ndm (can come for the 5th, if I can have some floor space)<br />
* Liyang HU<br />
* greenrd<br />
<br />
Possible attendees:<br />
* dcoutts (depends on the date)<br />
* xerox (depends on the date)<br />
* GK (depends on the date; it'd be great to meet some of the wonderful Haskell community folks)<br />
* EdwinBrady (depends on the date; would probably stay a couple of days)<br />
* vincenz (depends on the date, preferably a day or two, partially weekend)<br />
** Would need details in advance to reserve ticket for EUROSTAR<br />
<br />
Lodging:<br />
* Are there places we can crash, rooms we can share?<br />
** If dcoutts goes then he can probably offer floor space to a few.<br />
** I (psnl) have 14 sq metres of floor crash space in a college.<br />
<br />
Programme:<br />
* Is there a more concrete plan? What exactly are we doing?<br />
** Planning is taking place on IRC: #anglohaskell on irc.freenode.net<br />
** Talks:<br />
*** greenrd wants to talk about simulating dependent types in Haskell<br />
*** Lemmih could give a short talk on breakpoints in GHC<br />
*** Liyang is prepared to wave his arms in the air while not making much sense about idiomatic programming (and '''not just''' the ''applicative idioms'' you've witnessed previously...) with an additional helping of memoisation.<br />
** some kind of coding / pair programming? Maybe set aside one of the two days for this?<br />
<br />
Miscellaneous:<br />
* Please could everyone bring or make a nametag that identifies you by your real name and/or IRC name.</div>Liyanghttps://wiki.haskell.org/index.php?title=AngloHaskell/2007&diff=4984AngloHaskell/20072006-07-23T21:40:32Z<p>Liyang: </p>
<hr />
<div>On June the 9th, Microsoft Research sent out an advert for job. This job involves maintaining the Glorious Glasgow Compiler, and created quite a stir in the Haskell community: It's the job we've all been hoping for! After a while the CV's were sent, and Microsoft Research has now invited several Haskellers for an interview at Cambridge, UK.<br />
<br />
This event has been recognized as a great opportunity for a Haskell gathering and we hereby invite all Haskellers (and other cool people) to a fun couple of days in Cambridge.<br />
<br />
Date:<br />
* Friday the 4th and Saturday the 5th of August.<br />
<br />
Definite attendees:<br />
* Lemmih (anytime between 31st of July to 11th of August, can stay for a couple of days)<br />
* PhilippaCowderoy (barring emergencies, can hang around)<br />
* ShaeErisson (can stay for a couple of days)<br />
* Peter Nuttall (am around from the 26 July onwards, baring the 3rd when I'm in ipswitch)<br />
* Gen Zhang (am in Cambridge anyway)<br />
* GaneshSittampalam (for at least some of the time)<br />
* Neil Mitchell - ndm (can come for the 5th, if I can have some floor space)<br />
* Liyang HU (provided there's some sort of concrete plan...)<br />
<br />
Possible attendees:<br />
* dcoutts (depends on the date)<br />
* xerox (depends on the date)<br />
* GK (depends on the date; it'd be great to meet some of the wonderful Haskell community folks)<br />
* EdwinBrady (depends on the date; would probably stay a couple of days)<br />
* vincenz (depends on the date, preferably a day or two, partially weekend)<br />
** Would need details in advance to reserve ticket for EUROSTAR<br />
* greenrd<br />
<br />
Lodging:<br />
* Are there places we can crash, rooms we can share?<br />
* If dcoutts goes then he can probably offer floor space to a few.<br />
* I (psnl) have 14 sq metres of floor crash space in a college.<br />
<br />
Programme:<br />
* Is there a more concrete plan? What exactly are we doing?</div>Liyang