Turing Machine

anarchy golf - Turing Machine にハマりました。
最終的に通したコードはこんな感じ。空白を削って 168B です。

main = interact $ f "" 0 2 . map words . lines
f s i j m
  | j<2 = s
  | 0<1 = f (take i s ++ a : drop(i+1)s) (max i 0 + b%61) (c%63) m
  where
  [a,b,c] = m!!k!!j
  k
    | i<0 = 1
    | 0<1 = (s++"0")!!i%47
n%i = fromEnum n - i

このコードは、簡単に短くすることができます。
7 行目以降、k を求めるところで、リストの範囲を超えたインデックスが渡されるのを防ぐために場合分けをしてますが、リストの前にも要素を足してしまえば、場合分けは不要。
こんな感じで、160B まで縮みます。

main = interact $ f "" 1 2 . map words . lines
f s i j m
  | j<2 = s
  | 0<1 = f (take(i-1)s ++ a : drop i s) (max i 1 + b%61) (c%63) m
  where
  [a,b,c] = m!!(('0':s++"0")!!i%47)!!j
n%i = fromEnum n - i

ただ残念ながらこのコードは通りません。test #3 で timeout。
プロファイルもとって調べてみたら、(++) のコストがとにかく高くて、(:) で駄目押ししてる感じ。
ぎりぎり 1 秒くらいなので、運がよければ通るかもと 100 回くらい submit（ごめんなさい、ごめんなさい）してみたけど、やっぱり駄目。
あんまり悔しいので、ここにＵＰしときます。
Haskell の time limit を 1.5 秒くらいに‥‥。

S コンビネータいろいろ

上のエントリでのプチ収穫。
モナドとコンビネータ論理のコラボ！とか喜んでたら、既に先達が。
[Haskell-cafe] Point-free style
【オブジェクト倶楽部： 2008-33号】

import Control.Monad.Reader
s = flip (>>=) . flip
k = return

そういえばArrowでも書けるな。
毎日Haskell - FSWikiLite（2007-08-08）

import Control.Arrow
s = ((app .).).(&&&)

もちろんこれもある。でも Control.Applicative って、他の場面で使ったことない。
何のためのモジュール？

import Control.Applicative
s = (<*>)

でもやっぱり、いちいち import するのは嫌だ。Prelude の関数で書きたい。
とするとやっぱりこれか。
[Haskell-cafe] Point-free style

s = (((. head . uncurry zip . splitAt 1 . repeat) . uncurry) .) . (.) . flip

以前ほど変態だとは感じないけど、z から (z, z) を作る部分（head以降）は書けたとしても、uncurry (flip x . y) なんてとても思いつかない。頭いいな〜。

s x y z = uncurry (flip x . y) $ head $ uncurry zip $ splitAt 1 $ repeat z

B も C も K も I もあるんだから、 S コンビネータも Prelude に用意してほしいと思ったのですが、既にそういう議論はあったみたいです。
[Haskell-cafe] Point-free style

Reader モナドは引数隠蔽モナド

以前にもエントリを書きましたが、Readerモナドがさっぱり分からないので、もう一度勉強してみました。
あまり深く考えずに Reader a を a -> と読み替えると、関数の型は以下のようになります。

関数	型	等価な関数
(>>=)	(a->b) -> (b->a->c) -> a -> c
(=<<)	(a->b->c) -> (b->a) -> b -> c
(>>)	(a->b) -> (a->c) -> a -> c	flip const
return	a -> b -> a	const
ap	(a->b->c) -> (a->b) -> a -> c	<*>
liftM	(a->b) -> (c->a) -> c -> b	(.)
ask	a -> a	id
local	(a->a) -> (a->b) -> a -> b	flip (.)

ちょっと確かめてみると、確かに等価であることが分かります。

Prelude Control.Monad.Reader> (+3)`liftM`(*3) $ 2
9
Prelude Control.Monad.Reader> return 5 3
5
Prelude Control.Monad.Reader> ask 4
4

