星田さんの記事に対するコメント。
あ〜、妙なトコにハマったねぇ。
っつーかゴメン。僕もウッカリしてた。
最初に言っておくけど、
Foldの理解が試されるときが来たのだ！とりあえずは数字はこう動くんだろうな・・というのを考えてみる。右にカッコが伸びていくので新たにリストから読み込まれたものをFirstと比べて小さかったら入れ替える・・と。簡単じゃない？（と、この時は思ってました）
いや、その発想は正しい。
星田さんは全然違うトコでハマってたんだ。
まず正解のコードを見せよう。
これが正解だ。
コードの違いが分かる?そう、fold-leftじゃなくってfoldを使うんだ。
実はGaucheに於いてはfold ≠ fold-leftなんだ。
従って、foldl(Racket) ≒ fold(Gauche)で、foldr(Racket) ≒ fold-right(Gauche) なんだけど、Gaucheのfold-leftは全くの別物なんだ。
上のコードは単にfold-rightをfoldに置き換えるだけ、で達成出来る。
返り値のcdrの順序が違うが、これは気にしなくていい。「最短を分離」(して返り値のリストの先頭に置く)するのが関数saitan_wo_bunriの機能なんで、cdrの順序は関係ない。carが最短、ってのが分かれば良いだけ、だからだ。
(言い換えると、cdrの順序が違うのは、それこそ引数のリストが左から処理されるか右から処理されるか、の違いのせいだ。)
一方、fold-leftは引数の計算順序が違う。
詳しい事はこのページで川合史朗さん自らが解説を書いている。
平たく言うと、単純には、foldとfold-leftは次のような違いがある。
(define (fold op z lst)
(if (null? lst)
z
(fold op (op (car lst) z) (cdr lst))))
(define (fold-left op z lst)
(if (null? lst)
z
(fold-left op (op z (car lst)) (cdr lst))))
再帰部分でのopの引数適用順序が違うんだ。
従って、foldを使って以下のように書けば
reverseを作る事が可能なんだけど、fold-leftは想定しない結果を返す。
これが原因で、fold-leftが受け取るmatch-lambda*の引数の順序が逆にならないとマクロ展開が思った通りに行かないんだ(※2)。
スマン。ウッカリしてた。
※1: Racketのfoldl及びfoldrは、受け取った可変長のリスト引数が全部同じ長さでないとならない、と言った縛りがある。
一方、Gaucheのfold及びfold-rightはそう言った縛りがなく、一番短いリストが消費された時点で、計算が終了する。
※2: なお、じゃあOCamlのList.fold_leftが一体どっちなんだ、って問題がある。
OCamlのリファレンスマニュアルによると、List.fold_leftの定義は、
と書かれてて、定義を読む限り、引数の適用順序はまさしく、
(define (fold-left f init lst)
(if (null? lst)
init
(fold-left f (f init (car lst)) (cdr lst))))
となってて、Gaucheのfold-leftの定義と同じだ。
と言う事は、OCamlのfold-left使用のコードをSchemeに移植・改造する際には、fold-leftをそのまま使うべきか、それともfoldを使うべきか、ちと考えなければならない、と言う事だ。
今まで問題にならなかったのは、
- 使用教科書の傾向で、List.fold_rightの使用率の方が高かった。
- OCamlのList.fold_leftは引数リストを1つしか取らない。
- List.fold_leftに適用する関数が、川合史朗さんが記述してるように、足し算や掛け算のような「可換な演算」を使ってる例が多かったから。
だろう。僕もこの辺すっぽ抜けてて、全く意識せんかったんで、まさしくウッカリしてたんだ。
なお、川合史朗さんが書いてる通り、Lisp以降の後発の関数型言語ではGaucheで書かれてるfold-leftがフツーで、むしろSchemeで広く使われてるfoldは実装されてない模様。HaskellもOCamlと同様のfold-leftがfoldlとして提供されている。
