[B! programming][Haskell][deferred] slay-tのブックマーク

slay-t id:slay-t

programmingとHaskellとdeferredに関するslay-tのブックマーク (2)

遅延評価を活用して線形時間でGoogle Code Jam 2014 Round 1AのB問題を解く - tosの日記
公式の解説で，「遅延評価を使ってもできる」と書いてくれなかったので。注意：この記事は，Google Code Jam 2014 Round 1AのB問題 Full Binary Tree についてのネタバレを含みます。この問題は木DPをする典型的な問題であり，公式の解説にもあるように，木を根付き木にした後，頂点でのスコアを，子のスコアのうち大きい方から2つを用いて計算することで解けます。何を根として選ぶかをすべて試すとO(N2)解法となり，すべての根の可能性について同時にDPをする*1とO(N)解法になります。だから，根の選び方によって隣接頂点のうち「親以外が子となる」ので，隣接頂点のスコアのうち大きい方から3つを保存するような構造を持つ――待ってください。もちろん，降順ソートされたスコアのすべてを計算すると，O(N2)時間かかってしまいます。しかし，先頭3つを結果的に計算でき
slay-t 2014/05/07
code

data

google

haskell

algorithm

function

deferred

Programming
リンク
foldlを直す - 純粋関数空間
http://www.well-typed.com/blog/90/ foldlに関するこの記事（英文）が面白かったので、勝手翻訳しました。 foldlなんとかなるといいですね。 foldlを直す foldl 関数は壊れている。壊れているとみんなが知っている。四半世紀近く壊れたままだ。ついにこれを修正する時が来た！今日、私はPrelude.foldlをData.List.foldl'として知られる実装で再定義することを提案する。 foldlは壊れている！既にご存知だとは思うが、念のため… Haskellerが必ずfoldlではなく、foldrやfoldl'を使うように勧めてくることにお気づきだろうか？例えばReal World Haskellでは次のように言っている。 `foldl`のサンクの挙動のため、実アプリではこの関数を使わないようにするのが望ましい。特に問題がない場合でも
slay-t 2014/04/07
list

data

haskell

deferred

Programming
リンク
1