直感が外れた問題

SICPの問題1.41です。

引数として一引数の手続きを取り，受け取った手続きを二回作用させる手続きを返す手続きdoubleを定義せよ．例えばincが引数に1を足す手続きとすれば，(double inc)は2を足す手続きとなる。

(((double (double double)) inc) 5)

はどういう値を返すか．

プログラムは簡単。

(define (double f)
  (lambda (x) (f (f x))))

(define (inc n)
  (+ n 1))

(((double (double double)) inc) 5)

プログラムを追うのが面倒だったので返す値を勘で予想したら外れました。「4回適用する」という作業を行って、さらに「4回適用する」という動きになるというのを読み取れませんでした。

面白かったのでPerlでも書いてみました。

use strict;
use warnings;

sub double ($) {
    my $f = shift;
    sub { $f->($f->($_[0])); };
}

sub inc {
    $_[0] + 1;
}

print +(double (double \&double))->(\&inc)->(5), "\n";

そこそこきれいに書けますね。

最後はこれでも動きます。

print +(double double \&double)->(\&inc)->(5), "\n";