2

Haskellでは、XMLドキュメントの場合のように、再帰ツリーのデータ型を簡単に作成できます。

data XML = 
    Text String       -- Text of text node
  | Elem String [XML] -- Tagname; Child nodes

およびそれに関連するフォールド:

-- Simple fold (Child trees don't see the surrounding context.)
foldt :: (String -> a) -> (String -> [a] -> a) -> XML -> a
foldt fT fE (Text text) = fT text
foldt fT fE (Elem tagname ts) = fE tagname (map (foldt fT fE) ts)

-- Threaded fold for streaming applications.
-- See http://okmij.org/ftp/papers/XML-parsing.ps.gz
foldts :: (a -> String -> a) -> (a -> String -> a) ->  (a -> a -> String -> a) -> a -> XML -> a
foldts fT fE_begin fE_end = go
  where
    go seed (Text text) = fT seed text
    go seed (Elem tag children) = 
        let seed' = fE_begin seed tag in
        let seed'' = foldl go seed' children in
        fE_end seed seed'' tag

今の私の問題は、HTMLをモデル化するためにツリーデータ型にいくつかの追加の制限を追加する方法がわからないことです。HTMLでは、各要素ノードは正しいコンテキストでのみ表示でき、各要素はその子の異なるコンテキストに対応します。例えば:

  • imgのようなボイド要素には空のコンテキストモデルがあり、子を持つことは許可されていません。
  • タイトルなどのテキストコンテンツモデルを持つ要素は、子としてテキストノードのみを持つことができます(ネストされたタグは許可されません)
  • div要素はPhrasingコンテキストに表示できないため、span要素の子孫になることはできません。

だから私の質問は:

  1. Haskell98でこれらの制限をモデル化するにはどうすればよいですか?(Haskell98モデルは他のプログラミング言語にうまく翻訳されるはずなので、これを尋ねます)

    さまざまなコンテキストに対してさまざまなデータ型を作成する必要があるかもしれないと思いますが、これを原則的かつ明確な方法で行う方法がわかりません。迷子になることなくこれを行うにはどうすればよいですか?また、折り畳み関数はどのようになりますか?

  2. GADTなどの最新のGHC機能の使用が許可された場合、モデルはどのようになりますか?

    GADTは、制限をタイプチェッカーにプッシュして、折り畳み機能を単純に保つのに役立つかもしれないという予感がありますが、私はそれらの経験があまりありません...

100%機能するソリューションは必要ありません。それは明らかにStackOverflowの説明の範囲を超えているからです。GADTなどをよりよく理解し、残りを自分でできるようになるのに十分なだけです。

4

2 に答える 2

7

これにはGADTは必要ありません(少なくともまだ)。ツリータイプに関する詳細情報をコンパイラに教える必要があります。

data HTML
    = HTML HTMLHeader HTMLBody

data HTMLHeader
    = Header String

data HTMLBody
    = Body [HTMLContent]

data HTMLContent
    = Text HTMLText
    | Title HTMLText
    | Img  String
    | Elem String [HTML]

data HTMLText
    = Literal String
    | Bold String
    | Italic String
    | TextElems [HTMLText]

今、あなたはいくつかの不変条件を取得します:

-- Must have header and body. titles can't contain images.

x = HTML
        (Header "TEST") $ Body [
             Title (Literal "Title")
            ,Text (Bold "Content")
        ]

このツリーを導出するための原則的な方法は、特定のHTML文法(たとえば、XMLEBNFなど)から取得することです。http://www.w3.org/TR/2006/REC-xml11-20060816/#sec-well-formed

GADTを使用すると、いくつかのものをより効率的にエンコードでき、より強力な不変条件を適用できる関数をデータ型に書き込むことができます。

静的に検証可能なプロパティを増やし始めると、不変条件のエンコードがより複雑になる可能性があります。そのとき、GADT、型族、その他の拡張機能が役立ち始めます。

于 2013-03-17T17:47:46.243 に答える
2

これは、 OCamlに実装されたWebフレームワークである OCsigenプロジェクトによって行われ、強力な型指定の保証を提供しようとしています。

このドキュメントページで、Html5インターフェイスを確認できます。たとえば、imgスマートコンストラクターのタイプを参照してください (一口です!):

val img : 
  src:Xml.uri ->
  alt:Html5_types.text ->
  ([< `Accesskey
    | `Class
    | `Contenteditable
    | `Contextmenu
    | `Dir
    | `Draggable
    | `Height
    | `Hidden
    | `Id
    | `Ismap
    | `OnAbort
    | `OnBlur
    | `OnCanPlay
    | `OnCanPlayThrough
    | `OnChange
    | `OnClick
    | `OnContextMenu
    | `OnDblClick
    | `OnDrag
    | `OnDragEnd
    | `OnDragEnter
    | `OnDragLeave
    | `OnDragOver
    | `OnDragStart
    | `OnDrop
    | `OnDurationChange
    | `OnEmptied
    | `OnEnded
    | `OnError
    | `OnFocus
    | `OnFormChange
    | `OnFormInput
    | `OnInput
    | `OnInvalid
    | `OnKeyDown
    | `OnKeyPress
    | `OnKeyUp
    | `OnLoad
    | `OnLoadStart
    | `OnLoadedData
    | `OnLoadedMetaData
    | `OnMouseDown
    | `OnMouseMove
    | `OnMouseOut
    | `OnMouseOver
    | `OnMouseUp
    | `OnMouseWheel
    | `OnPause
    | `OnPlay
    | `OnPlaying
    | `OnProgress
    | `OnRateChange
    | `OnReadyStateChange
    | `OnScroll
    | `OnSeeked
    | `OnSeeking
    | `OnSelect
    | `OnShow
    | `OnStalled
    | `OnSubmit
    | `OnSuspend
    | `OnTimeUpdate
    | `OnVolumeChange
    | `OnWaiting
    | `Spellcheck
    | `Style_Attr
    | `Tabindex
    | `Title
    | `User_data
    | `Width
    | `XML_lang
    | `XMLns ],
   [> `Img ])
  nullary

(OCamlの標準構文では、t3つの型パラメーターを持つ 型でありa、ではなく記述されています)。bc(a,b,c) tt a b c

子がない可能性があるという事実<img>は、ここでは「nullary」タイプを使用してエンコードされています。残りの静的情報は、このノードで使用できる属性の種類をエンコードします。

奇妙な`Foo | `Bar | `Bazものは、いわゆる「ポリモーフィックバリアント」(たとえば、この記事で紹介されています)であり、OCamlに多かれ少なかれ固有の行多相を使用した一種の拡張可能な構造和タイプです(プログラミング言語には役立ちますが、拡張可能なレコードは、OCamlとHaskellの通常の名目上のレコードを一般化するためです)。ここでは、主にタイプレベルのリストの形式として使用されます。

それ以外は、これはファントムタイプの比較的古典的な使用法であり、HTML仕様に含まれるケースの数が非常に多いため、極端なサイズになります。ファントムタイプは、MLの世界で追加のタイプ抽象化を実施するためのGADTの前身です。Haskell98では、直接型抽象化ではなく、型クラスを使用して同じ種類の型レベル情報をエンコードしようとする可能性があります。

于 2013-03-17T17:54:18.080 に答える