平衡二分探索木を優先度付きキューとして使う

.NET 6 では、優先度付きキューを表す PriorityQueue<TElement,TPriority> クラスが基本クラスライブラリ (BCL) に追加されました。
言い換えると、.NET 5 以前の BCL には優先度付きキューが存在しません。
そこで、.NET 5 以前の環境において、平衡二分探索木のクラスを利用して優先度付きキューに相当する処理を実現する方法を考えてみます。

優先度付きキューの要件

まず、優先度付きキュー (priority queue) に必要な機能を整理します:

  • Count: 現在の要素の数を取得する
  • Peek: 優先度が最も高い要素を取得する。削除はしない
  • Pop: 優先度が最も高い要素を取得し、同時に削除する
  • Push: 新たな要素を追加する

すなわち、初めから全ての要素がわかっている (静的データ) とは限らず、要素の動的な追加に対応します。
また、オプション機能として次のものが考えられます:

  • 一般的に、要素の重複を許す
  • 昇順・降順を指定できる
  • 要素に対して、優先度を表すキーを指定できる

例えば、1組の生徒たち、2組の生徒たち、・・・のような順でデータを取得する要件に対応するには、優先度を表すキーを指定できる機能があると便利です。

平衡二分探索木に関連するクラス

ここでは、.NET 5 以前の BCL に存在する平衡二分探索木およびその周辺のクラスについてまとめます。
以下の3種類があり、「追加した要素が自動的にキーの順序でソートされる」「キーの重複は不許可」という点はこれらに共通です。
なお、SortedList<TKey,TValue> クラスは平衡二分探索木ではありません (以降の節では使いません)。

(1) SortedSet<T> クラス

  • 要素をキーとして使用する
  • 要素の動的な追加および削除の時間計算量は O(log n)
  • HashSet<T> が順序付きになったと考えてよい

(2) SortedDictionary<TKey,TValue> クラス

  • キーと値のペアを格納する
  • 要素の動的な追加および削除の時間計算量は O(log n)
  • Dictionary<TKey,TValue> が順序付きになったと考えてよい

(3) SortedList<TKey,TValue> クラス

  • キーと値のペアを格納する
  • 通常のリストのような構造であり、空間計算量は O(n)
    • 平衡二分探索木ではない
  • 要素の動的な追加および削除の時間計算量は O(n)
  • キーからインデックスの取得、インデックスから要素の取得の時間計算量は O(log n)
  • ソート済みの静的データで初期化するだけの場合や、末尾にくるデータを追加するだけであれば速い

実装

では、平衡二分探索木を利用して、優先度付きキューを実装していきます。
要件に合わせて以下の3種類を用意しました。

(1) 要素を重複させない場合

  • SortedSet<T> をほぼそのまま利用する
  • Min プロパティおよび Add, Remove メソッドを呼び出せばよい

(2) 要素の重複を許す場合 (一般的な優先度付きキュー)

  • SortedDictionary<T, int> を利用する
  • 要素ごとの個数を管理する

(3) 要素に対して優先度を表すキーを指定する場合 (重複を許可)

  • SortedDictionary<TKey, Queue<T>> を利用する
  • キーごとにキューで要素を管理する

ソースコードは次の通りです。言語は C# です。
なお、降順を指定するには、前回の記事で作成した補助クラスで IComparer<T> を生成すればよいです。

