egison-programming-contest.md

Egisonプログラミングコンテスト2018問題集

パターンマッチ指向プログラミング

関数型プログラミングにおいて基本的なリスト操作関数を再帰を使わずに，単一のmatch-all式で定義できる． たとえば，map関数は以下のように定義できる．

(define $map
  (lambda [$f $xs]
    (match-all xs (list something)
      [<join _ <cons $x _>> (f x)])))

以下，map関数以外のリスト操作関数について，match-allを使った定義を考えてみよう．

キーワード: something, eq, list, multiset, cons, join, predicate pattern, not-pattern, later pattern

問題

下記の空白(1,2)をうめてmember?関数を完成させよ．

(define $member?
  (lambda [$x $xs]
    (match xs (list eq)
      {[ _1_ _2_ ]
       [_ #f]})))

問題

下記の空白(1,2)をうめてreverse関数を完成させよ．

ヒント: consとjoinの逆の意味をもつsnocとniojパターンコンストラクタを使う．

(define $reverse
  (lambda [$xs]
    (match-all xs (list something)
      [ _1_ _2_ ])))

問題

下記の空白(1,2,3)をうめてconcat関数を完成させよ．

(define $concat
  (lambda [$xss]
    (match-all xss _1_
      [ _2_ _3_ ])))

問題

下記の空白(1,2,3)をうめて，2つのコレクションの共通部分を抽出するintersect関数を完成させよ．

(define $intersect
  (lambda [$xs $ys]
    (match-all [xs ys] _1_
      [ _2_ _3_ ])))

問題

下記の空白(1,2)をうめてunique関数を完成させよ．

(define $unique
  (lambda [$xs]
    (match-all xs (list eq)
      [ _1_ _2_ ])))

以下のような順序の結果を出すunique関数の実装は比較的簡単である．

(unique {1 2 3 2 4})                                                                                                                                                                                                                                                            
;{1 3 2 4} 

以下のような順序の結果を出すunique関数の実装も工夫が必要だが単一のmatch-all式で可能である．

(unique {1 2 3 2 4})                                                                                                                                                                                                                                                            
;{1 2 3 4}    

マッチャー定義

問題

以下のcardプログラムを拡張して，ジョーカーを含んだ場合でもポーカーの役判定ができるようにせよ．

  (algebraic-data-matcher
    {<spade> <heart> <club> <diamond>}))

(define $card
  (matcher
    {[<card $ $> [suit (mod 13)]
      {[<Card $x $y> {[x y]}]}]
     [$ [something] {[$tgt {tgt}]}]}))

たとえば，以下の場合について，"Straight flush"と返せるようにせよ．

(poker-hands {<Card <Club> 12>
              <Card <Club> 10>
              <Joker>
              <Card <Club> 1>
              <Card <Club> 11>})