Functional Programming

●問題76

andalso, orelse, not を用いて排他的論理和を求める関数 xor(p, q) を定義してください。

val xor = fn : bool * bool -> bool

- xor(true, true);
val it = false : bool
- xor(true, false);
val it = true : bool
- xor(false, true);
val it = true : bool
- xor(false, false);
val it = false : bool

解答

●問題77

2 つの真偽値 p, q を与えたとき、次に示すような真偽値 s, c を出力する関数 half_adder(p, q) を定義してください。s, c はタプルで返すものとします。

val half_adder = fn : bool * bool -> bool * bool

- half_adder(false, false);
val it = (false,false) : bool * bool
- half_adder(true, false);
val it = (true,false) : bool * bool
- half_adder(false, true);
val it = (true,false) : bool * bool
- half_adder(true, true);
val it = (false,true) : bool * bool

解答

●問題78

3 つの真偽値 p, q, r を与えたとき、次に示すような真偽値 s, c を出力する関数 full_adder(p, q, r) を定義してください。s, c はタプルで返すものとします。

val full_adder = fn : bool * bool * bool -> bool * bool

- full_adder(false, false, false);
val it = (false,false) : bool * bool
- full_adder(true, false, false);
val it = (true,false) : bool * bool
- full_adder(true, true, false);
val it = (false,true) : bool * bool
- full_adder(true, true, true);
val it = (true,true) : bool * bool

解答

●問題79

true, false とリストで n ビットの無符号整数を表すことにします。これを uint と呼ぶことにしましょう。たとえば、0 と 255 を 8 桁の unit で表すと次のようになります。

       MSB                                         LSB
  0 : (false false false false false false false false)
255 : (true  true  true  true  true  true  true  true)

0 以上の整数値 n を m 桁の uint に変換する関数 int_to_uint(n, m) と、uint を整数値に変換する関数 uint_to_int(x) を定義してください。

val int_to_uint = fn : int * int -> bool list
val uint_to_int = fn : bool list -> int

- int_to_uint(0, 8);
val it = [false,false,false,false,false,false,false,false] : bool list
- int_to_uint(127, 8);
val it = [false,true,true,true,true,true,true,true] : bool list
- int_to_uint(128, 8);
val it = [true,false,false,false,false,false,false,false] : bool list
- int_to_uint(255, 8);
val it = [true,true,true,true,true,true,true,true] : bool list

- uint_to_int([true, true, true, true]);
val it = 15 : int
- uint_to_int([true, false, false, false]);
val it = 8 : int
- uint_to_int([false, false, true, true]);
val it = 3 : int
- uint_to_int([false, false, false, false]);
val it = 0 : int

解答

●問題80

uint で論理演算を行う関数 uint_and, uint_or, uint_xor, uint_not を定義してください。

val uint_and = fn : bool list * bool list -> bool list
val uint_or = fn : bool list * bool list -> bool list
val uint_xor = fn : bool list * bool list -> bool list
val uint_not = fn : bool list -> bool list

- uint_and([false, false, true, true], [false, true, false, true]);
val it = [false,false,false,true] : bool list
- uint_or([false, false, true, true], [false, true, false, true]);
val it = [false,true,true,true] : bool list
- uint_xor([false, false, true, true], [false, true, false, true]);
val it = [false,true,true,false] : bool list
- uint_not([true, false, true, false]);
val it = [false,true,false,true] : bool list

解答

●問題81

2 つの uint を加算する関数 uint_add(x, y) を定義してください。uint_add はタプルを返します。桁あふれが生じた場合、2 番目の返り値は true になります。なお、x, y の桁は同じものとします。

val uint_add = fn : bool list * bool list -> bool list * bool

- uint_add([false, true, true], [false, false, true]);
val it = ([true,false,false],false) : bool list * bool
- uint_add([true, true, true], [false, false, true]);
val it = ([false,false,false],true) : bool list * bool

解答

●問題82

uint を +1 する関数 uint_inc x を定義してください。uint_inc はタプルを返します。桁あふれが生じた場合、2 番目の返り値は true になります。

val uint_inc = fn : bool list -> bool list * bool

- uint_inc([false, false, false]);
val it = ([false,false,true],false) : bool list * bool
- uint_inc([true, true, true]);
val it = ([false,false,false],true) : bool list * bool

解答

●問題83

