Function call expression 参戦記

公私ともにバタバタしていて、blog も twitter も放置していますが、どうにか生きてます。
anarchy golf - Function call expression に関して、youzさんが解説を書けと言ってるので、２位という立場で僭越ながら書いてみる。
２週間前に問題を見て、なんて好みの問題だろうと思い、誰も参加してないけど submit。
こういう処理系ちっくな問題のときはだいたい、Parsec で考えを整理してから実装してる。今回もまずParsec で下書き。

import Text.ParserCombinators.Parsec

m @ main = getLine >>= putStrLn . either show id . parse expr "" >> m

expr = do
  f <- char 'f'
  xs <- many $ do
    char '('
    e <- expr
    char ')'
    return e
  return $ foldl apply [f] xs

apply f x = '(' : f ++ ' ' : x ++ ")"

これを Parsec 使わずに書きなおす。Programming in Haskell にもある通り、パーサーは文字列を受け取って、パースした結果と残りの文字列を返せばいい。いろいろ小細工して 98B。

m@main=getLine>>=putStrLn.(!1)>>m
(_:'(':a)?b=a!0?('(':b++' ':a!1++")")
(_:a)?b=[a,b]
a!i=a?"f"!!i

もう少し縮みそうな気がするも、競争相手がいないので放置していたところ、１週間前に notogawaさんが以下のツィート。
「@Lost_dog_ さんが嘆いていたのでFunction call expressionを処理」
そうですか。こちらが身を削って書いたコードを易々と“処理”されたのですね。しかも 91B。7B 差。
悔しさに歯噛みしつつ、アイデアも時間もなくそのまま deadline 当日を迎える。
前夜に GCJ Round1B があり、寝不足の頭と残念な結果をお供に、子供と鉄道博物館へ。
半分諦めていたけど、運転シミュレータに並びながらあれこれ考える。
今の方針で縮めるとしたら getLine と putStrLn で１行ずつ処理してるところくらいだけど、局所最適化してるので、このまま縮めるのは無理だろう。スタックマシンの処理系実装みたいなことをやればもう少しシンプルに書けるのでは？
そんなアイデアをベースに、プラレールに興じる子供の横で、鉄道手帳にメモしながら検討する。文字 'f' が来たらスタックに積む。'(' はたぶん無視しても大丈夫。')' が来たらスタックのトップの２要素を関数適用して "(f x)" みたいな文字列にすればよさそう。さらに '\n' も '(' と同じように無視して、入力をまとめて処理すれば、入力１行に対して解析結果がスタックに１行積み上がるから、反転して出力すれば求める結果が得られるんじゃないか？！
"f(f)(f)" とか "f(f(f))" みたいな入力を当てはめて上手くいきそうだったので、コーディングにとりかかる。といってもＰＣなど持ってないので、携帯からあなごるのサイトにアクセスして、フォームで入力。記号の入力が激しく面倒でした。でもやればできるもんです。コンパイルエラーもなく一発で success ！92B！惜しい。

main=interact$unlines.reverse.foldl(&)[]
s&'f'="f":s                       -- 'f'が来たらスタックに積む
(b:a:s)&')'=('(':a++' ':b++")"):s -- ')'が来たらスタックの先頭２要素を関数適用
s&_=s                             -- 残り（'(', '\n'）は無視

あと 1B をどうすればいいか、残り30分でつらつら考えましたが、時間切れ。
notogawaさんの解を見て納得。'\n' もスタックに積んじゃえば、そのままスタックの文字を結合して答えが出るんだ。
あと、改めて考えると、')' は後置（逆ポーランド）記法の関数適用演算子と捉えられるんですよね。面白いなぁ。
負けたことは悔しいですが、とても楽しい問題でした。infix to postfix も同じように縮まないだろうかと考えたり。