「関数プログラミング」を含む日記

2008-12-31

■http://anond.hatelabo.jp/20081231050338

その辺のメモリポインタと関数ポインタのあいまいさがCのポインタの面白いところだと思うよ？

よくわからんが何が曖昧なんだろう。区別されているでしょ。

クラックされるから関数ポインタを使わないというのも初耳。セキュリティ関係ない。だいいちダブルディスパッチ、スレッドの開始、クイックソートの比較関数、C++の仮想関数の実装、最近流行の関数プログラミング等、関数ポインタは普通にユビキタスな存在でしょ。

実行時に自分のコードをデータとして扱うことは楽しい、そういうことをやるのにCが使える(というかCとアセンブラくらいしかない)、というのはそうだけど

Permalink | トラックバック(1) | 09:38

2007-11-10

■関数プログラミングにおけるFizzBuzz問題

いくつか考えてみた

(問1)高階関数と再帰関数を必ず使って数値を要素とするリストの要素の総和を求める関数を書け。ただし高階関数を使うという要件と再帰関数を使うという要件は同じ関数で満たしてもよい。

(問2)二つの引数をとり二つのうち大きいほうを返す関数と高階関数、再帰関数をつかって数値のリストの最大値を求める関数を書け。ただし高階関数を使うという要件と再帰関数を使うという要件は同じ関数で満たしてもよい。

というのは簡単すぎるか？簡単すぎるなら

(問3)高階関数と再帰関数を必ず使ってある数値に5を足し、10かけて2で割った数を求める関数を書け。ただし高階関数を使うという要件と再帰関数を使うという要件は同じ関数で満たしてもよい。

こっちの方がいいかな。でもトリッキーすぎる気もする。

一応問題を出したので、SchemeとPythonで自分で想定している答えを書いておいた。はてなではSchemeが人気のようなので、あまり知らなかったけど関数言語ではSchemeで書いておいた。Pythonで書くのはSchemeだけだとわかりにくいので、なにかスクリプト言語で書いておこうと思ったから。Rubyの方が人気なので、はじめはRubyで書こうと思ったけど挫折した。だれかRubyで書いてくれないかな・・・。コードオブジェクトってなによ。というか関数はオブジェクトなのに引数にできないの？なんで？（以下疑問と愚痴の嵐なので略）Perlは古株が多くてユーザー数も多そうだけど、・・・その・・・無理です・・・。あの言語仕様はやる気がしない。ぶっちゃけ理解できない。Pythonを知らないひとは多そうだけど、知らなくてもSchemeよりは感じは掴めると思うのでPythonでも書いておくことにした。

Scheme編

http://anond.hatelabo.jp/20071110215936

Python編

http://anond.hatelabo.jp/20071110220132

これで大部分のひとがこの問題に興味をもたなくて解答するひとがいなくても、興味を持ったひとは安心だね！

追記：

問3で次のは無しとしておきたい。

Scheme

(define continuous-apply
    (lambda (lst obj)
        (cond
            ((null? lst)
                obj)
            (else
                (continuous-apply (cdr lst) ((car lst) obj))))))

(define plus5
    (lambda (num)
        (+ num 5)))

(define times10
    (lambda (num)
        (* num 10)))

(define divide2
    (lambda (num)
        (/ num 2)))

(define plus5-times10-divide2
    (lambda (num)
        (continuous-apply (list plus5 times10 divide2) num)))

(plus5-times10-divide2 2)

Python

def continuousApply(lst, obj):
    if lst:
        return continuousApply(lst[1:], lst[0](obj))
    else:
        return obj

def plus5(num):
    return num + 5

def times10(num):
    return num * 10

def divide2(num):
    return num / 2

def plus5_times10_divide2(num):
    return continuousApply([plus5, times10, divide2], 2)

plus5_times10_divide2(2)

Permalink | トラックバック(1) | 22:18

■Schemeによる解答

あくまで自分でこう答えるという話。

(問1)

(define fold-left
    (lambda (func obj lst)
        (cond
            ((null? lst)
                obj)
            (else
                (fold-left func (func obj (car lst)) (cdr lst))))))

(define my-sum
    (lambda (lst)
        (fold-left + (car lst) (cdr lst))))

・例

