Parenist養成ゼミ: 高階関数と無名関数

この記事は、Parenist養成ゼミシリーズの記事である。

今回は、Parenにおいて関数はsymbolやstringと変わらぬただのデータ型の一種であること。したがって、高階関数を定義することもでき、それにより、より高度な抽象化が可能な事について理解することを目的とした。

• func.p

高階関数

Parenにおいて、関数はただのatomの一種であり、他のatom同様に以下のような性質を持つ。

• being writable
• being readable
• being storable
• being constructible at runtime
• being passable as a parameter to a function
• being returnable as the result of a function

このように、他のatomと同様に何も制約がないことをfirst-class objectであるという。

定義より関数はfirst-class objectであるから、関数を引数にとる関数や関数を返す関数を定義することができる。そのような関数のことを高階関数(higher order functions)という。

高階関数を用いると、より抽象度の高い処理を記述することができる。

例えば、listと関数を引数に受け取り、listの各要素に関数を適用したlistを返す関数を%mapは以下のように定義できる。

(function %map (fn lis)
  (if (nil? lis) nil
      (cons (fn (car lis)) (%map fn (cdr lis)))))

これは以下のように用いる。

) (function double (x)
    (* x 2))
double
) (.. 5)
(0 1 2 3 4)
) (%map double (.. 5))
(0 2 4 6 8)

組み込みの高階関数

関数applyは関数と引数となるlistを受け取り適用する。

) (apply + (.. 10))
45

これは、以下の呼び出しと等しい。

(+ 0 1 2 3 4 5 6 7 8 9)

関数partialは、関数と引数の一部を受け取り部分適用した関数を返す。

) (apply (partial = 'a) '(a))
true
) (apply (partial * 1 2 3) '(4 5))
120

関数composeは、関数を複数受け取りそれらの合成関数を返す。

) (begin (<- third (compose car cdr cdr)) (third (.. 10)))
2

関数take-while/drop-whileは関数を受け取り、take/dropを述語が真を返す間適用した結果を返す。

) (take-while (partial < 3) (.. 10))
(0 1 2)
) (drop-while (partial < 3) (.. 10))
(3 4 5 6 7 8 9)

関数mapは関数を受け取り、引数を集合のように扱い写像する。

) (map ++ (.. 10))
(1 2 3 4 5 6 7 8 9 10)

関数countは述語を受け取り、条件を満たす要素数を返す。

) (count even? (.. 10))
5
) (count zero? (.. 10))
1

関数every?/some?/none?は述語をすべて満たす/どれか満たす/どれも満たさないか判定する。

) (every? nil? '(1))
nil
) (some? nil? '(1))
nil
) (none? nil? '(1))
true

) (every? nil? '(1 nil))
nil
) (some? nil? '(1 nil))
true
) (none? nil? '(1 nil))
nil

関数select/rejectは、述語を満たす/満たさないlistを返す。

) (select even? (.. 10))
(0 2 4 6 8)
) (reject even? (.. 10))
(1 3 5 7 9)

関数reduceは引数を左から右に畳み込む。

) (reduce + (.. 10))
45
) (reduce list (.. 10))
(((((((((0 1) 2) 3) 4) 5) 6) 7) 8) 9)

無名関数

関数はfirst-class objectであるから、実行時に生成できる。

special operator fは関数を作成する。特定のsymbolに束縛されていないため、無名関数とも呼ばれる。

(f (args ...) expr ...)

実のところ、functionマクロで定義してきた関数は、指定したsymbolに関数を代入しているだけである。

(function foo () ...)
<=> (<- foo (f () ...))

例えば、先の例では関数doubleを定義することなしに以下のようにして同等の処理が行える。

) (map (f (x) (* x 2)) (.. 5))
(0 2 4 6 8)

パラメーター

関数には以下に示すパラメーターを柔軟に指定できる。

• 必須パラメーター
• オプショナルパラメーター
• レストパラメーター
• キーワードパラメーター