using System;
using System.Collections.Generic;
using System.Linq;
namespace AlgorithmLab.DataTrees
{
// 要素が重複しない (すべての値の順序が異なる) 場合に利用できます。
public class DistinctPriorityQueue<T>
{
// 要素をそのままキーとして使用します。
SortedSet<T> ss;
public DistinctPriorityQueue(IComparer<T> comparer = null)
{
ss = new SortedSet<T>(comparer ?? Comparer<T>.Default);
}
public int Count => ss.Count;
public T Peek()
{
if (ss.Count == 0) throw new InvalidOperationException("The container is empty.");
return ss.Min;
}
public T Pop()
{
if (ss.Count == 0) throw new InvalidOperationException("The container is empty.");
var item = ss.Min;
ss.Remove(item);
return item;
}
public bool Push(T item) => ss.Add(item);
}
// 要素が重複する場合も利用できます (一般的な優先度付きキュー)。
public class BstPriorityQueue<T>
{
// 要素をそのままキーとして使用します。
SortedDictionary<T, int> sd;
public BstPriorityQueue(IComparer<T> comparer = null)
{
sd = new SortedDictionary<T, int>(comparer ?? Comparer<T>.Default);
}
public int Count { get; private set; }
public T Peek()
{
if (Count == 0) throw new InvalidOperationException("The container is empty.");
return sd.First().Key;
}
public T Pop()
{
if (Count == 0) throw new InvalidOperationException("The container is empty.");
Count--;
var (item, count) = sd.First();
if (count == 1) sd.Remove(item);
else sd[item] = count - 1;
return item;
}
public void Push(T item)
{
Count++;
sd.TryGetValue(item, out var count);
sd[item] = count + 1;
}
}
// 要素に対して優先度を表すキーを指定する場合に利用します。
public class KeyedPriorityQueue<T, TKey>
{
SortedDictionary<TKey, Queue<T>> sd;
Func<T, TKey> keySelector;
public KeyedPriorityQueue(Func<T, TKey> keySelector, IComparer<TKey> comparer = null)
{
this.keySelector = keySelector ?? throw new ArgumentNullException(nameof(keySelector));
sd = new SortedDictionary<TKey, Queue<T>>(comparer ?? Comparer<TKey>.Default);
}
public int Count { get; private set; }
public T Peek()
{
if (Count == 0) throw new InvalidOperationException("The container is empty.");
return sd.First().Value.Peek();
}
public T Pop()
{
if (Count == 0) throw new InvalidOperationException("The container is empty.");
Count--;
var (key, q) = sd.First();
if (q.Count == 1) sd.Remove(key);
return q.Dequeue();
}
public void Push(T item)
{
Count++;
var key = keySelector(item);
if (!sd.TryGetValue(key, out var q)) sd[key] = q = new Queue<T>();
q.Enqueue(item);
}
}
}

また、平衡二分探索木を利用する利点として、優先度の高いほうだけでなく、両側に対する優先度付きキューを実現できることが挙げられます。
PopFirst, PopLast メソッドとして作成すればよいでしょう。

利用例

(1) DistinctPriorityQueue

(2) BstPriorityQueue

(3) KeyedPriorityQueue

前回: ソート用の比較関数の補助クラス

作成したサンプル

検証したバージョン

  • C# 8.0
  • .NET Standard 2.1

参照

ソート用の比較関数の補助クラス

.NET で配列やコレクションをソートするときに、ソートの条件を指定する方法がいくつかあります。
今回はそれらを一通り調べ、さらにソート条件の指定を補助するためのクラスを作成しました。

既存ライブラリのまとめ

まず、配列やコレクションをソートするために呼び出す主なメソッドを挙げてみます。

そして、これらのメソッドのオーバーロードでソートの条件を指定する方法をまとめると、次のようになります。

  • IComparable<T>
    • 対象となる型 T が IComparable<T> インターフェイスを実装している場合、引数を指定しなくてもソート可能
    • ただし、これだけでは降順にできない
  • Comparison<T> または Func<T, T, int>
    • 引数 (x, y) に対し、次の値を返す比較関数
      • x が小さいならば、負の値
      • 等しいならば、0
      • x が大きいならば、正の値
  • IComparer<T>
  • TKey[]
    • 各要素に対応するキーの配列
    • キーの型が IComparable<TKey> インターフェイスを実装していることが必要
  • Func<T, TKey> によるキーの指定、および昇順・降順の指定
    • LINQ の Enumerable.OrderBy メソッドなど
    • 第2キー以降を指定するには Enumerable.ThenBy メソッドなど
    • キーの型が IComparable<TKey> インターフェイスを実装していることが必要