(my-sum '(1 2 3 4 5 6 7 8 9 10))

(問2)

(define fold-left
    (lambda (func obj lst)
        (cond
            ((null? lst)
                obj)
            (else
                (fold-left func (func obj (car lst)) (cdr lst))))))

(define large
    (lambda (x y)
        (cond
            ((>= x y)
                x)
            (else
                y))))

(define my-max
    (lambda (lst)
        (fold-left large (car lst) (cdr lst))))

・例

(my-max '(58 90 1 2 4 3 100))

(問3)

(define fold-right
    (lambda (func lst obj)
        (cond
            ((null? lst)
                obj)
            (else
                (func (car lst) (fold-right func (cdr lst) obj))))))

(define my-apply
    (lambda (func obj)
        (func obj)))

(define plus5
    (lambda (num)
        (+ num 5)))

(define times10
    (lambda (num)
        (* num 10)))

(define divide2
    (lambda (num)
        (/ num 2)))

(define plus5-times10-divide2
    (lambda (num)
        (let ((lst (list plus5 times10 divide2)))
            (fold-right my-apply (reverse lst) num))))

・例

(plus5-times10-divide2 5)

全部畳み込み関数を使っているのは、はじめ使い道がないと思ってたのにかなり使い道があることがわかったので、それを示したかったから。あとmap 関数あたりはほかの言語でもあるから、すぐに思いつくだろうし。

というか最後のやつは手続きを抽象化することでリストの形で扱えるようにしているから、関数プログラミングでは重要だと思う。関数プログラミングの肝は計算によって手続きを含めたすべて表すことができることだと思っている。その例だと思うんだけどね。例えばSchemeなら上記の答えを応用して、似たような「手続き」を生み出す関数を作ることができる。

(define make-proceduce
    (lambda (fst . rest)
        (let ((lst (cons fst rest)))
            (lambda (num)
                (fold-right my-apply (reverse lst) num)))))

これを使うと次のようにできる。

(define divide2-plus5-times10
    (make-proceduce divide2 plus5 times10))

(divide2-plus5-times10 2)

(define divide2-times10-plus5
    (make-proceduce divide2 times10 plus5))

(divide2-times10-plus5 2)

関数合成がつかえるならそっちのほうが楽だけど、リストという形で「手続き」をつくり出していることがわかるだろうか？手続きをリストで操作できるのだ。こういうのが関数プログラミングの肝だと勝手に思っている。

こうやってくると型推論や多相型の重要性もわかると思うんだよ。上記のようなことはPythonでもできる。でも高階関数はつかいすぎるとわかりにくい。どっかにバグが入ってくるかもしれない。それを機械的に防ぐのが型推論。型という観点から型推論でおかしいところを探し出してくれる。それならC言語でもいいのではないかという人もいるかもしれない。だがC言語は融通が利かない。例えばapply関数にしても引数の型が数値なら数値、文字なら文字と決まっている必要がある。だから数値に向けにapply関数を作っても文字には使えない。こうした型のデメリットをなくす一方、そのメリットを享受するためにあるのが多相型。これによってapply関数やmap 関数を一般的に作ることができ、型のメリットを享受しながらデメリットをなくすことができる。このように関数で手続きなんかを抽象化するときに型推論や多相型があると便利なのだ。

Permalink | トラックバック(1) | 21:59

2007-11-09

■Pythonではなぜ string.len() でなく len() なのか？

http://anond.hatelabo.jp/20071021143442

その理由は知らないが、なければ作ればいいじゃないか。

class MyString(str):
    def length(self):
        return len(self)

というクラスを作って

string = MyString("Hello world")
print string.count("o"), string.length()

とRubyライクにやれば

2 11

とでるよ。え、リストもlist.length()が使いたいって？それも簡単。

class MyList(list):
    def length(self):
        return len(self)

l = MyList([1, 2, 3, 4, 5, 6])
l.length()

6

きちんと他のメソッドも使えるよ。

l[1:]

[2, 3, 4, 5, 6]

l.reverse()
l

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

ね。簡単でしょ。

Pythonは仕組みが統一されているものが多いので、いじりやすいのですよ。上の例のやつは組み込みのクラスオブジェクトとユーザー定義のクラスオブジェクトがおおむね統一されているからこそ簡単にできる。他にも関数なんかもほかのオブジェクトと同じオブジェクトなので、高階関数なんてもの簡単に作ることができて関数プログラミングぽくできる。例えば今はなきapply関数なんかは

def myApply(func, *args):
    return func.__call__(*args)

と定義できる。実際に

def sumUpThree(num1, num2, num3):
    return num1 + num2 + num3

でためしてみる。

myApply(sumUpThree, 1, 2, 3)

結果はちゃんと

6

とでる。将来廃止されそうなmap 関数も簡単に定義できる。他にも複数の引数をもつ関数の部分適用のようなことを行う関数も次のように簡単に定義できる。

def partial(func, *oldArgs):
    def wrapper(*newArgs):
        return func.__call__(*(oldArgs + newArgs))
    return wrapper

sumUpThree関数でテストすると

sum_1 = partial(sumUpThree, 1)
sum_1(2, 3)

6

sum_1_5 = partial(sum_1, 5)
sum_1_5(9)

15

sum_10_20 = partial(sumUpThree, 10, 20)
sum_10_20(30)

60

こういう風に高階関数が簡単にできるのは関数がオブジェクトで関数の実行とはメソッドの呼び出しにすぎないからだ。以上のように組み込みオブジェクトとユーザー定義オブジェクトの差があまりないことや関数もオブジェクトであることに見られるようにPythonは仕組みが統一されていてシンプルだ。そのためひとつのことがわかれば他のこともわかることが多いし、簡単にいじることもできる。

だからなければpythonをいじればいいと思うよ。

最後にラムダ式信者のためにpartialをラムダ式を使って書いておく。

def partial(func, *oldArgs):
    return lambda *newArgs:func.__call__(*(oldArgs + newArgs))

Pythonはラムダ式がだめだといわれているが、こんな風にかけたとして何がうれしいというのだ。

Permalink | トラックバック(2) | 11:10

- 転職ならen
- 派遣ならen