1

ある種のツリー構造を表すadtがあるとしましょう。

data Tree = ANode (Maybe Tree) (Maybe Tree) AValType
          | BNode (Maybe Tree) (Maybe Tree) BValType
          | CNode (Maybe Tree) (Maybe Tree) CValType

型コンストラクターに対してパターンマッチングを行う方法がないことを知っている限り（または、マッチング関数自体に型がない場合）、コンパイル時の型システムを使用して、戻り値や解析の可能性を排除したいと思います。ツリーノードの「タイプ」が間違っています。たとえば、CNodeはANodeの親にしかなれません。私は持っているかもしれません

parseANode :: Parser (Maybe Tree)

私のCNodeパーサーの一部として使用されるParsec解析関数として：

parseCNode :: Parser (Maybe Tree)
parseCNode = try (
                  string "<CNode>" >>
                  parseANode >>= \maybeanodel ->
                  parseANode >>= \maybeanoder ->
                  parseCValType >>= \cval ->
                  string "</CNode>"
                  return (Just (CNode maybeanodel maybeanoder cval))
             ) <|> return Nothing

型システムによると、parseANodeはMaybe CNode、Maybe BNode、またはMaybe ANodeを返す可能性がありますが、MaybeANodeのみを返すようにしたいのです。これは、データのスキーマ値や実行時のチェックではないことに注意してください。実際には、特定のツリースキーマ用に作成したパーサーの有効性をチェックしようとしています。IOW、私は解析されたデータのスキーマの正しさをチェックしようとはしていません。実際にやろうとしているのは、パーサーのスキーマの正しさをチェックすることです。いつかparseANodeを台無しにしないようにしたいと思います。 ANode値以外のものを返します。

バインド変数の値コンストラクターと照合した場合、型推論によって意味がわかることを期待していました。

parseCNode :: Parser (Maybe Tree)
parseCNode = try (
                  string "<CNode>" >>
                  parseANode >>= \(Maybe (ANode left right avall)) ->
                  parseANode >>= \(Maybe (ANode left right avalr)) ->
                  parseCValType >>= \cval ->
                  string "</CNode>"
                  return (Just (CNode (Maybe (ANode left right avall)) (Maybe (ANode left right avalr)) cval))
             ) <|> return Nothing

しかし、これには多くの問題があります。特に、そのparseANodeはNothingを返すことができなくなりました。そして、それはとにかく機能しません-parseANodeがNothingまたはMaybe BNodeなどを返す場合、バインド変数はパターンマッチとして扱われ、ランタイムは非網羅的なパターンマッチングについて文句を言うようです。

私はこれらの線に沿って何かをすることができました：

data ANode = ANode (Maybe BNode) (Maybe BNode) AValType
data BNode = BNode (Maybe CNode) (Maybe CNode) BValType
data CNode = CNode (Maybe ANode) (Maybe ANode) CValType

しかし、制約がすべてのノードに適用されることを前提としているため、この種の問題はありません-私はそれを行うことに興味がないかもしれません-実際、ANodeの子育てのみが可能なのはCNodeだけかもしれません。だから私はこれを行うことができると思います： 

data AnyNode = AnyANode ANode | AnyBNode BNode | AnyCNode CNode

data ANode = ANode (Maybe AnyNode) (Maybe AnyNode) AValType
data BNode = BNode (Maybe AnyNode) (Maybe AnyNode) BValType
data CNode = CNode (Maybe ANode) (Maybe ANode) CValType

しかし、これにより、* Nodeとのパターンマッチングがはるかに困難になります。実際、これらは完全に異なるタイプであるため、不可能です。パターンマッチングしたいところならどこでも型クラスを作ることができたと思います

class Node t where
    matchingFunc :: t -> Bool

instance Node ANode where
    matchingFunc (ANode left right val) = testA val

instance Node BNode where
    matchingFunc (BNode left right val) = val == refBVal

instance Node CNode where
    matchingFunc (CNode left right val) = doSomethingWithACValAndReturnABool val

とにかく、これはちょっと厄介なようです。誰かがこれを行うためのより簡潔な方法を考えることができますか？

4

3 に答える 3

4

私はあなたの最終的な解決策に対するあなたの反対を理解していません。AnyNode次のように、s に対してパターンマッチングを行うことができます。

f (AnyANode (ANode x y z)) = ...

もう少し冗長ですが、必要なエンジニアリング特性を備えていると思います。

于 2010-10-09T00:22:05.730 に答える
4

コンパイル時の型システムを使用して、ツリーノードの間違った「型」を返したり解析したりする可能性を排除したいのですが。

これはGADTのユースケースのように聞こえます。

{-# LANGUAGE GADTs, EmptyDataDecls #-}
data ATag
data BTag
data CTag

data Tree t where
  ANode :: Maybe (Tree t) -> Maybe (Tree t) -> AValType -> Tree ATag
  BNode :: Maybe (Tree t) -> Maybe (Tree t) -> BValType -> Tree BTag
  CNode :: Maybe (Tree t) -> Maybe (Tree t) -> CValType -> Tree CTag

Tree tこれで、ノードタイプを気にしないとき、または気にするときに使用できTree ATagます。

于 2010-10-08T22:42:26.490 に答える
1

キーガンの答えの拡張：赤/黒の木の正しさのプロパティをエンコードすることは、一種の標準的な例です。このスレッドには、GADTとネストされたデータ型ソリューションの両方を示すコードがあります：http：//www.reddit.com/r/programming/comments/w1oz/how_are_gadts_useful_in_practical_programming/cw3i9

于 2010-12-20T14:42:32.300 に答える