課題と解決策

普段これらを使っていると、次のような実感があります。

  • 対象となる型 T が IComparable<T> インターフェイスを実装しており、その昇順でソートしたい場合は、引数のないオーバーロードを呼び出すだけであり簡単
  • それ以外の少し複雑な条件の場合、LINQ のように、Func<T, TKey> によりキーを指定したいことが多い
    • しかし、このオーバーロードは用意されていないことが多い
  • IComparer<T> オブジェクトを引数に指定するオーバーロードであれば、だいたいどのソート関数でも備えている

そこで、「Func<T, TKey> によるキーの指定、および昇順・降順の指定」から IComparer<T> オブジェクトを生成するためのヘルパー クラスを作成しました。言語は C# です。

using System;
using System.Collections.Generic;
namespace AlgorithmLab.DataTrees
{
public static class ComparerHelper
{
public static IComparer<T> GetDefault<T>()
{
// カルチャに依存しない場合に高速化します。
if (typeof(T) == typeof(string)) return (IComparer<T>)StringComparer.Ordinal;
return Comparer<T>.Default;
}
public static IComparer<T> ToDescending<T>(this IComparer<T> c)
{
if (c == null) throw new ArgumentNullException(nameof(c));
return Comparer<T>.Create((x, y) => c.Compare(y, x));
}
}
// クラスに型引数を指定することで、Create メソッドを呼び出すときに型引数 <T, Tkey> の指定を省略できます。
public static class ComparerHelper<T>
{
public static IComparer<T> Create(bool descending = false)
{
var c = ComparerHelper.GetDefault<T>();
return descending ? c.ToDescending() : c;
}
public static IComparer<T> Create<TKey>(Func<T, TKey> keySelector, bool descending = false)
{
if (keySelector == null) throw new ArgumentNullException(nameof(keySelector));
var c = ComparerHelper<TKey>.Create(descending);
return Comparer<T>.Create((x, y) => c.Compare(keySelector(x), keySelector(y)));
}
public static IComparer<T> Create<TKey1, TKey2>(Func<T, TKey1> keySelector1, bool descending1, Func<T, TKey2> keySelector2, bool descending2)
{
if (keySelector1 == null) throw new ArgumentNullException(nameof(keySelector1));
if (keySelector2 == null) throw new ArgumentNullException(nameof(keySelector2));
var c1 = ComparerHelper<TKey1>.Create(descending1);
var c2 = ComparerHelper<TKey2>.Create(descending2);
return Comparer<T>.Create((x, y) =>
{
var d = c1.Compare(keySelector1(x), keySelector1(y));
if (d != 0) return d;
return c2.Compare(keySelector2(x), keySelector2(y));
});
}
}
}
using System;
using AlgorithmLab.DataTrees;
namespace ConsoleApp1
{
class Program
{
static void Main(string[] args)
{
var a = new[] { 3, 14, 1, 592, 65, 358 };
// 文字数の降順、値の昇順
// 結果: { 358, 592, 14, 65, 1, 3 }
Array.Sort(a, ComparerHelper<int>.Create(x => x.ToString().Length, true, x => x, false));
}
}
}
view raw Program.cs hosted with ❤ by GitHub

これにより、LINQ 以外の場面でソートするときも、LINQ とほぼ同様の記述方法でキーを指定できるようになりました。

次回: 平衡二分探索木を優先度付きキューとして使う

作成したサンプル

検証したバージョン

  • C# 6
  • .NET Standard 2.0

参照

カテゴリー: .NET Core, .NET Framework. タグ: . 1 Comment »

経営で MVV と呼ばれているものの出典

// 積ん読してしまう人のための Advent Calendar 2021 の 7 日目の記事です。

