#ひとくちに Lisper といってもいろんな人がいますよねぇ。あるいは、言語で縛るんじゃなくて、「言語は何でもいいから○○のアルゴリズムを何も見ないで実装できる人」とかだとどうでしょう？
#面接まで来たらいろいろできると思うけど(私が好きなのはやっぱり"Coders at work"で誰かが言ってたけど、自分の作ったものについて詳しく説明させるってやつ)、今の話は募集要綱をどう書くかってことですよね。それなら面接人数を絞り込む篩でさえあればいいんだから、マイナーな言語をいくつか列挙して「このうち3つ以上でnontrivialなプログラムを書いたことがある」とかでもいいかも。そういう言語マニアみたいな性質の人を集めたければ、だけど。
#なるほどー
#言語マニアってのもやっかいな側面はありますからねー
#何にせよ、募集要項は、「明らかに対象外の人を除外する」ためのものであって「その条件でベストな人を選ぶ」ものじゃないから、「その属性を持っている人」について考えるよりも、「その属性を持ってない人」(その属性を持ってない人に来て欲しいか)について考えるべきじゃないでしょうか。
#そのとおりですね
#ちょっとプログラマを(アメリカで)集めたいというのがあって, ふとPGの言ってたことがきになったりしました.
##こんなのもあるんですねぇ
#こんなことを言っている人も。 http://j.mp/kgV7pD Rails Hub情報局: 実力を測るのにFizzBuzzも二分探索も使えない #「実力」って一次元じゃないからなあ。
#「デバッグさせる」ってのはなんか良さそうなきがする
#それは良いんだが、問題を用意するのが難しそうだ。
#確かにw
#Gaucheのutil.combinationsのテストスイートに足りないパターンが見つかりました。
#permutations-for-eachのsetに長さ４と５以上のリストを与えたパターンが無いですね。
#リポジトリにはあるのかな。
#最近いじってないから、最初から欠けている可能性高いです。
#Nendoでfor-each-with-indexを実装していないのに、テストケースが全て通ったので、調べてみたら発見したという次第です。
#git clone中...
#とりあえず、git pull origin master したのですが、masterは Gauche 0.9.1同様、テストケースが欠けていますね。
#Nendo用にテストケースを足そうと思っているので、できたら本家(Gauche)にもフィードバックします。
#setが'(a b c d)のパターンと setが'(a b c d e) のパターンですね。
#テストスイートのファイルに保持するには、'(a b c d e)の結果のリストがデカいですが...
#結果を、別の関数で生成するようにできると嬉しいですね。
#ふたとおりのやり方で作って、結果が一致すれば良し、という考え方です。
#なるほど。クロスチェックですね。
#Gaucheのほうはスピード重視で setの長さごとに最適化されているんですね。
#ちなみに、fold-with-indexが使われているところは、Nendoではfold-with-indexを作るのをあきらめて書きな直しました（弱;）
#Gauche 0.9.1は
#;; permute set. all elements are considered distinct.
;; the shortcut for 3 elements or less speeds up a bit.
(define (permutations set)
(match set
[() (list '())]
[(a) (list set)]
[(a b) `(,set (,b ,a))]
[(a b c)
`(,set (,a ,c ,b) (,b ,a ,c) (,b ,c ,a) (,c ,a ,b) (,c ,b ,a))]
[else
(reverse!
(fold-with-index
(lambda (ind elt acc)
(fold (lambda (subperm acc) (acons elt subperm acc))
acc
(permutations (but-kth set ind))))
'()
set))]))#こうなっていますが...
#Nendoでは
#;; permute set. all elements are considered distinct.
;; the shortcut for 3 elements or less speeds up a bit.
(define (permutations set)
(match set
[() (list '())]
[(a) (list set)]
[(a b) `(,set (,b ,a))]
[(a b c)
`(,set (,a ,c ,b) (,b ,a ,c) (,b ,c ,a) (,c ,a ,b) (,c ,b ,a))]
[else
(append-map
(lambda (ind head)
(map
(lambda (rest)
(cons head rest))
(permutations (but-kth set ind))))
(iota (length set))
set)]))#とりあえず、こうしました。
#iotaのあたりが私の弱さを表現している感じです。
#append-map-with-indexって無いのか。
#なんとか-with-indexが増やすと際限ないですね。
#なんか思い出してきた。当初は3以下を特別扱いする最適化は無かったんだけど、何かのソルバーのコードを最適化してたときに、これが劇的な効果をあげることに気づいて入れたんじゃなかったかな。で、テストコードの方は最適化前にはちゃんとfold-with-indexのパスを通ってたんだけど、最適化後には通らなくなったと。
#あっ、テストケースのほうは、fold-with-indexが通ります。話をごっちゃにしてすみません。
#テストケースで通らないのは、for-each-with-indexのパスのほうですね。
#*-with-index問題は効率とのトレードオフですね。lazyな言語ならiota相当の無限整数リストを作るのが軽いので、わざわざ*-with-indexバージョンを用意せずとも、ひとつ余分に無限整数リストを渡してやればいいだけですから (つまりkiyokaさんのやり方が素直でよい)
#なるほど。
#ちなみに、Rubyでは with_index系メソッドが増えるのをきらってかEnumerableクラスにwith_indexメソッドがサポートされていて、メソッドチェーンで何にでもくっつけるという方針みたいです。
#でもpermutationsについては、iotaでの整数リスト生成のコストが問題になるような大きなセットだとそもそもpermutationsをeagerに計算するのが非現実的なので、iota使っても構わないと思います (iotaのコストはO(N)で増えるけど、permutations全体のコストはO(N!)で増えるから比べ物にならない)
#まあメソッドチェーンを使えば、-with-indexの部分が .with-indexにかわるだけですからね。Rubyはパッと見を重視する言語(笑)
#ふーむ、Schemeでも「mapを取ってmap-with-index相当のものを返す」関数は書けなくはないかな。
#with-indexという関数かマクロになるんでしょうかね。
#でも、Rubyのような見た目にはならないですね。
#マクロにする必要はないと思いますが、foldとmapで引数のとり方が違うのでそういうのをどう扱うか。
#あーなるほど。
#見た目は、((with-index map) proc lis ...) というふうになるんで倒置になっちゃいますね。Lispらしいといえばらしいけど。
#あっ、それくらいなら許せますね。Lisperだからかもしれませんが...
#うーん。foldとmap両方に使えるようにするには... ちょっと思いつきませんね。修行が必要です。
#そこは難しいと思う。静的型ならwith-indexに渡された関数だけで判断がつくんだけど、動的型だとどうしようもないんで、with-indexに関数の型を何らかの方法で教えてやらないと。ベタには、procとコレクション引数の間に挟まる引数の数を指定してやるとかかなあ。(foldならseedが挟まるので1)
#withIndex :: ([(Int,a)] -> [b]) -> [a] -> [b] のようにすればよいかも。
#おもいつきですが。
#渡す関数を (Int,a) -> b ではなく [(Int,a)] -> [b] にしちゃうってことかな。というかfoldも扱うなら [(Int,a)] -> b を取るようにして withIndex :: ([(Int, a) -> b) -> [a] -> b の方がいい? まだ具体的に思い浮かばないけど。
#あ間違えた。([(Int,a)] -> b) -> [a] -> b
#あーでもそれって、eagerな言語だとあんま嬉しくないんだ。[a]から[(Int,a)]を先に作ってやらないとならないんで。リスト作りおきが許されるならそもそも add-index :: [a] -> [(Int,a)] があれば (map proc (add-index lis)) でも (fold proc seed (add-index lis)) でもokなんだけど、そういう作りおきをしたくないってのが*-with-indexの動機だから。
#((with-index (map$ f)) lis) のような使い方を想定
#してます
#ああそうか > eager だと嬉しくない
#ああ、型シグネチャで会話が進んでいってる...
#高階関数の話では型シグネチャー必須 :)
#必須... ですか。lazyとeagerの条件も必須... なんですよね。
#Coders at Workでサイモンペイトンジョーンズだったかが、設計のほとんどを型シグネチャで行うみたいなこと書いてたのを思い出しました。
#nobsunも多分同じクラスタの人ですね。
#with-indexに渡す高階関数がfold-right系なら作り置きしなくてもよいようにできるかも。これも思いつき
#ああそうか、map も fold も第一引数の関数が1引数関数とは限らないのか。ええーん。
#CPSにするのかな？ gkbr ああ儂にはむずかしそう。
Gauche > Archives > 2011/06/14