sh1.2 pyblosxom

• 404 Blog Not Found:たらいを回すならHaskell
• はこべにっき# - Pythonでもわりとたらい回せそう？

このメモ化(Memoize)の話、そういえば去年の夏くらいにはやったなー。 当時はもひとつ理解できんかったけど。

taks = {}
def tak (x, y, z):
    global taks
    if x <= y:
        return y
    else:
        if not taks.has_key((x,y,z)):
            taks[(x,y,z)] = tak(tak(x - 1, y, z),
                                tak(y - 1, z, x),
                                tak(z - 1, x, y))
        return taks[(x,y,z)

を見てやっとどういう概念か理解できた。まぁ実現方法は色々あるみたいだけど。 で、一言で言うと、:

同じ引数を渡した場合には必ず同じ返値を返す関数(純粋関数)の場合、毎回時間の
掛かる演算をするのではなくて計算結果をキャッシュ(メモ)しておいて再利用
しましょう

ということなんだね。

以下は、今回メモ化を理解する際に参考にしたエントリです。

• Memoise
• [結] 2005年8月 - 結城浩の日記: Perl版の「メモ化(memoization), 再帰関数定義関数, 最小不動点」
• Pythonでメモ化 @ NISHIO HIROKAZU # Archived COREBlog

class Memorize:
    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        if self.cache.has_key(args):
            return self.cache[args]

        result = self.func(*args)
        self.cache[args] = result
        return result

fib = Memorize(fib)
print fib(5)

• Be Cloudy or Clear?: memoize with decorator

 1| def memoize(func):
 2|     cache = {}
 3|     def cached_func(*args):
 4|         if cache.has_key(args):
 5|             return cache[args]
 6|         result = func(*args)
 7|         cache[args] = result
 8|         return result
 9|     return cached_func
10|
11| @memoize
12| def fib(n):
13|     print "fib(%d) was called." % n
14|     if n == 0 or n == 1:
15|         return 1
16|     else:
17|         return fib(n - 1) + fib(n - 2)
18|
19| print fib(5)
20| print fib(8)

• ASPN : Python Cookbook : Cache decorator in python 2.4

まだ「ふつうのHaskell」を読み終わってないのに、昨日本屋に寄ったら 「入門Haskell」が売ってたので、思わず買ってしまった。

入門Haskell―はじめて学ぶ関数型言語 ASIN: 4839919623

• 404 Blog Not Found:ふつうくさく、汗臭くないHaskell本

にあった、

「入門Haskell」にあって「ふつうのHaskellプログラミング」に(足り)ないのはなにか?

愛、である。

が気になったので。

最初のほうだけぱらぱら読んだけどさすがに一番最初にこちらを読んでたら わけわからんかっただろうな。ちゃんと読むのはふつうのHaskellを読み終わってから。

• fgrep

  むーしばらく考えたんだけど、高階関数がまだちゃんと使いこなせない。 手続き型の考え方からまだ抜け出れていないようだ。

• 演習問題1: 行単位でソートするsortコマンド

-- sort
import List

main = do cs <- getContents
          putStr $ dosort cs

dosort cs = unlines $ sort $ lines cs

• 演習問題2: 同じ行が連続していたら1行にまとめるuniqコマンド

-- uniq
import List

main = do cs <- getContents
          putStr $ uniq cs

uniq cs = unlines $ map head $ group $ lines cs

• List.group

  同じ値は、連続していないとまとめてくれないようだ:

  Prelude> map head $ List.group [1,2,2,3,4,5,5,1]
  [1,2,3,4,5,1]
  

• 演習問題の解答について

  あれ？コマンド間を「.」でつなぐとか、「=<<」とかまだやってないような 記号を使って解答書かれてますけど？なんでだ？

• 高階関数

  mapとかの第一引数で渡す関数が引数を2つとか取るときには関数と第一引数 を括弧で括って指定すれば良い。( haskell - 結城浩のHaskell日記 )

Prelude> map (replicate 3) ["OK","GJ"]
[["OK","OK","OK"],["GJ","GJ","GJ"]]

• モジュールのimport

  インタープリタ(ghci)では、「import hogehoge」というのはできないようで List.tailsのように「使いたいモジュール.関数」としてやれば良い

• head: carと同じ

• tail: cdrと同じ

• List

  • List.tails [1,2,3,4,5]:

    [[1,2,3,4,5],[2,3,4,5],[3,4,5,],[4,5],[5],[]]
    

  • List.isPrefixOf

    「`」で括ると中置演算子にできるらしいが、別にわざわざ中置演算子に しなくても、前置演算子のままでいいんじゃない？:

    Prelude> map (List.isPrefixOf "ef") $ List.tails "abcdef"
    [False,False,False,False,True,False,False]
    
    Prelude> any (List.isPrefixOf "ef") $ List.tails "abcdef"
    True
    

まだfgrepを自分で書くとこまでいけてないけど、眠いので今日はここまで。

• 文字列は文字のリストである

['s','t','r','i','n','g'] ⇒ "string"
['c']                     ⇒ "c"

• concat :: [[a]] -> [a]

  リストのリストをリストに連結してリストにする

concat [['T','h','i','s',' '], ['i','s',' '],['a',' ','p','e','n']]
⇒ ['T','h','i','s',' ','i','s',' ','a',' ','p','e','n']
⇒ "This is a pen"

• リスト3.5の例題

  定数定義「tabStop = 8」を「TabStop = 8」ってしたら "Not in scope: data constructor 'TabStop'"って表示されてエラーになった。 大文字で始まると別の使い方になるのかな？

• 演習問題: aをAに、Aをaに変更するプログラム。

  最初に書いたのがこれ。

-- swapa 1
main = do cs <- getContents
          putStr $ swapa cs

swapa cs = concatMap doswapa cs
doswapa 'a' = "A"
doswapa 'A' = "a"
doswapa c = [c]

一応動く、でも冗長だった。わざわざ文字列にしてconcatする必要がなかった。 「map doswapa cs」の返値は、[Char]になるからそのままで文字列になるから 単に下のようにしたら良かった。

-- swapa 2
main = do cs <- getContents
          putStr $ swapa cs

swapa cs = map doswapa cs

doswapa 'a' = 'A'
doswapa 'A' = 'a'
doswapa c = c

ここまで読んだ印象は、型定義の厳しいLispって感じかな。モナドまではまだ遠い。