経営の世界で「Mission, Vision and Values (MVV)」と言われているものがあります。
一部の日本企業の Web サイトの会社概要や企業理念のページを閲覧すると、

  • ミッション
  • ビジョン
  • バリュー

と、まるで定型のように項目が並んでいるのをよく見かけると思いますが、これのことです。
この記事では、MVV と呼ばれている経営テンプレートの出典を確認していきます。

MVV の出典

この MVV は、「ドラッカーが提唱した MVV」として紹介されることが多いようです。
「ドラッカー MVV」などで検索すると、この内容について最近書かれたと思われる記事がたくさんヒットします。
経営コンサルタントによる記事も多く含まれています。
そしてそれらの記事では、MVV の出典として書籍「ネクスト・ソサエティ」または「ドラッカー5つの質問」が挙げられています。

しかし結論から言ってしまうと、実際に書籍を調べたところ、それらの記事に書かれた内容とは異なるものでした。
Web 上には、とてもこれらの出典を読解したとは思えない、勝手に枝葉を付け足して独り歩きした記事が並んでいます。
さらに、原文をそのまま引用しない (改変している)、ルールに反した記事も非常に多いです。
経営に興味のある人は、これまでに二次情報源で得た言説は一切忘れて、一次情報源である「ネクスト・ソサエティ」「ドラッカー5つの質問」をお読みください。

以下では、これらの書籍を調べた結果を具体的に列挙していきます。

「ネクスト・ソサエティ」 (2002年5月)

  • 「価値、使命、ビジョンの確立」(第1部 第6章より)
    • 原文では「its social legitimacy: its values, its mission, its vision」
    • 注) values の訳は「価値」ではなく「価値観」とするのがよい
  • この節の見出しである「組織としての個の確立」を言い換えたもの
  • この記述があるだけで、他にこの内容に関する詳しい説明があるわけではない

書籍全体を見ても経営手法を深掘りした書籍ではなく、この記述だけを見て「経営理念ステートメントのテンプレートとして使おう」と考えるのは無理があります。おそらく著者がこの文を書いた時点では、テンプレート化されることを意図していないでしょう。

「ドラッカー5つの質問」 (2017年12月)

  • 著者はドラッカーではない (日本語の書籍)
  • 「経営理念、ミッション、ビジョン」(第1の質問より)
  • おそらくこれら3つの順番は重要
  • テンプレートとして使えるようにはなっているが、単にこれら3つを並べた形式ではない
  • この章の主題はミッション
  • 「経営理念」は「根本的な考え」「想い」と説明されており、values に近い

この書籍を MVV の出典と考えるのであれば、「ドラッカーが提唱した MVV」とするのは誤りです。
書籍全体を見ると、5章からなる経営テンプレートとなっており、ステートメントを作るためというよりは、何が大事なのかを自分たち自身に問うためのテンプレートとなっています。

なお、同じ章で次のように定義されています。

  • 経営理念:わが社の社会に対する根本的な考え
  • ミッション:わが社が社会で実現したいこと
  • ビジョン:わが社のミッションが実現した時の状態

この章の主題となっているミッションについては後述します。

調査結果

結論として、「ネクスト・ソサエティ」「ドラッカー5つの質問」においてそれらしい表現が登場するものの、これらを MVV の出典と考えるのは無理があると考えています。
英語の記事も調べましたが、日本語の記事に現れるようなテンプレート化はされていません。
なお、values (価値観) と value (価値) では意味が若干異なります。
原文では values ですが、二次情報源では value に変化していることが多いです。

日本語の記事の中でも数少ない、まともな書評記事がこちらでした。
> 「経営理念」と「ミッション」と「ビジョン」はどう違う? 「ドラッカー5つの質問」が教えてくれること
ただし、やはりこの章の主題はミッションであることに注意が必要です。

