2010/09/27

unfold の cons が指定できても良いような

そんなことを思ったのでメモがてら。


追記

@valvallow (define(accrec-right p f g c s :optional(t'()))(let l((s s)(a t))(if(p s)a(l(g s)(c(f s)a))))) unfoldとunfold-rightの最後の引数は意味が違いますよ
(define (accrec-right p f g c s :optional(t'()))
   (let l ((s s)(a t))
     (if (p s)
         a
         (l(g s)(c (f s) a)))))

(accrec-right null? car cdr cons '(1 2 3 4 5) '(0))
;; (5 4 3 2 1 0)

このオプション引数の指定のやり方、知りませんでした。。
それに、unfold、unfold-right の引数も確認しました。
ありがとうございました!!

追記2

これは Hylomorphism になるのかなあ: 「unfold の cons が指定できても良いような」 http://valvallow.blogspot.com/2010/09/unfold-cons.html
ヒロモーフィズム?ハイロモーフィズム?何と読むんでしょうか。。初めて聞きました。
意味はわかりませんが、
「アナモルフィズム」(anamorphism)
「アポモルフィズム」(apomorphism)
とかいった言葉は srfi-1 のドキュメントで目にしたことがあります。

追記3

leque さんのコメントより。ありがとうございます!
『関数プログラミングの楽しみ』ではリストに対する hylomorphism を次のような感じで定義しています。
(define (hylo f e p g h seed)
  (fold-right f e (unfold p g h seed)))

(define (fact n)
  (hylo * 1 (cut = <> 0) values (cut - <> 1) n))
おお。なんかカッコイイ!

こんな感じでも良いのかな。
(define (fact n)
  (hylo * 1 zero? identity (lambda (n)
                             (- n 1)) n))

(define (fact n)
  (fold * 1 (unfold zero? identity (cut - <> 1) n)))


プログラミングGauche

2 件のコメント:

  1. 自分も『関数プログラミングの楽しみ』で少し読んだ程度できちんと理解はしていないのですが、
    unfold をリスト以外にも汎化したものを anamorphism、
    同様に fold を汎化したものを catamorphism と言い、
    さらに、 anamorphism で展開して catamorphism で畳み込む操作を hylomorphism と呼ぶそうです。
    リストで言うと、 catamorphism は cons を二引き数関数で置き換えたものになるので
    unfold の cons を指定できるようにして terminal-fun で fold の knil を返せば
    hylomophism っぽいのかなあと思ったのでした。
    『関数プログラミングの楽しみ』ではリストに対する hylomorphism を次のような感じで定義しています。
    (define (hylo f e p g h seed)
    (fold-right f e (unfold p g h seed)))

    (define (fact n)
    (hylo * 1 (cut = <> 0) values (cut - <> 1) n))

    返信削除
  2. anamorphism, catamorphism, hylomorphism これだけで混乱しますね^^;
    最後の hylo 関数、なんだかおもしろいですね!行って帰ってくるような。。values で少し悩みましたが identity でも良さそうですね!

    返信削除