IFPH 練習問題 1.2.3 簡約系列の計数 ref: http://qiita.com/items/6566c006074005c12f88

ifphex010203.hs

-- | 式の定義
data Expr = Zero
          | Pred Expr
          | Succ Expr
  deriving (Show,Read)

-- | Redex(簡約可能式)を数える．
countRedex :: Expr -> Int
countRedex Zero = 0
countRedex (Succ t) = case t of
  Pred _ -> 1 + countRedex t
  _      -> countRedex t
countRedex (Pred t) = case t of
  Succ _ -> 1 + countRedex t
  _      -> countRedex t

-- | 1ステップの簡約(複数の結果がありうる)
reduce :: Expr -> [Expr]
reduce Zero     = []
reduce (Pred t) = case t of
  Succ t' -> t' : map Pred (reduce t)
  _       -> map Pred (reduce t)
reduce (Succ t) = case t of
  Pred t' -> t' : map Succ (reduce t)
  _            -> map Succ (reduce t)

-- | 簡約系列の生成
redSeqs :: Expr -> [[Expr]]
redSeqs t = case reduce t of
  [] -> [[t]]
  ts -> concatMap (map (t:) . redSeqs) ts

-- | 簡約系列の数
countRedSeqs :: Expr -> Int
countRedSeqs =  length . redSeqs

-- | IFPH 練習問題 1.2.3 で与えられた式
exer010203 :: Expr
exer010203 =  Succ(Pred(Succ(Pred(Pred(Zero)))))

{-
実行例:
? countRedSeqs exer010203
3
-}