ついでに、これらの書籍と内容の近い「経営者に贈る5つの質問 第2版」「ビジョナリー・カンパニー」も調べてみました。

「経営者に贈る5つの質問 第2版」 (2017年9月)

  • 「ドラッカー5つの質問」に近い内容の経営テンプレート
  • 「ネクスト・ソサエティ」の文脈とはおそらく関連がない
  • 「ビジョン」は、用語としては登場するがキーワードとして深掘りされてはいない

「ビジョナリー・カンパニー」 (1995年9月)

  • 基本理念 (core ideology) =基本的価値観+目的
  • 「目的」は「存在理由」と説明されており、mission に近い

出典についての検証は以上です。

ミッション

書籍「経営者に贈る5つの質問」「ドラッカー5つの質問」ではともに、ミッションの重要性についての記述が目立ちます。
そこで、これらの書籍における「ミッション」をまとめてみます。

ミッションは自らの行動を表すものであり、社会に起因するもの (地域、業界、顧客) と自己に起因するもの (価値観、専門性、存在意義、生き甲斐、楽しさ、誇り) の両方により構成されると考えられます。
そしてミッションにより、組織の個性、自分たちらしさを明確にします。
また、価値観およびミッションは、既に心の中にあるもの、あるいはこの先ずっと信じられるものから抽出します。

それぞれの書籍で、ミッションを構成する3つの要素が挙げられています。

  • 機会:社会のニーズに合っているか
  • 能力:われわれの専門性に合っているか
  • 意欲:われわれの価値観に合っているか

ビジョンについては、いずれの書籍でも「ミッションが実現したときの姿」と書かれており、ミッションが決まるとほぼ自明に決まる、という印象を受けました。実際、ミッションとビジョンにほぼ同じことが書かれている企業は多いです。
また、ミッションが行動を表すのに対し、ビジョンは成果を表すものであり、自分たちらしさを示す要素が薄くなるでしょう。

ドラッカー周辺の書籍をいくつか読んだ結果として、もし企業理念について何らかのテンプレート化をしたいのであれば、

  • 価値観 (Values)
  • ミッション (Mission)

とするのがより妥当であると考えています。

参照

カテゴリー: 経営. タグ: . Leave a Comment »

C# で演算子を実装する (6)

前回の記事では、論理演算子のオーバーロードについて説明しました。
今回は補足として、その他の注意点や設計について書いていきます。

タプル型との相互変換

C# 7.0 以降の機能で、ユーザー定義型でも Deconstruct メソッドを追加することにより、タプル型と同様に分解を利用できます (後付けの拡張メソッドでも可)。次のコードは、タプル型とのキャスト演算子と Deconstruct メソッドにより、ユーザー定義の構造体をタプル型に近い形で扱うことを目指した実装例です。

namespace OperatorsLib.Structs
{
public struct Vector2
{
public double X { get; }
public double Y { get; }
public Vector2(double x, double y) => (X, Y) = (x, y);
public void Deconstruct(out double x, out double y) => (x, y) = (X, Y);
public static implicit operator Vector2((double x, double y) v) => new Vector2(v.x, v.y);
public static explicit operator (double, double)(Vector2 v) => (v.X, v.Y);
}
}
view raw Vector2.cs hosted with ❤ by GitHub
using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using OperatorsLib.Structs;
namespace UnitTest.Structs
{
[TestClass]
public class Vector2Test
{
[TestMethod]
public void Cast()
{
Vector2 v = (3, 4);
var (a, b) = v;
var t = ((double c, double d))v;
Assert.AreEqual(v, (a, b));
Assert.AreEqual(v, t);
Assert.AreEqual((v.X, v.Y), (t.c, t.d));
}
}
}
view raw Vector2Test.cs hosted with ❤ by GitHub

KeyValuePair

