train number.....(0) - wvogel日記

明日から一週間家を離れるのでブログの更新が滞ってしまう。
なので、その前になにか書こうかと思ったけど、ちょっと面倒な問題にぶつかってしまった.....

タイトルのとおり、
電車乗るときに買う切符に印字されている4桁の数字、
あれから、10の数字を作れるかどうかという判定をするプログラムを書こうかと思って。
とりあえず括弧と割り算は置いておいて、

,-,*の3つでやる

方針としては、
数字と演算子両方について、並び順の全パターンを列挙し、[String]にしてやってから、
各式についてParsecで値を計算してやれば良い。

数字の並び、及び演算子の並びには

import Data.List

permutations :: a -> [a]

を利用すれば簡単に列挙できる

だが、演算子は

+,+,+  -,-,*

のような並びも許されるということを忘れていた.....

とりあえず、重複なしの場合の式の列の生成

module Train where
import Data.List

opes = permutations ['+','-','*']

train :: String -> [String]
train = concat.map (mysort opes).permutations

mysort :: [String] -> String -> [String]
mysort [] _ = []
mysort (o:os) vs =mysort' (zip (o++"_") vs):mysort os vs
  where
    mysort' :: [(Char,Char)] -> String
    mysort' [(_,v)] = [v]
    mysort' ((o,v):ovs) = v:o:mysort' ovs

関数名は適当です。
mysortも、どっちかというとcombinationsの方が正しい。
これで、とりあえず、暫定的ではあるが、式は生成できるので
（演算子の重複は、opes = の箇所をいじっていくことにする）
Parsecで計算部を作りましょう。
今回は（）を含んでいないので、以前Parsec使わずに作った簡易電卓でも代用出来ますが、（）への拡張を考え、Parsecを使う

書いてみた。

run :: Show a => Parser a ->String -> IO()
run p input = case (parse p "" input) of
                Left _ -> putStr"Parse error at"
                Right  x -> print x

num:: Parser Int
num = read<$>many1 digit

express' :: Parser Int
express' = do foldr ($)<$>factor'<*> many (add<|>sub)
 where
  add = (+) <$>(char '+' >> factor')
  sub =flip (-) <$>(char '-' >> factor')

factor' :: Parser Int
factor' = do foldr ($)<$> num
               <*> (many $ (*) <$>(char '*'>> factor'))

一度do記法で書いたものを、Applicativeで書き直したものです。
まだまだ、いきなりApplicativeスタイルでは書き進められない。