プログラミング言語特論 第3回レポート

  1. （線形再帰の除去）

    次のように定義されたC言語の関数sum, reverse （ソース）: 

      int sum(list xs) {
    if (xs==NULL) {
      return 0;
    } else {
      return xs->car+sum(xs->cdr);
    }  
  }

  list reverse(list xs)  {
    if (xs==NULL) {
      return xs;
    } else {
      return append(reverse(xs->cdr), cons(xs->car, NULL));
    }
  }
    を同等な繰り返しを用いた定義に書き換えよ。

    ただし、このプログラムの中で使われている構造体や関数の定義は次のとおりである。 

      struct _list {
    int car;
    struct _list* cdr;
  };
  
  typedef struct _list* list;
  
  list cons(int x, list xs) {
    list ret = (list)malloc(sizeof(struct _list));
    ret->car = x;
    ret->cdr = xs;
    return ret;
  }

  list append(list xs, list ys) {
    if (xs==NULL) {
      return ys;
    } else { 
      return cons(xs->car, append(xs->cdr, ys));
    }
  }
  2. （非決定性 --- 「アガリ」判定）

    1〜9までの数字の書かれた「パイ」を14枚集めるゲームがある。
      2つの同じ数の「パイ」の集まりを、「トイツ」
      3つの同じ数の「パイ」の集まりを、「コーツ」
      3つの連続した数の「パイ」の集まりを「シュンツ」
      「シュンツ」または「コーツ」のことを「メンツ」
    という。

    「パイ」の集まりのなかに、「メンツ」が4組と「トイツ」が1組あれば、 「アガリ」という。

    整数のリストの中に「シュンツ」があるかどうかを判定するプログラムは非決定性のモナド （プリント4.12） 

      type M a = [a];
  
  unitM :: a -> M a;
  unitM a = [a];
  
  bindM :: M a -> (a -> M b) -> M b;
  m `bindM` k = case m of { 
		  []   -> [];
		  x:xs -> k x ++ (xs `bindM` k)
		};
  
  failM :: M a;
  failM = [];
    を用いて、 
      pick :: Eq a => [a] -> M a;
  pick xs = nub xs;  
  
  remove :: Eq a => a -> [a] -> M [a];
  remove x xs = if x `elem` xs then unitM (delete x xs) else failM;
  
  shuntsu :: [Int] -> M ([Int], [Int]);
  shuntsu xs = pick xs `bindM`    \ y0 ->
	       remove  y0    xs  `bindM` \ ys0 ->
	       remove (y0+1) ys0 `bindM` \ ys1 ->
	       remove (y0+2) ys1 `bindM` \ ys2 ->
	       unitM ([y0, y0+1, y0+2], ys2);
    のように定義することができる。ここで elem, nub, deleteなどはHaskellに標準で用意されている関数である。

      nub                     :: (Eq a) => [a] -> [a]; -- 重複を取り除く
  nub                      = nubBy (==); 
  
  nubBy			:: (a -> a -> Bool) -> [a] -> [a];
  nubBy eq []              = [];
  nubBy eq (x:xs)          = x : nubBy eq (filter (\y -> not (eq x y)) xs);

  delete                  :: (Eq a) => a -> [a] -> [a];  -- 要素の削除
  delete                   = deleteBy (==);
  
  deleteBy                :: (a -> a -> Bool) -> a -> [a] -> [a];
  deleteBy eq x []         = [];
  deleteBy eq x (y:ys)     = if x `eq` y then ys else y : deleteBy eq x ys;

    shuntsuは引数のリスト中に含まれている「シュンツ」と 残った「パイ」の組合せをすべて列挙する。例えば、 shuntsu [1,2,3,4,5]の結果は、 

      [([1,2,3],[4,5]),([2,3,4],[1,5]),([3,4,5],[1,2])]
    となる

    1. 整数のリストの中にある「トイツ」「コーツ」をすべて列挙する関数 

        toitsu :: [Int] -> M ([Int], [Int]);
  kotsu  :: [Int] -> M ([Int], [Int]);
      を定義せよ。

    2. （通常長さ14の）整数のリストを受け取り「アガリ」になっているかどうかを判定し、 「アガリ」のときは「メンツ」と「トイツ」のリストを返す関数: 

        agari :: [Int] -> M [[Int]]
      を定義せよ。例えば、agari [1,1,1,1,2,3,4,5,6,7,8,9,9,9]の結果は 
         [[[1,1,1],[1,2,3],[4,5,6],[7,8,9],[9,9]]]
      となる。

      注: agariの結果の中に順番だけ異なる本質的に同じ出力が重複して、例えば 

        [[[1,2,3],[4,5,6],[7,8,9],[1,1,1],[9,9]],[[1,2,3],[4,5,6],[1,1,1],[7,8,9],[9,9]],[[1,2,3],[7,8,9],[4,5,6],[1,1,1],[9,9]], ..]
      のようになっても良い。もちろん、重複はできるだけ取り除くことが望ましい。

  3. （CPSへの変換）

    プリントp.46 問5.7.1
    このHTMLファイルを元にしてよい。

  4. （チャレンジ）
    上記の「アガリ」判定プログラムをCまたはJavaに移植せよ。
TeXまたはWord（など）でレポートを作成して下さい。

締切は2月19日、提出場所は7Fの香川のレターボックスです。

プログラミング言語特論のホームページ
Koji Kagawa (kagawa@eng.?????)