2 つの uint を減算する関数 uint_sub(x, y) を定義してください。uint_sub はタプルを返します。桁借りが生じた場合、2 番目の返り値は true になります。なお、x, y の桁は同じものとします。

val uint_sub = fn : bool list * bool list -> bool list * bool

- uint_sub([true, true, true, false], [false, true, false, true]);
val it = ([true,false,false,true],false) : bool list * bool
- uint_sub([true, true, true, false], [true, true, true, true]);
val it = ([true,true,true,true],true) : bool list * bool
- uint_sub([true, true, true, true], [true, true, true, true]);
val it = ([false,false,false,false],false) : bool list * bool

解答

●問題84

uint を左へ 1 ビット論理シフトする関数 uint_sll と、右へ 1 ビット論理シフトする関数 uint_srl を定義してください。uint_sll と uint_srl はタプルを返します。2 番目の返り値は uint_sll であれば MSB、uint_srl であれば LSB になります。

val uint_srl = fn : bool list -> bool list * bool
val uint_sll = fn : bool list -> bool list * bool

- uint_srl([true, false, true, false]);
val it = ([false,true,false,true],false) : bool list * bool
- uint_srl([false, true, false, true]);
val it = ([false,false,true,false],true) : bool list * bool
- uint_sll([true, false, true, false]);
val it = ([false,true,false,false],true) : bool list * bool
- uint_sll([false, true, false, false]);
val it = ([true,false,false,false],false) : bool list * bool

解答

●問題85

次に示す uint の比較関数を定義してください。なお、x, y の桁は同じものとします。

val uint_equal = fn : ''a * ''a -> bool
val uint_zero = fn : bool list -> bool
val uint_greater = fn : bool list * bool list -> bool
val uint_less = fn : bool list * bool list -> bool

- uint_equal([true, true, true, true], [true, true, true, true]);
val it = true : bool
- uint_equal([true, true, true, true], [true, true, false, true]);
val it = false : bool
- uint_zero([false, false, false, true]);
val it = false : bool
- uint_zero([false, false, false, false]);
val it = true : bool
- uint_greater([false, true, true, true], [false, true, true, false]);
val it = true : bool
- uint_greater([false, true, true, true], [false, true, true, true]);
val it = false : bool
- uint_greater([false, true, true, true], [true, true, true, true]);
val it = false : bool
- uint_less([false, true, true, true], [false, true, true, false]);
val it = false : bool
- uint_less([false, true, true, true], [false, true, true, true]);
val it = false : bool
- uint_less([false, true, true, true], [true, true, true, true]);
val it = true : bool

解答

●問題86

2 つの uint を乗算する関数 uint_mul(x, y) を定義してください。桁あふれは無視してください。なお、x, y の桁は同じものとします。

val uint_mul = fn : bool list * bool list -> bool list

- uint_mul([false, false, true, true], [false, false, true, true]);
val it = [true,false,false,true] : bool list
- uint_mul([true, false, false, false], [false, false, true, false]);
val it = [false,false,false,false] : bool list
- uint_mul([true, false, false, false], [false, false, false, true]);
val it = [true,false,false,false] : bool list

解答

●問題87

2 つの uint を除算する関数 uint_div(x, y) を定義してください。uint_div は商と余りをタプルで返します。なお、x, y の桁は同じものとします。

val uint_div = fn : bool list * bool list -> bool list * bool list

- uint_div([true,true,true,true],[false,false,true,false]);
val it = ([false,true,true,true],[false,false,false,true])
  : bool list * bool list
- uint_div([true,true,true,true],[false,true,false,false]);
val it = ([false,false,true,true],[false,false,true,true])
  : bool list * bool list
- uint_div([true,true,true,true],[true,false,false,false]);
val it = ([false,false,false,true],[false,true,true,true])
  : bool list * bool list

解答

●問題88

複雑なデータ構造をファイルなどに保存する場合、データ構造を線形なデータに変換できると便利です。このような操作を「シリアライズ (serialize) 」とか「シリアル化」といいます。逆に、元のデータ構造に戻す操作を「デシリアライズ」といいます。

二分木を次のように定義したとき、それをシリアライズする関数 serialize tree を作ってください。

datatype 'a tree = Leaf of 'a | Node of 'a tree * 'a tree

今回は二分木の要素を整数 (int) とします。二分木は次の方法で簡単にシリアライズすることができます。