(1) のタプル型など の補足となりますが、タプル型 (ValueTuple) が登場する以前は、2つの値を値型で保持するために KeyValuePair<TKey,TValue> 構造体を使うことがありました。この KeyValuePair<TKey,TValue> には等値演算子のオーバーロードも Equals メソッドのオーバーライドもないため、いちおう Equals メソッドで Key および Value に対する等価比較はできるもののパフォーマンスは最適化されていません。

なお、最近のバージョンの基本クラスライブラリでは KeyValuePair<TKey,TValue> に Deconstruct メソッドが追加されているため、
例えば Dictionary<TKey,TValue> の要素を列挙するときに次のように分解を利用できます。

[TestMethod]
public void KeyValuePair_Deconstruct()
{
var d = Enumerable.Range(1, 100).ToDictionary(i => i, i => i / 2.0);
foreach (var (i, value) in d)
Console.WriteLine($"{i} {value}");
}
view raw Vector0Test.cs hosted with ❤ by GitHub

ValueType のような抽象クラスを作る

(1) の記事で、構造体は暗黙的に ValueType クラスを継承するため最初から Equals メソッドでフィールドごとの等価性評価ができると書きました。
これのクラス版で、パフォーマンスは気にしないけど簡単な実装で等値演算を備えたクラスを実装したいという場合、
ValueType と同様にリフレクションでフィールドごとの等価性評価をする抽象クラスを次のコードで作ることができます。
なお、ValueType クラスを直接継承することはできません。

using System;
using System.Reflection;
namespace OperatorsLib.Classes
{
public abstract class EquatableObject
{
// ValueType と同様に、すべてのフィールドで等価性を評価します。
public override bool Equals(object obj)
{
var type = GetType();
if (type != obj?.GetType()) return false;
foreach (var field in type.GetFields(BindingFlags.Instance | BindingFlags.Public | BindingFlags.NonPublic))
if (!Equals(field.GetValue(this), field.GetValue(obj))) return false;
return true;
}
public override int GetHashCode()
{
HashCode hc = default;
foreach (var field in GetType().GetFields(BindingFlags.Instance | BindingFlags.Public | BindingFlags.NonPublic))
hc.Add(field.GetValue(this));
return hc.ToHashCode();
}
}
}
namespace OperatorsLib.Classes
{
public class VectorEq : EquatableObject
{
public double X { get; }
public double Y { get; }
public VectorEq(double x, double y) => (X, Y) = (x, y);
}
}
view raw VectorEq.cs hosted with ❤ by GitHub

構造体の既定のコンストラクター

主に (3) の記事への補足です。
構造体では引数付きのコンストラクターを追加しても、引数のない暗黙的な既定のコンストラクターの存在が残ります。
構造体の既定のコンストラクターは、既定値 default(T) を得るために使われます (クラスにおいては null に相当)。
開発者が明示的に既定のコンストラクターを宣言することはできません。

構造体では、この暗黙的な既定のコンストラクターが呼び出されるときはすべてのフィールドが型の既定値で初期化されます。
したがって、明示的なコンストラクターと暗黙的なコンストラクターの間で齟齬が発生しないように注意しなければなりません。
例えば、明示的なコンストラクターの中で、引数で渡された値を単純にフィールドに設定することの他に何らかの処理がある場合や、
0 や null などの既定値を不正 (invalid) な値として扱っている場合、
値が必要になったら計算してキャッシュさせるために -1 や NaN で初期化する場合などが該当します。

次のコードは Norm とAngle を初期化時に計算して設定している2次元ベクトルの例です。
すべてのプロパティの値が 0 でも問題なく使えることが期待されます。

using System;
namespace OperatorsLib.Structs
{
public struct VectorInit
{
public double X { get; }
public double Y { get; }
public double Norm { get; }
public double Angle { get; }
// ctor() と ctor(0, 0) の結果が同等になる必要があります。
public VectorInit(double x, double y)
{
(X, Y) = (x, y);
Norm = Math.Sqrt(X * X + Y * Y);
Angle = Math.Atan2(Y, X);
}
}
}
view raw VectorInit.cs hosted with ❤ by GitHub

