0

私は最近、A Taste of Curryをたどり、その後、もう少し実質的なパーサーを作成することによって、簡単な算術パーサーの例をテストすることにしました。

記事で例示されているように、(属性と子を使用して)node2string動作する関数を作成し、それから関数を取得しました。Nodeinverseparse

<input/>最初のナイーブな実装には、単純なHTML スニペットなどを正確に 1 つのNode表現に解析するという誤りがありました。他のすべては、非決定論的に次のような無効なものを生成しました

Node { name = "input", attrs = [Attr "type" "submit"] }
Node { name = "input type=\"submit\"", attrs = [] }

等々。

内部からそれを修正するためのいくつかの最初の素朴な試みの後node2string、私はポイントに気付きましparse = inverse node2stringた<input type="submit"/>.その2 つの有効で構築可能な値はNode、HTML 表現につながります。

Node私は、アルファベットのみを渡すことを許可するように制限する必要があることに気付きましたAttr. 論理プログラムよりも基本的ではない設定 (純粋な宣言型プログラミングとは対照的に、はるかに手書きで「指示的」な通常の Haskell など) では、NodeコンストラクターをmkNodeセンチネル関数などの背後に単に隠していたでしょうが、私はこれを感じています。推論エンジンまたは制約ソルバーがどのように機能するかにより、Curry ではうまく機能しません (これについては私が間違っている可能性があります。実際、そうであることを願っています)。

そのため、代わりに次のようになりました。Curry のメタプログラミング (または、Curry がサポートしていれば Template Haskell) を使用して手動のボイラープレートをクリーンアップできると思いますが、表面的な処理は状況から抜け出す方法の 1 つにすぎません。

data Name = Name [NameChar] -- newtype crashes the compiler
data NameChar = A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

name2char :: NameChar -> Char
name2char c = case c of A -> 'a'; B -> 'b'; C -> 'c'; D -> 'd'; E -> 'e'; F -> 'f'; G -> 'g'; H -> 'h'; I -> 'i'; J -> 'j'; K -> 'k'; L -> 'l'; M -> 'm'; N -> 'n'; O -> 'o'; P -> 'p'; Q -> 'q'; R -> 'r'; S -> 's'; T -> 't'; U -> 'u'; V -> 'v'; W -> 'w'; X -> 'x'; Y -> 'y'; Z -> 'z'

name2string :: Name -> String
name2string (Name s) = map name2char s

-- for "string literal" support
nameFromString :: String -> Name
nameFromString = inverse name2string

data Node = Node { nodeName :: Name, attrs :: [Attr], children :: [Node] }
data Attr = Attr { attrName :: Name, value :: String }

attr2string :: Attr -> String
attr2string (Attr name value) = name2string name ++ "=\"" ++ escape value ++ "\""
  where escape = concatMap (\c -> if c == '"' then "\\\"" else [c])

node2string :: Node -> String
node2string (Node name attrs children) | null children = "<" ++ name' ++ attrs' ++ "/>"
                                       | otherwise     = "<" ++ name' ++ attrs' ++ ">" ++ children' ++ "</" ++ name' ++ ">"
  where name'     = name2string name
        attrs'    = (concatMap ((" " ++) . attr2string) attrs)
        children' = intercalate "" $ map (node2string) children

inverse :: (a -> b) -> (b -> a)
inverse f y | f x =:= y = x where x free

parse :: String -> Node
parse = inverse node2string

実際、これは完全に機能します（私の判断では）：

Parser> parse "<input type=\"submit\"/>"
(Node [I,N,P,U,T] [(Attr [T,Y,P,E] "submit")] [])

Parser> parse "<input type=\"submit\" name=\"btn1\"/>"
(Node [I,N,P,U,T] [(Attr [T,Y,P,E] "submit"),(Attr [N,A,M,E] "btn1")] [])

(Curry には型クラスがないため、[NameChar]print をより適切に作成する方法はまだわかりません)

ただし、私の質問は次のとおりです。

のようなものisAlpha(または実際の HTML 仕様により忠実な関数) を使用して、これと同等の結果を達成する方法NameCharはありますか? ADT 内のどこかに「機能制限」を配置することすらできないようです。

依存型付き関数型論理プログラミング言語では、制約を型レベルで表現し、推論エンジンまたは制約ソルバーに処理させるだけですが、ここでは途方に暮れているようです。

4

1 に答える 1

1

を使用しても同じ結果が得られますChar。すでに指摘したように、を使用して部分的なアイデンティティとしてisAlpha定義できます。name2charコードの次の行を変更しました。

type NameChar = Char

name2char :: NameChar -> Char
name2char c | isAlpha c = c

次に、2 つの例示的な式は次のように評価されます。

test> parse "<input type=\"submit\" name=\"btn1\"/>"
(Node (Name "input") [(Attr (Name "type") "submit"),(Attr (Name "name") "btn1")] [])

test> parse "<input type=\"submit\"/>"
(Node (Name "input") [(Attr (Name "type") "submit")] [])

副作用として、英字以外の文字を含む名前は警告なしに で失敗しnameFromStringます。

test> nameFromString "input "

編集：あなたは関数パターンのファンであるように見えるので、Nodes およびAttrs のジェネレーターを定義し、それらを変換関数で使用できます。

attr :: Name -> String -> Attr
attr name val
  | name `elem` ["type", "src", "alt", "name"] = Attr name val

node :: String -> [Attr] -> [Node] -> Node
node name [] nodes
  |  name `elem` ["a", "p"] = Node name [] nodes
node name attrPairs@(_:_) nodes
  |  name `elem` ["img", "input"] = Node name attrPairs nodes

node2string :: Node -> String
node2string (node name attrs children)
  | null children = "<" ++ name ++ attrs' ++ "/>"
  | otherwise     = "<" ++ name ++ attrs' ++ ">"
                  ++ children' ++ "</" ++ name' ++ ">"
 where
  name'     = name
  attrs'    = concatMap ((" " ++) . attr2string) attrs
  children' = intercalate "" $ map (node2string) children

attr2string :: Attr -> String
attr2string (attr name val) = name ++ "=\"" ++ escape val ++ "\""
 where
  escape = concatMap (\c -> if c == '"' then "\\\"" else [c])

このアプローチには欠点があります。有効な名前の特定のセットに対しては非常にうまく機能しますが、以前のような述語 (たとえば、all isAlpha name) を使用すると惨めに失敗します。

Edit2:条件付き のソリューションは、詳細なソリューションよりもかなり「きれい」であるという事実に加えてisAlpha、宣言的な方法でも定義されています。あなたのコメントがなければ、NameCharデータ型でアルファベット文字をエンコードしていることは (それほど簡単には) 明確になりません。一方isAlpha、条件は、必要なプロパティの宣言仕様の良い例です。これはあなたの質問に答えていますか？何を目指しているのかわからない。

于 2015-11-09T08:38:46.850 に答える