高階関数とは…関数を引数として受け取る関数めちゃくちゃ簡単な例作ってみた↓

(define pow2
  (lambda (x)
    (* x x)
    )
  )
(define eval-func
  (lambda (f x)
    (f x)
    )
  )

eval-funcというのが高階関数で、他のpow2は次の呼び出しで使います。高階関数eval-funcは引数としてfとxを受け、(f x)の結果を返します。 fは括弧で囲まれた一番左なので関数である必要があります。そしてさらに言うとこの括弧の一番左以外にはxの1つしかないので引数を1つ持つある関数をfにしなければなりません。なので引数を一つ受け取って2乗や4乗を返す関数を作りました。次の呼び出しはどちらも一緒の値を返します。

(eval-func pow2 5)
(eval-func (lambda (x) (* x x)) 5)

1行目は1つの引数を受けてその引数を２乗するpos2をeval-funcのfに与えています。２行目はlambdaで即席で作った関数を与えています。どちらも一緒です。

ペア…２つ要素を持つもの
リスト…ペアをつなげて作れる

ペア…consを使って作れる。

(define p (cons 1 2))

こうすると、

上の図のpのほうのようになります。 list関数を使っても似たようなことができますが、形が少し変わります。

(define p2 (list 1 2))

この場合は図のp2のほうのようにペアを二つつかってそれらを連結した形で1と2が格納されます。まあ関数名がlistだけあってリストを作ることを前提にこうなってるんですが。なのでcdrを取り出すとそれぞれ違った結果が返ってきます。 car関数…ペアの１番目の要素を取り出す。 cdr関数…ペアの２番目の要素を取り出す。 pのcdr要素は原始的な2という数字、p2は２番目の要素を持たないペアが出てきます。 p2で2を取ろうと思えば

(car (cdr p2))

とか

(cadr p2))

とする必要があります（２個めの省略記法はある程度までなら定義されてるけど長いと読み返すとき訳わかめになるので１個めのほうが良いかも）。 list関数でやってることは

(cons 1 (cons 2 '()))

と同じ。 '()はnullのようなもの。

で、最初の高階関数とリストの連携技みたいなこともできるので両者は共に便利ですよね。みたいな。さっきのp2を１から７までの奇数に変えます。また引数lで受け取ったリストのcar要素をprocess関数で評価した結果に変えたリストを返す高階関数my-mapを作ります。

(define my-map
  (lambda (process l)
    (if (null? l)
        '()
        (cons (process (car l)) (my-map process (cdr l)))
        )
    )
  )

cons関数でペアを作る時そのcar要素をｌのcar要素をprocessで評価したしたものにします。またcdr要素については自信にlの残りを与えて呼び出すことでリストを形成します。次で呼び出します。

p2(my-map (lambda (x) (* x 3)) p2)

my-map関数の呼び出し部分はp2の各値が3倍になったリストが返ってきていることが確認できるはずです。当然ですが関数の実行前後でp2の値は変わりません。consで新たにペアを作って全く新しいリストが作られるからです。なのでこの値を今後何度も使う場合は次のようにdefineしとけば便利かもしれません。

(define p3 (my-map (lambda (x) (* x 3)) p2))

mapを少し応用して条件にマッチした要素のみで構成された新たなリストを作る関数my-filterも自作できます。今回は高階関数の引数processには述語を与えます。あえてifのネストで書きました。

(define my-filter  (lambda (process l)
    (if (null? l)
        '()
        (if (process (car l))
            (cons (car l) (my-filter process (cdr l)))
            (my-filter process (cdr l))
            )
        )
    )
  )

例えば次のように実行すると5以上の要素だけで作られた新たなリストを返します。

(my-filter (lambda (x) (<= 5 x)) p2)

もっともmapやfilterなどの関数はもともとあるのでわざわざ作る必要も無いのですが。

schemeまとめ（5:高階関数＆リスト）