はじめに
少し昔の記事になりますが、こちらの記事で「関数型プログラミング」について紹介されています。
そこではお題として、「唐揚げ弁当をつまみ食いする」の実装があげられていました。ここにそれを再掲させていただくと、
課題：
唐揚げ弁当がいくつかあるとします。それぞれ唐揚げが複数入っています。
この中からｘ個の唐揚げをつまみ食いするプログラムを作りましょう。
つまみ食いはバレないようにするために、
その時点で最も唐揚げ数が多いお弁当から取るという仕様にします。
となります。
すでに手続き型言語Pascal での実装と、動的型付関数型言語Elixir での実装をしてみたのですが、なんとなく、もうちょっと他のプログラミング手法と比較し見たくなり、論理型プログラミング言語と呼ばれるPrologでの実装を試してみました。
実装
まずは、お弁当をどう表すかですが、Prologではデータタイプがいきなり作れてしまうので、
bentoo('唐揚げ',10)
のように直接表すことにします。そして、つまみ食いを繰り返していくのですが、0回目の状態(まだつまみ食いをしていない状態)をorder(0,L)として次のように定義しました。
order(0,L) :- L = [bentoo('唐揚げ',10),bentoo('唐揚げ',8),bentoo('唐揚げ',6)].
これで、1回つまみ食いした状態、2回つまみ食いした状態を定義していけばいいのですが、これは次のように再帰的に定義します。
order(N,R) :- N1 is N - 1, order(N1,L), selectMaxBentoo(L,_,N2),
tsumamigui(L,N2,R).
つまり、つまみ食いN回目のお弁当のリストは、つまみ食いN-1回目のお弁当リストに対して、一番唐揚げのたくさんあるお弁当を選んで(selectMaxBentoo)、それからつまみ食い(tsumamigui)したもの、という定義です。
次に、お弁当と、お弁当のリストを表示する部分を次のように実装しました。
showBentoo(bentoo(D,K)) :- print(D), print(K), print('個'), nl.
showOrder([]) :- true.
showOrder([X|L]) :- showBentoo(X), showOrder(L).
あと、必要なのは、selectMaxBentooとtsumamiguiですね。
これらは、それぞれ次のように定義しました。
selectMaxBentoo([X],X,0).
selectMaxBentoo([bentoo(D,K)|L],X,N) :- selectMaxBentoo(L,bentoo(D1,K1),N1),
(K >= K1 -> X = bentoo(D,K), N = 0; X = bentoo(D1,K1), N is N1 + 1).
引数は、お弁当のリスト、唐揚げが最大のお弁当、唐揚げが最大のお弁当のインデックスです。
ひとつ目の式は、お弁当がひとつしかない時で、当然、唐揚げが最大のお弁当はそのただ一つのお弁当で、インデックスは0です。
二つ目の式は、再帰的に定義していて、リストの最初のお弁当と、残りのお弁当の中で唐揚げが最大のお弁当を比較して、多いほうを全体で唐揚げ最大のお弁当としています。インデックスは、リストの最初のお弁当が最大のときは0に、そうでなければ、インデックスを一つ増やします。
tsumamigui([bentoo(D,K)|L],N,[bentoo(D1,K1)|R]) :-
N = 0 -> D1 = D, K1 is K - 1, L = R; D1 = D, K1 = K, N1 is N - 1, tsumamigui(L,N1,R).
引数は、お弁当のリスト、つまみ食いするお弁当のインデックス、つまみ食い後のお弁当のリストです。
これも再帰的に定義していて、N=0ならリストの最初のお弁当からつまみ喰いをし、そうでないなら、残りの中からN-1番目のお弁当をつまみ食いです。
最後に、結果を表示します。
:- forall(between(1,5,I), (order(I,L), print('-----'), nl, showOrder(L))).
コード全体では
order(0,L) :- L = [bentoo('唐揚げ',8),bentoo('唐揚げ',6),bentoo('唐揚げ',7)].
order(N,R) :- N1 is N - 1, order(N1,L), selectMaxBentoo(L,_,N2), tsumamigui(L,N2,R).
showBentoo(bentoo(D,K)) :- print(D), print(K), print('個'), nl.
showOrder([]) :- true.
showOrder([X|L]) :- showBentoo(X), showOrder(L).
selectMaxBentoo([X],X,0).
selectMaxBentoo([bentoo(D,K)|L],X,N) :- selectMaxBentoo(L,bentoo(D1,K1),N1),
(K >= K1 -> X = bentoo(D,K), N = 0; X = bentoo(D1,K1), N is N1 + 1).
tsumamigui([bentoo(D,K)|L],N,[bentoo(D1,K1)|R]) :-
N = 0 -> D1 = D, K1 is K - 1, L = R; D1 = D, K1 = K, N1 is N - 1, tsumamigui(L,N1,R).
:- forall(between(1,5,I), (order(I,L), print('-----'), nl, showOrder(L))).
:- halt.
となります。コードだけ見ると、関数型と似ているような、似ていないような、、。
実行結果は
-----
唐揚げ9個
唐揚げ8個
唐揚げ6個
-----
唐揚げ8個
唐揚げ8個
唐揚げ6個
-----
唐揚げ7個
唐揚げ8個
唐揚げ6個
-----
唐揚げ7個
唐揚げ7個
唐揚げ6個
-----
唐揚げ6個
唐揚げ7個
唐揚げ6個
感想
Prologは、いろいろちょっと他のプログラミング言語と違う感じで、勝手が分からず、どういう風に進めていけば良いのか悩みました。また、N1 is N - 1とせずにN1 = N - 1としてエラーになってしまったり、、、。慣れるまで時間がかかりそうです。
論理型プログラミングは、関数型プログラミングに似ているような気もするのですが、高階関数を使っているわけではなくて、論理を定義しているだけで問題が解けてしまうというのが、なんだか面白いと思いました。