演算子の優先順位

演算子が実行される優先順位は C# 演算子と式 (C# リファレンス) に載っています。
優先順位の低い演算を先に実行するには、丸括弧 () で囲みます。この表はなかなかすべて覚えられるものではないため、
優先順位が高くてもあまり馴染みのない演算の組合せの場合には丸括弧で囲むことがあります。
Visual Studio などのエディターに省略を推奨されるのであれば丸括弧を省略してよいでしょう (下図で丸括弧が灰色になっています)。
とくに省略を推奨されない (どちらでもよい) 組合せもあります。

VS-Precedence

前回: C# で演算子を実装する (5)

作成したサンプル

バージョン情報

  • C# 8.0
  • .NET Standard 2.1
  • .NET Core 3.1

参照

C# で演算子を実装する (5)

前回の記事では、キャスト演算子、インデクサーなどについて説明しました。
今回は論理演算子を扱います。

ユーザー定義型で直接オーバーロードできる論理演算子には、!, &, ^, | さらに true および false 演算子があります。
ただし整数型においては、&, ^, | はビット演算を表します。
また、否定 ! は、整数のビット演算においては補数 ~ に相当します。

論理演算については、bool 型や bool? 型の状態で扱えば実務上は事足りることが多く、ユーザー定義型でこれらの演算子をオーバーロードして使う機会はあまりないと思います。
そこで、今回は && および || 演算子による短絡評価 (ショート サーキット) を検証してみました。

短絡評価 (ショート サーキット)

ユーザー定義型で && および || 演算子による短絡評価を利用するには、次の条件を満たす必要があります。

  • & および | について、2つの引数と戻り値の型はすべて、定義元の型
  • true および false 演算子が宣言されている

そしてこのとき、x && y は x が偽を表すならば y には何もせず x を返し、そうでなければ x & y を評価します。
形式的に書くと T.false(x) ? x : (x & y) のようになります。
同様に、x || y は x が真を表すならば y には何もせず x を返し、そうでなければ x | y を評価します。
形式的に書くと T.true(x) ? x : (x | y) のようになります。

bool 型における短絡評価も上記の法則に従っていると見なすことができ、短絡評価の概念を bool 型以外に拡張したことになります。
なお、bool? 型では && および || 演算子を利用できません。

さて、上記の仕組みから考えると、短絡評価を適用できる論理体系とは、x と y のうち1つ以上が偽を表すのであれば x & y も偽を表し、x と y のうち1つ以上が真を表すのであれば x | y も真を表すものである必要があります。
これは、真・偽のほかに第3の値の存在を考える3値論理で体系を構成する場合、クリーネの3値論理に相当します。
bool? 型における論理演算 (!, &, ^, |) もこのクリーネの3値論理に従います。
3値論理については記事の後半で補足します。

実装例

今回の実装例では、与えられた文字列が真を表すのか、偽を表すのか、それ以外かの3値を判定する構造体を作成し、各論理演算子をオーバーロードしています。
以下にソースコードを示します。