複数のパラメーターを同時に組み合わせることができるが、その場合は上の順番で指定しなければならない。

ただし、レストパラメーターとキーワードパラメーターは同時に指定できない。

必須パラメーター

必須パラメーターは関数呼び出し時に必ず与えなければならない引数である。

関数呼び出し時に必須パラメーターが足りない場合はエラーとなる。

) (function avg2 (x y)
    (/ (+ x y) 2))
) (avg2 2 4)
3

オプショナルパラメーター

オプショナルパラメーターは関数呼び出し時に省略可能な引数である。省略された場合nilが束縛される。

) (function inc (x :opt y)
    (+ x (|| y 1)))
inc
) (inc 3)
4
) (inc 3 2)
5

レストパラメーター

レストパラメーターは束縛されなかった実引数に対応する可変長引数である。対応する実引数がない場合はnilが束縛される。

) (function first-rest (first :rest rest)
    (list first rest))
) (first-rest 1 2 3)
(1 (2 3))
) (first-rest 1)
(1 nil)

キーワードパラメーター

キーワードパラメーターは省略可能な順序を問わない名前付きの引数である。省略された場合はnilが束縛される。

関数呼び出し時は対応するキーワードを指定する。

) (function k1-k2-k3 (:key k1 k2 k3)
    (list k1 k2 k3))
k1-k2-k3
) (k1-k2-k3 :k1 1 :k2 2)
(1 2 nil)
) (k1-k2-k3 :k1 1)
(1 nil nil)
) (k1-k2-k3 :k3 3 :k1 1)
(1 nil 3)

課題

• 付録のfunc.pを作成し、main関数を変更することなしにpassが表示されるようにプログラムを修正せよ。

実行例

$ paren func.p
pass

付録

func.p

; function.

(function %select (fn lis)
  '?)

(function %count (fn lis)
  '?)

(function %every? (fn lis)
  '?)

(function %concat (lis1 lis2)
  '?)

(function pairs (lis)
  ;; use take and drop.
  '?)

(function partition (lis)
  (if (nil? lis) nil
      (let (separator (partial = (car lis)))
        (cons (take-while separator lis)
              (partition (drop-while separator lis))))))

(function repeat (x n)
  '?)

(function compress (lis)
  '?)

(function uncompress (lis)
  '?) ; use pairs and repeat.

(macro test (x y)
  `(if (!= ,x ,y) (raise Error (str "assert failed " (list :expr ',x :evaluated ,x :expected ',y)))))

(function! main (args)
  (test (%select atom? '(1 (2) 3 (4 5))) '(1 3))
  (test (%select cons? '(1 (2) 3 (4 5))) '((2) (4 5)))
  (test (%select even? (.. 5)) '(0 2 4))
  (test (%count atom? (.. 5)) 5)
  (test (%count cons? (.. 5)) 0)
  (test (%count even? (.. 5)) 3)
  (test (%every? even? nil) true)
  (test (%every? even? (.. 10)) nil)
  (test (%every? even? (%select even? (.. 10))) true)
  (test (%concat nil nil) nil)
  (test (%concat (.. 3) nil) (.. 3))
  (test (%concat nil (.. 3)) (.. 3))
  (test (%concat (.. 3) '(3)) (.. 4))
  (test (%concat '(0) (map ++ (.. 3))) (.. 4))
  (test (partition '(a a a b b c c d a)) '((a a a) (b b) (c c) (d) (a)))
  (test (pairs (.. 10)) '((0 1) (2 3) (4 5) (6 7) (8 9)))
  (test (repeat 'a 5) '(a a a a a))
  (test (compress '(a a a b b c c d a)) '(a 3 b 2 c 2 d 1 a 1))
  (test (uncompress '(a 3 b 2 c 2 d 1 a 1)) '(a a a b b c c d a))
  (test (uncompress (compress (.. 3))) (.. 3))
  (write 'pass))