haskell 正規表現

Question

正規表現を抽象化したコードを書きたくて、以下のようなものができました。

data Regex 
    = Literal String                        -- 完全一致
    | AnyChar                               -- 何かしら1文字 「.」
    | Not Regex　                           -- 否定 「^」
    | And {a::Regex, b::Regex}              -- aの次にb
    | Or  {a::Regex, b::Regex}              -- aまたはb 「|」
    | Repeat {range::[Int], element::Regex} -- elementがrangeのいずかの個数

superPosition :: Regex -> Regex             -- 0回か1回 「?」
superPosition regex = Repeat [0,1] regex

some :: Regix -> Regix                      -- 1回以上繰り返し 「+」
some regex = Repeat [1..] regex

oneOrMore :: Regex -> Regex                 -- 0回以上繰り返し 「*」
oneOrMode regex = Repeat [0..] regex

match :: Regex -> String -> Bool
match (Literal literal)      string = literal == string
match (AnyChar)              string = length string == 1
match (Not regix)            string = not $ match regix string
-- TODO -- match (And a b)              string =
match (Or  a b)              string = match a || match b
-- TODO -- match (Repeat range element) string = 

解決したい問題点

• TODOの部分の実装は今の自分の力でも無理やり実装しようと思えばできるけど、効率の良いhaskellらしいコードにするにはどんなやり方があるか。

• someとかの関数とOrとかのコンストラクタが利用側では同じように使えるべきだが、キャメルケースとパスカルケースで違う見た目になっている。

• superPositionとかoneOrMoreという名前付けが他のものと一貫性が取れてない。もっと良い名前がないか？

• someとかorとかの名前付けだと利用側で名前衝突が起こる可能性があるかも？ないかも？初心者だからこの名前付けが良いのか悪いのかも分からない。

• rangeに負の整数を指定できてしまう

他にも私には分からない問題点があると思うので、そちらにもリファクタリングやマサカリをお願いします。
「regexは他にあるから車輪の再発明だ」っていうマサカリだけは無しでお願いします。
勉強のために車輪の再発明をしています。

そもそもRegexはString -> Boolの型シノニムとした方がいいんですかね？

Answer 1

• TODOの部分の実装は今の自分の力でも無理やり実装しようと思えばできるけど、効率の良いhaskellらしいコードにするにはどんなやり方があるか。

マッチの部分は（手続きプログラミングでも）オートマトンを使って実装するのが定番だと思います。オートマトンについてはすみませんが他を参考にしてください。

• someとかの関数とOrとかのコンストラクタが利用側では同じように使えるべきだが、キャメルケースとパスカルケースで違う見た目になっている。

or = Or

として or を定義することができます。

• superPositionとかoneOrMoreという名前付けが他のものと一貫性が取れてない。もっと良い名前がないか？

いい案が思い付かないのでノーコメントで。

• someとかorとかの名前付けだと利用側で名前衝突が起こる可能性があるかも？ないかも？初心者だからこの名前付けが良いのか悪いのかも分からない。

名前空間があるので問題ないと思います。

例えばこれが Regex モジュールだった場合、利用者は Regex.some という形で参照することができます。（他の方法もあります。）

• rangeに負の整数を指定できてしまう

Int の代わりに Word で非負整数を表します。

Comments

[mightyMask]

そもそもこのような実装にするのと、`String->Bool`の型シノニムとして実装するのはどちらの方が良い実装だと思いますかね？

[kakkun61]

正規表現をパースしたトークン列としては

```haskell
type Regex = [Token]

data Token
= Char (Prelude.Char -> Bool)
| Or Regex Regex
| Repeat Word Regex
```

こんな雰囲気にする気がします。