namespace OperatorsLib.Structs
{
public struct StringBool
{
public static StringBool True { get; } = bool.TrueString;
public static StringBool False { get; } = bool.FalseString;
public static StringBool Unknown { get; } = null;
// bool? として持つこともできますが、この例ではあえて論理演算を自作します。
public string Value { get; }
public bool IsTrue => bool.TryParse(Value, out var b) && b;
public bool IsFalse => bool.TryParse(Value, out var b) && !b;
public bool IsUnknown => !bool.TryParse(Value, out var _);
public StringBool(string value) => Value = value;
public override string ToString() => Value ?? "Unknown";
public static implicit operator StringBool(string v) => new StringBool(v);
public static explicit operator bool?(StringBool v) => v.IsUnknown ? default(bool?) : v.IsTrue;
public static bool operator true(StringBool v) => v.IsTrue;
public static bool operator false(StringBool v) => v.IsFalse;
public static StringBool operator !(StringBool v) => v.IsUnknown ? Unknown : v.IsTrue ? False : True;
public static StringBool operator &(StringBool v1, StringBool v2) => v1.IsFalse || v2.IsFalse ? False : v1.IsUnknown || v2.IsUnknown ? Unknown : True;
public static StringBool operator ^(StringBool v1, StringBool v2) => v1.IsUnknown || v2.IsUnknown ? Unknown : v1.IsTrue ^ v2.IsTrue ? True : False;
public static StringBool operator |(StringBool v1, StringBool v2) => v1.IsTrue || v2.IsTrue ? True : v1.IsUnknown || v2.IsUnknown ? Unknown : False;
}
}
view raw StringBool.cs hosted with ❤ by GitHub

コンストラクターの処理で bool? に変換することもできますが、この例ではあえて Value プロパティで入力の文字列を保持することとし、論理演算を自作しています。上記のように実装することで、下記のコードのように短絡評価を使えるようになります。

[TestMethod]
public void Tables()
{
StringBool t = "true";
StringBool n = "force";
StringBool f = "false";
var s = new[] { t, n, f };
// 真理値表を作成します。
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
Console.Write($"{s[i] && s[j],-8}");
}
Console.WriteLine();
}
Console.WriteLine();
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
Console.Write($"{s[i] || s[j],-8}");
}
Console.WriteLine();
}
}

このコードにより、下図のような真理値表が得られます。
短絡になったケースは小文字始まりで表示されています。

StringBool-Tables

クリーネの3値論理

情報技術で多く使われているクリーネの3値論理における、真でも偽でもない3つ目の値 (C# では bool? 型の null) とは、「真でも偽でもない、もう一つの異なる固定値」ではなく「本来は真または偽の値を持つが、現在はわかっていない状態」と考えたほうが意味論的には理解しやすいと思います。
(命題論理の考え方については、以前に命題論理を実装する (C#) という記事で書きました。)

そこで、null の代わりに unknown という名前を使うことにします。
具体例として、unknown & false は、左側のオペランドが実際に true とわかっても false とわかっても式全体では false であることが確定しています。また、unknown & true は、左側のオペランドが true とわかるか false とわかるかで式全体の結果が変わるため現在は unknown です。すると、x & y が現時点で true と確定するのは x と y がともに true のときだけです。
残りの !, ^, | についても同様に考えて体系を構成できます。

bool? 型における論理演算もこれと同じになります。
演算結果の真理値表はなかなか丸暗記できないと思いますが、上記のように短絡評価と関連付けることで導けるようになるはずです。

また、== および != 演算子を等価性ではなく命題論理における同値性として扱いたい場合、これらの演算子の戻り値の型を bool ではなく定義元の型とし、x == y!(x ^ y) と同じ意味に、x != yx ^ y と同じ意味になるようにオーバーロードします。

もし null を unknown ではなく「もう一つの異なる固定値」と考えて「一方が null ならば x & y は null」のような体系を立てる場合であっても、各論理演算子をオーバーロードすれば実現できるでしょう。ただし、短絡評価はできません。

制御条件式

true 演算子が宣言されていることで、if ステートメントなどにおける制御条件式として if (obj) のように使えます。
また、true 演算子の代わりに bool 型への暗黙的型変換を宣言することででも、制御条件式として使えるようになります。
両方を宣言した場合は、この暗黙的型変換が優先されるようです。

public static implicit operator bool(StringBool v) => v.IsTrue;

次回はその他の注意点や設計についてです。

前回: C# で演算子を実装する (4)
次回: C# で演算子を実装する (6)

作成したサンプル

バージョン情報

  • C# 8.0
  • .NET Standard 2.1
  • .NET Core 3.1

参照