つまり Reader モナドは引数隠蔽モナドだと思えばいいわけですね。本当は第一引数があるのだけれども、あたかもそれが引数に存在しないかのように記述できると。
ということは、Reader モナドを使って書いた↓の simpleR、modifyR は simple、modify みたいに書いても同じことだ。
僕にはこの方が分かりやすいな。引数を引き回したくない気持ちは確かに分からないでもないけど、そのためにモナドの枠組みで do とか書かなきゃいけないのは、ちょっと面倒な気がする。

import Control.Monad.Reader

env :: [Int]
env = [1,2,3]

simpleR :: Reader [Int] Int
simpleR = return head =<< ask

modifyR :: Reader [Int] Int
modifyR = local tail simpleR

simple :: [Int] -> Int
simple = head

modify :: [Int] -> Int
modify = simple . tail

main :: IO ()
main = do
 print $ runReader simpleR env
 print $ runReader modifyR env
 print $ simple env
 print $ modify env

畳

Problem 256 を 紹介する - 落書き、時々落学
Problem 256 - Project Euler

面白そう！
でも僕は ２５３問目 が解けず、止まったままです。皆さん代わりに解いてください。

squill

squill というDBアクセスのための DSL があります。
https://squill.dev.java.net/
ざっと触ってみたのですが、Tupleクラスとか用意されていて、似たようなO/Rマッパーと比べてもなかなかよくできている感じ。
Javaでここまでできれば十分だと思うのですが、id:masanobuimai は何を言っときたかったんだろう。

HaskellDB

HaskellDBを触っています。
基本が射影と制限と直積(関係代数 - Wikipedia)で、INNER JOIN ましてや OUTER JOIN なんて完全に無視してるところとか、NULL可の列とNULL不可の列をそのままでは比較できないところとか、とにかく理論派です。現場の都合なんて考えちゃいない。
実装もちょっとアヤしくて、timestamp型の列とかdate型の列とか参照しようとしただけでエラーになります。どうも型変換に失敗してるっぽい（データベースは PostgreSQL。MySQL とか HSQL なら上手くいくかも）。あとは複数のテーブルに同じ名前の列があったとき、テーブルをきちんと指定しても片方のテーブルのデータしか取り出せませんでした。どっちもバグじゃないかなぁ。
でも、こういうの大好き。

test = do
  pet <- table pets
  owner <- table owners
  -- ownerId が NULL可だと、Int 型と Maybe Int 型なので、そのままでは比較できない
  restrict (owner!xid .==. pet!ownerId)
  project (
    name << pet!name
    -- ↓の行がエラーになる
    -- birthDate << pet!birthDate
    -- ownerName が name だと、テーブルを指定してもpet!nameが返ってしまう
    ownerName << owner!ownerName
    )

LINQテクノロジ入門

LINQテクノロジ入門 MS VS2008による新たなクエリ構築技法 (マイクロソフトコンサルティングサービステクニカルリファレンスシリーズ)

ちょっと勉強してるのですが、この本、いいです。
僕みたいに初めて C# を触るド素人でも手を動かして確かめられるように、懇切丁寧な手順が書いてあるし、そうかと思うと、一部では裏の仕組みにまで踏み込んで、なぜそういう動作になるのか詳しく説明されています。

一番感心したのはラムダ式の展開についての解説。
Where メソッドにラムダ式を渡すと、式ツリーを経由して対応する SQL に変換してくれるわけですが、同じ匿名関数だからといって匿名メソッド（デリゲート）を渡してしまうと、式ツリーに変換できないので、where 句の無い SQL が実行されてしまう。またラムダ式で渡しても、IEnumerable 型だと解釈されると、やはり変換されない。

言われてみれば当たり前なのですが、ラムダ式は何かの Syntax Sugar ではなく、新しい言語仕様なんですね。
こういう強力な仕様を後から付け足してしまうあたり、何というか .NET は流石だと思いました。（節操が無いと言われるわけだ）