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

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

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

   • （追加） 以前のテンプレートプログラムはの定義が一部抜け落ちていたことが判明しました。 （現在のテンプレートは修正済み）

     type Env = [(String, Value)];
     

     （211行め辺り）の次に、次の定義を挿入して下さい。

     lookup' :: Eq a =>  a -> [(a, b)] -> b;
     lookup' x ((n,v):rest) = if n==x then v else lookup' x rest;
     

   • （ヒント）{- ここを考えて下さい -}となっているところに ST.hsから該当する部分のコードをコピーしてきて、 （エラーメッセージに従って）2箇所修正するだけです。

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に移植せよ。

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