1

注: これは、相互排除の並行性の問題とは関係ありませんが、この問題を説明するより良い方法は思いつきませんでした。

ユーザーにいくつかのフラグを選択させたい場合があるという問題がありますが、一部のフラグは相互に排他的です。データ構造を使用してどのフラグが相互に排他的であるかを説明したいのですが、私が考えたものはすべてぎこちないものでした。

基本的に、フラグの使用方法を次のように指定できるようにしたいと考えています。

[ -fa | -e | -d ] [ -c ] [ -g | -h]

これは、意味的には、-fa、-e、-d のいずれかを使用できますが、2 つ以上を使用することはできません (ただし、f は a と共に使用でき、両方を使用する必要はありません)。-c を指定してもしなくてもかまいません。また、-g または -h のいずれかを指定できますが、両方を指定することはできません。

これが私の「最善の」解決策です。

Map[Flag, MutexGroup] (およびその逆、Map[MutexGroup, List[Flag]]) Map[MutexGroup, List[MutexGroup]]

私の例ではどのように見えるでしょうか

Map("f" -> 1, "a" -> 1, "e" -> 2, "d" -> 3, "c" -> 4, "g" -> 5, "h" -> 6 ) Map(1 -> List(2, 3), 2 -> List(1, 3), 3 -> List(1, 2), 4 -> List.empty, 5 -> List(6), 6 - > リスト(5))

簡潔にするために、Map[MutexGroup, List[Flag]] は含めていません。

このソリューションは、それを使用しなければならないことを考えるだけで身震いします。この種のことを処理する標準的な方法はありますか?

4

1 に答える 1

3

あなたは文法を説明しています。

文法を表現するのに最適なのは、抽象構文木です。ツリーは、(相互に排他的な) 選択を表す標準構造です。

構文ツリーはさまざまな方法で表すことができますが、適切な形式の式のみを構築できることが静的に保証されるため、1 つの優れたアプローチは代数データ型を使用することです。フラグ自体がセットを形成するため、Setデータ型を使用して重複しないプロパティを強制することも有効です。

-- can have any one of -fa, -e, -d, but not two or more
-- (however, f can be used with a, and you don't need to use both).
-- I can either have a -c or not, and I can have either -g or -h, but not both.
--

-- zero or more flags
type Flags = Set Flag

-- Flags come in three groups
data Flag
        = F1 FAED
        | F2 C
        | F3 GH
    -- equality up to the first constructor. 

-- one of: -f or -a; -e; -d
data FAED
        = FA FA 
        | E
        | D

-- a type for: -f ; -a ; -f -a
data FA = F
        | A
        | FA

-- the -c flag
data C  = C

-- either -g or -h
data GH = G
        | H

言語をエンコードする方法は他にもありますが、構文ツリーを使用して言語を表現する方法を開始するには、これで十分です。

于 2012-06-04T13:44:10.197 に答える