1. 二分木を行きがけ順に巡回する。
2. 節ではフラグ 0 を出力して左右の枝をたどる。
3. 葉に到達したらフラグ 1 と要素を出力する。

なお、シリアライズしたデータはリストに格納して返すことにします。

val serialize = fn : int tree -> int list

- serialize(Node(Leaf 10, Leaf 20));
val it = [0,1,10,1,20] : int list
- serialize(Node(Node(Leaf 10, Leaf 20), Leaf 30));
val it = [0,0,1,10,1,20,1,30] : int list
- serialize(Node(Node(Leaf 10, Leaf 20), Node(Leaf 30, Leaf 40)));
val it = [0,0,1,10,1,20,0,1,30,1,40] : int list

解答

●問題89

関数 seriallize でシリアライズしたデータを復元する関数 deserialize ls を定義してください。

val deserialize = fn : int list -> int tree * int list

- deserialize([0,1,10,1,20]);
val it = (Node (Leaf 10,Leaf 20),[]) : int tree * int list
- deserialize([0,0,1,10,1,20,1,30]);
val it = (Node (Node (#,#),Leaf 30),[]) : int tree * int list

- deserialize([0,0,1,10,1,20,0,1,30,1,40]);
val it = (Node (Node (#,#),Node (#,#)),[]) : int tree * int list
- serialize(#1(it));
val it = [0,0,1,10,1,20,0,1,30,1,40] : int list

解答

●問題90

部分和問題は、要素が数値の集合 S において、要素の総和が M となる部分集合があるか判定する問題です。たとえば、集合 {2, 3, 5, 8} の場合、総和が 10 となる部分集合は {2, 3, 5} と {2, 8} がありますが、14 となる部分集合はありません。部分集合の総数は、要素数を n とすると 2ⁿ 個になるので、n が大きくなるとナイーブな方法では時間がかかってしまいます。実際には、動的計画法などの手法を使うことで、現実的な時間で部分和問題を解くことができます。

部分和問題を解くプログラムを作ってください。

val subset_sum = fn : int * int list -> unit

- subset_sum(10, [2,3,5,8]);
2 3 5
2 8
val it = () : unit
- subset_sum(14, [2,3,5,8]);
val it = () : unit

解答

●解答76

真偽値 p, q の論理演算は全部で 16 通りあります。これらの論理演算は not, and, or の組み合わせで実現することができます。

    否定
 p     not
-------------
 false true
 true  false

              論理積  論理和  否定論理積  否定論理和  排他的論理和
 p     q       and      or       nand        nor          xor
-------------------------------------------------------------------
 false false  false   false      true       true         false
 false true   false   true       true       false        true
 true  false  false   true       true       false        true
 true  true   true    true       false      false        false

演算結果が true となる所に注目します。排他的論理和の場合、p = false, q = true または p = true, q = false のときに結果は true になります。最初の条件は (not p) andalso q で、2 番目の条件は p andalso (not q) で表すことができます。あとは 2 つの条件式を orelse で結合すればいいわけです。プログラムは次のようになります。

リスト : 排他的論理和

fun xor(p, q) = ((not p) andalso q) orelse (p andalso (not q))

(* 別解 *)
fun xor1(p, q) = (p orelse q) andalso (not (p andalso q))

別解はブール代数の定理を用いて求めることができます。上図の or と nand の and を計算すると、確かに xor になることがわかります。

●解答77

真理値表から s = p XOR q, c = p AND q であることがすぐにわかります。

リスト : 半加算器

fun half_adder(p, q) = (xor(p, q), p andalso q)

これを論理回路で実現すると「半加算器」になります。s は 1 ビットの加算、c が桁上がりを表します。ただし、半加算器は入力が 2 つしかないので、下位の桁上がりを受け取ることができません。整数の加算回路を実現するには、次に示す全加算器を使います。

●解答78

r を桁上がりと考えると、真理値表は 1 ビットの加算を表していることがわかります。この真理値表を出力する論理回路を「全加算器」といいます。全加算器は 2 つの半加算器と or を使って実現することができます。

リスト : 全加算器

fun full_adder(p, q, r) =
    let
      val (a, b) = half_adder(p, q)
      val (c, d) = half_adder(a, r)
    in
      (c, b orelse d)
    end

最初に p と q を half_adder で加算します。値は a, b にセットします。次に、a と r を half_adder で加算します。値は c と d にセットします。加算の結果は c になり、桁上がりは b orelse d で求めることができます。

●解答79

リスト : 数値を m 桁の uint に変換

fun oddp(n) = n mod 2 <> 0
fun evenp(n) = n mod 2 = 0

fun int_to_uint(n, m) =
    let
      fun iter(n, a) =
          if length a = m then a
          else iter(n div 2, oddp(n)::a)
    in
      iter(n, [])
    end

int_to_uint は簡単です。ビットオンを true に、ビットオフを false に変換するだけです。数値 n が奇数の場合、LSB は 1 なので累積変数 a に true を追加します。そうでなければ false を追加します。この処理は述語 oddp を使うと簡単です。あとは n を 2 で割り算し、ビットを順番に調べていくだけです。

リスト : uint を数値に変換

fun uint_to_int(x) =
    foldl (fn(n, a) => if n then a * 2 + 1 else a * 2) 0 x

uint_to_int も簡単です。foldl で要素を順番に取り出し、要素 n が true ならば累積変数 a を 2 倍して 1 を足し算します。false ならば 1 を足し算しません。

●解答80

リスト : 論理演算

(* 論理積 *)
fun uint_and(x, y) = ListPair.map (fn(a, b) => a andalso b) (x, y)

(* 論理和 *)
fun uint_or(x, y) = ListPair.map (fn(a, b) => a orelse b) (x, y)

(* 排他的論理和 *)
fun uint_xor(x, y) = ListPair.map xor (x, y)

(* 否定 *)
fun uint_not(x) = map (op not) x

論理演算は map を使うと簡単です。andalso と orelse は関数形式に変換できないので、直接 map に渡すことはできません。このため、匿名関数の中で a andalso b と a orelse b を評価しています。

●解答81

リスト : 加算

fun uint_add(x, y) =
    ListPair.foldr (fn(n, m, (a, b)) =>
                      let
                        val (s, c) = full_adder(n, m, b)
                      in
                        (s::a, c)
                      end)
                   ([], false)
                   (x, y)

uint_add は ListPair.foldr と full_adder を使うと簡単です。foldr でリスト x, y の最後尾の要素から full_adder を順番に適用して加算処理を行います。匿名関数の引数 n がリスト x の要素、m がリスト y の要素、第 3 引数のタプルが累積変数です。タプルの先頭要素 a が uint を表すリスト、次の要素 b が桁上がりの有無を表す真偽値です。初期値は空リストと false に設定します。

●解答82

リスト : uint をインクリメントする

fun uint_inc(x) =
    foldr (fn(n, (a, b)) => 
             let
               val (s, c) = half_adder(n, b)
             in
               (s::a, c)
             end)
          ([], true)
          x

uint_inc は uint_add とほとんど同じです。foldr に渡す初期値を空リストと true に設定します。これで引数 x を +1 することができます。

●解答83

減算は 2 の補数を使って計算します。簡単な例として 4 ビットの整数値を考えてみましょう。負の整数を 2 の補数で表した場合、4 ビットで表される整数は -8 から 7 になります。次の図を見てください。

 0 : 0000
 1 : 0001    -1 : 1111
 2 : 0010    -2 : 1110
 3 : 0011    -3 : 1101
 4 : 0100    -4 : 1100
 5 : 0101    -5 : 1011
 6 : 0110    -6 : 1010
 7 : 0111    -7 : 1001
             -8 : 1000


    図 : 2 の補数

2 の補数はビットを反転した値 (1 の補数) に 1 を加算することで求めることができます。たとえば 7 - 2 は 7 + (-2) = 0111 + 1110 = 1 0101 となり、桁上がりを無視すると値は 5 になります。また、15 - 14 は (-1) - (-2) = (-1) + 2 = 1111 + 0010 = 1 0001 となり、正しく計算することができます。

逆に、2 - 7 は 2 + (-7) = 0010 + 1001 = 1011 になります。この場合、2 の補数で考えると 1011 は -5 になるので、符号付き整数では正しい値になりますが、無符号整数で考えると桁借りが発生しています。したがって、減算したときの桁借りの有無は、加算したときの桁上がりの値を反転することで求めることができます。

プログラムは次のようになります。

リスト : 減算

fun uint_sub(x, y) =
    let
      val (a, _) = uint_inc(uint_not(y))
      val (s, c) = uint_add(x, a)
    in
      (s, not c)
    end

uint_not(y) で 1 の補数を求め、uint_inc で +1 することで 2 の補数を求めることができます。あとは uint_add で x と加算するだけです。値を返すとき、not で c の値を反転することをお忘れなく。

●解答84

リスト : 論理シフト

exception Empty_list

fun butlast([]) = raise Empty_list
|   butlast([_]) = []
|   butlast(x::xs) = x :: butlast(xs)

fun last([]) = raise Empty_list
|   last([x]) = x
|   last(_::xs) = last(xs)

fun uint_srl(x) = (false :: butlast(x), last(x))

fun uint_sll(x) = ((tl x) @ [false], hd x)

論理シフトも簡単です。uint_srl は関数 butlast で最後尾のセルを取り除き、先頭に false を追加します。関数 last は最後尾の要素を取り出します。uint_sll は tl で先頭要素を取り除き、演算子 @ で最後尾に [false] を追加するだけです。

●解答85

リスト : uint の比較関数

fun uint_equal(x, y) = x = y

fun uint_zero(x) = List.all (fn y => not y) x

fun uint_greater([], []) = false
|   uint_greater(x::xs, y::ys) =
    if x = y then uint_greater(xs, ys) else x
|   uint_greater(_, _) = raise Empty_list

fun uint_less([], []) = false
|   uint_less(x::xs, y::ys) =
    if x = y then uint_less(xs, ys) else y
|   uint_less(_, _) = raise Empty_list

uint_equal は比較演算子 = で x と y を比較するだけです。unit_zero は関数 List.all ですべての要素が false であることを確認します。uint_greater は x と y の要素を先頭から順番に比較し、x の要素と y の要素が等しい場合は uint_greater を再帰呼び出しします。要素が異なる場合、要素 x が true ならば x が大きいので true を返します。そうでなければ false を返します。つまり、x の値を返せば良いわけです。uint_less も同様にプログラムできます。

●解答86

筆算のアルゴリズムをそのまま 2 進数に適用します。たとえば、1 1 0 1 と 1 0 1 の乗算は次のように計算します。

       1 1 0 1
 *       1 0 1
 --------------
       1 1 0 1
     0 0 0 0
   1 1 0 1
 -------------
 1 0 0 0 0 0 1


図 : 1101 * 101

このアルゴリズムはビットシフトと加算で実現することができます。桁あふれのチェックは行わないことにすると、プログラムは次のようになります。

リスト : uint の 乗算

fun make_list(x, n) =
  let
    fun iter(0, a) = a
    |   iter(n, a) = iter(n - 1, x::a)
  in
    iter(n, [])
  end

fun uint_mul(x, y) = 
    #1(foldr (fn(n, (a, b)) =>
               let
                 val c = #1(uint_sll(b))
               in
                 if n then (#1(uint_add(a, b)), c) else (a, c)
               end)
             (make_list(false, length(x)), x)
             y)

foldr で y の LSB から計算を始めます。匿名関数の引数 n が y の要素、第 2 引数にはタプルを渡します。第 1 要素 a が累積値、第 2 要素 b が累積値に加算する値です。最初は 0 と x に初期化します。n が真のときは a に b を加算します。そうでなければ、a を加算しません。この値と uint_sll で b を 1 ビット左シフトした値をタプルに格納して返します。最後に foldr の返り値から累積値を取り出して返します。

●解答87

筆算のアルゴリズムをそのまま 2 進数に適用します。次の図を見てください。

     1 0 1 0 1
---------------
 1 1 0 1 0 1 1
 1 0 1 0 0 0 0
---------------
     1 1 0 1 1
     1 0 1 0 0
   ------------
         1 1 1
         1 0 1
         ------
           1 0


図 : 1101011 / 101

x (1101011) を y (101) で除算する場合、最初に y を左シフトして桁合わせを行います。上図の場合、1101011 から y を 4 ビットシフトした値 z (1010000) を引き算して余り q が 11011 になります。このとき、商 p に 1 をセットします。次に、z を右へ 1 ビットシフトした 101000 と q を比較します。この場合、q のほうが小さいので引き算できません。p の値は左へ 1 ビットシフトして 10 になります。

あとは同様に、z を右へ 1 ビットシフトして q と比較します。引き算できる場合は p を左へ 1 ビットシフトしてから値を +1 します。引き算できない場合は p を左へ 1 ビットシフトするだけです。上図の場合、10100 は 11011 よりも小さいので、p の値は 101 になり、q の値は 111 になります。次に、1010 は 111 よりも大きいので p の値は 1010 になります。最後に、101 は 111 よりも小さいので、p の値は 10101 になり、q の値は 10 になります。これで商 p と余り q を求めることができます。

プログラムは再帰定義を使うと簡単です。次のリストを見てください。

リスト : uint の除算

fun uint_div(x, y) =
    if uint_less(x, y) then (make_zero(length(x)), x)
    else if uint_equal(x, y) orelse (hd y) then
      (#1(uint_inc(make_zero(length(x)))), #1(uint_sub(x, y)))
    else
      let
        val (p, q) = uint_div(x, #1(uint_sll(y)))
      in
        if uint_less(q, y) then (#1(uint_sll(p)), q)
        else (#1(uint_inc(#1(uint_sll(p)))), #1(uint_sub(q, y)))
      end

uint_div は再帰呼び出しするたびに引数 y を 1 ビット左シフトして桁合わせを行います。x が y よりも小さい場合は除算できないので商 0 と余り x をタプルで返します。x と y が等しい、または y の MSB が true の場合、商は 1 で余りが x - y になります。

これ以外の場合、y を 1 ビット左シフトして uint_div を再帰呼び出しします。余り q が y よりも小さい場合、p を 1 ビット左シフトした値と q を返します。そうでなければ、p を 1 ビット左シフトしてから +1 した値と q - y を返します。これで商と余りを求めることができます。

●解答88

リスト : 二分木のシリアライズ

datatype 'a tree = Leaf of 'a | Node of 'a tree * 'a tree

fun serialize(Leaf x) = [1, x]
|   serialize(Node (l, r)) = [0] @ serialize(l) @ serialize(r)

二分木のシリアライズは簡単です。引数 tree が Node (節) の場合、0 を出力してから再帰呼び出しして左部分木 l をたどり、それから右部分木 r をたどります。その結果を演算子 @ で連結すればいいわけです。Leaf (葉) の場合は 1 と要素を格納したリストを返します。

●解答89

リスト : 二分木のデシリアライズ

exception Deserialize_err

fun deserialize(1::x::ls) = (Leaf x, ls)
|   deserialize(0::ls) =
    let
      val (x, ls1) = deserialize(ls)
      val (y, ls2) = deserialize(ls1)
    in
      (Node (x, y), ls2)
    end
|   deserialize(_) = raise Deserialize_err

デシリアライズも簡単です。関数 deserialize は生成した二分木と残りのデータをタプルで返します。リスト ls の先頭要素が 0 の場合、deserialize を再帰呼び出しして左部分木 x を生成し、それから右部分木 y を生成します。あとは (Node(x, y), ls2) を返すだけです。ls の先頭要素が 1 の場合は葉なので、次の要素 x を取り出して (Leaf x, ls) を返します。

●解答90

まずはナイーブな方法で部分和問題を解いてみましょう。今回は要素を正整数に限定します。部分和問題は「べき集合」を生成する高階関数 power_set を使うと簡単です。プログラムは次のようになります。

リスト : 部分和問題

(* べき集合の生成 *)
fun power_set f xs =
    let
      fun power_sub [] a = f (rev a)
      |   power_sub (y::ys) a = (power_sub ys (y::a); power_sub ys a)
    in
      power_sub xs []
    end

(* リストの要素の和を求める *)
fun sum_list([]) = 0
|   sum_list(x::xs) = x + sum_list(xs)

(* リストの表示 *)
fun print_intlist([]) = print("\n")
|   print_intlist(x::xs) =
    (print(Int.toString(x) ^ " "); print_intlist(xs))

(* 部分和問題を解く *)
fun subset_sum(n, xs) =
    let
      fun check(ys) = if sum_list(ys) = n then print_intlist(ys) else ()
    in
      power_set check xs
    end

部分集合 ys の総和を関数 sum_list で求め、n と等しい場合は print_intlist で出力します。それでは実行してみましょう。

>>> subset_sum0(10, [2, 3, 5, 8])
[2, 8]
[2, 3, 5]
>>> subset_sum0(14, [2, 3, 5, 8])
>>>

とても簡単ですね。ただし、集合の要素数が多くなると、実行時間がかかるようになります。要素数を n とすると、subset_sum の実行時間は 2ⁿ に比例する遅いプログラムです。興味のある方は高速化に挑戦してみてください。