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


  1. 問4.10.2 (プリント p.Ⅳ-12、エラー処理+状態)

    テンプレートをダウンロードして、 {- ここを考えて下さい -}となっているところを埋めて下さい。
    その後テストプログラムを適当に変更して、 適切なエラーメッセージが出るかどうか確認して下さい。

  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.Ⅴ-11 問5.7.1
    このHTMLファイルを元にしてよい。

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

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


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