Haskellでメモ化を行うもう一つの方法 - 純粋関数型雑記帳
はじめに Haskell で動的計画法を書くための3つの方針 - tosの日記 これを読んで、私もちょっと前にHaskellでメモ化をやる方法を考えていたことを思い出したので、書いてみることにします。 Haskellでのメモ化は、私のかなり昔の駄文(リアルにびっくりするほど駄文なのでご注意。メモ化の綴りも間違ってます)や、このあたりに日本語の文章があります。 これらのページでのメモ化実現方針は、1. 計算済み値を保持するテーブルをMapなどを用いて用意する 2. そのテーブルを副作用を用いて更新する、というものになっています。なるほど、これは手続き型言語との対比でとても直接的な実装です。しかし、テーブルを更新するために関数全体がモナドになってしまったりして、あまり使い勝手が良くなさそうです。モナドであることを悟らせないために、演算子をモナド化したり、あるいはモナドじゃなくするためにunsa
fib.coffee
fib.coffee �2���U sys = require('sys') crypto = require('crypto') key = (values) -> sha1 = crypto.createHash('sha1') sha1.update values.join('-') sha1.digest('hex') memoize = (f, memo = {} ) -> (args...) -> memo[k = key(args)] or memo[k] = f args... fib = (n) -> if n < 2 then n else fib(n-1) + fib(n-2) fib = memoize(fib) sys.p fib 10 sys.p fib 55 # cannot calculate without memo
2010-12-17
この記事はHaskell Advent Calendar jp 2010のために書いたものです． 「n個の対応する括弧のパターン」（http://d.hatena.ne.jp/ymotongpoo/20101209/1291879286）についてあれこれを徒然に考えてみました． 再帰で考える まずはパターン数を数えることにしましょう．この手の問題はまずは再帰で考えるのが基本です． m個のカッコ（開き括弧）とn個コッカ（閉じ括弧）を並べるのであるが，であり，並べる途中においてもコッカの数がカッコの数を越えることがないようにするものとします．このときの並べ方の数を kakoka (m,n) としましょう．この kakoka (m,n) を構成できれば，n組の対応する括弧を含む列の数は parenseq n = kakoka (n,n) というわけです． さて，この kakoka を考える最もシ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
