このエントリーをはてなブックマークに追加

カルテットには、社員同士が交流を深める部活がいくつかあります。バレー部やテニス部といった運動系もあれば、(実際には投資をしない)投資部のようなインドアなものもあります。しかし、人見知りな私は、どの部活にも参加していません(汗) でも、プログラマならプログラミング技術を磨きたい! 部活で! というわけで、自分で「プログラミング部」を作り、中途入社したメンバーを半ば強引に誘って、二人で朝活スタイルの部活としてスタートし活動していました。

プログラミング部の活動は、私がプログラミング問題を選び、二人それぞれ問題を解くコードを書くというものです。ただし、問題を解くことだけをゴールとはせず、プログラマが問題をどのように理解したのか、どのような解き方なのかをコードに表現するという部分を中心に据えて取り組みます。なので、問題を解くコードを完成させるのにかかる時間よりも、コードについて議論し、話の展開に応じてその場でコードを書き換え、また議論するといった時間の方が圧倒的に長いというハードコアな部活です。

プログラミング部でもっともよく議論したポイントを一言でいうと、抽象化です。取り組んでいる問題を字面通りにコードに表現するのではなく、抽象化して捉え直したものを使うことで、コードの役割分担が明確になることがあります。今回は、朝活で取り上げた例を題材にして、問題を抽象化して捉え直す前と後での違いを紹介します。

数独とは

数独(別名ナンプレ、ナンバープレイス)は、魔方陣の一種で、一般的には下のように縦横9×9のマスに、ルールを満たすように1〜9の数字を埋めていくゲームです。すべてのマスに数字が埋まれば完成です。

image

満たさなければならないルールは単純です。

  • そのマスを含む行(横一列)内で、数字の重複がないこと
  • そのマスを含む列(縦一列)内で、数字の重複がないこと
  • 全体を縦横3分割にした9つの領域それぞれで、数字の重複がないこと

初期状態で、ある程度のマスには数字が埋められています。埋められた数字をヒントにしながら、残りの空白のマスの数字をルールに従って埋めていきます。当然ながら、初期状態で空欄が多い(つまりヒントが少ない)ほど解くのが難しくなります。Wikipediaの記述によれば、初期状態でヒントの数が16個以下のものは解法を持ちえないことが証明されているそうです。

数独チェッカー(簡易版)

今回は、数独のすべてのマスに数字を記入し終わった状態が、正解なのか不正解なのかを判定する部分のみを取り上げ、プログラムで実装します。状況を単純にするために、いくつかの不正状態は考慮しないことにします。この数独チェッカー(簡易版)に求められる要件は次のとおりです。

  • 9x9の数独で、すべてのマスに数字が入った状態が正解か不正解かを判定する
  • マスに空欄がある状況は考慮しなくてよい
  • マスには1から9の数字のみが入力される。これ以外の値の入力は考慮しなくてよい

このチェッカーにおけるチェックアルゴリズムの一例は、次のようになります。

  • すべての行について重複がないかチェックを実行し、1つでも重複があれば不正解
  • すべての列について重複がないかチェックを実行し、1つでも重複があれば不正解
  • すべての領域について重複がないかチェックを実行し、1つでも重複があれば不正解
  • 不正解が1つもなければ、正解

愚直に書いたコード

チェックアルゴリズムは単純なので、そのままコードにすることはそれほど難しくありません。行、列、領域ではマスの取り扱い方がやや異なるので、行用のチェック、列用のチェック、領域用のチェックを別々のメソッドで実装することにします。作成した Checker.php は次のようになります。

※チェック部分では、イレギュラーな数値は存在しない前提としています。

// Checker.php
class Checker
{
    public function check(array $data): bool
    {
        if ($this->checkRows($data) === false) return false;
        if ($this->checkColumns($data) === false) return false;
        if ($this->checkRanges($data) === false) return false;

        return true;
    }

    /**
     * すべての行をチェックする
     * @param array $data
     * @return bool
     */
    private function checkRows(array $data): bool
    {
        foreach ($data as $row) {
            if (count(array_unique($row)) !== 9) return false;
        }

        return true;
    }

    /**
     * すべての列をチェックする
     * @param array $data
     * @return bool
     */
    private function checkColumns(array $data): bool
    {
        for ($i = 0; $i < 9; $i++) {
            $colData = [];
            for ($j = 0; $j < 9; $j++) {
                $colData[] = $data[$j][$i];
            }
            if (count(array_unique($colData)) !== 9) return false;
        }

        return true;
    }

    /**
     * すべての領域をチェックする
     * @param array $data
     * @return bool
     */
    private function checkRanges(array $data): bool
    {
        for ($i = 0; $i < 9; $i++) {
            $checkData = [];
            for ($j = 0; $j < 3; $j++) {
                for ($k = 0; $k < 3; $k++) {
                    $row = (int)($i / 3) * 3 + $j;
                    $col = ($i % 3) * 3 + $k;
                    $checkData[] = $data[$row][$col];
                }

            }
            if (count(array_unique($checkData)) !== 9) return false;
        }

        return true;
    }
}

最初の状態のクラス図 最初の状態のクラス図

ここまでの段階で、コードにどのような問題があるのかを考えるのは難しいかもしれません。以降ではまず抽象化などによって問題を捉え直し、その結果を使ってコードを書き直します。そこまで考えを進めてから振り返ることで、コードの問題が浮かび上がります。

問題を捉え直す

最初のコードは極端に愚直に書いたものでした。そこにはただ1つの Checker というオブジェクトがあり、checkRows() checkColumns() checkRanges() というプライベートメソッドを使ってチェックを実現しているということしか表現されていません。整理の糸口をつかむために、まずは数独の世界に登場する他の要素もオブジェクトに加えてみましょう。そうすることで、自然と問題を細かく見ていくことになり分析が進む、というのが典型的なオブジェクト指向のアプローチです。

オブジェクトを使う

この記事の最初に載せた数独のビジュアルイメージからは、まず次の2つがオブジェクトの候補になりそうです。

  • Cell (セル:1つのマス)
  • CellMatrix (セルのマトリックス。数独の全体。)

次に、チェックアルゴリズムの記述では、行や列、領域といった言葉が登場していますので、これらもオブジェクト候補として検討に加えましょう。

  • Row (行:セルマトリックスにおける、横一列のセルの集まり)
  • Column (列:セルマトリックスにおける、縦一列のセルの集まり)
  • Range (領域:セルマトリックスを縦横3分割にした、個々の正方形部分)

これらのオブジェクトの名前を使って、チェックアルゴリズムを表現しなおしてみましょう。

  • すべての Row について Cell の値に重複がないかチェックを実行し、1つでも重複があれば false
  • すべての Column について Cell の値に重複がないかチェックを実行し、1つでも重複があれば false
  • すべての Range について Cell の値に重複がないかチェックを実行し、1つでも重複があれば false
  • 不正解が1つもなければ、true

CellMatrix が現れていませんが、チェックアルゴリズムを実行する前提として数独のデータが存在していなくてはならないため、これもオブジェクトとして妥当なものとします。 これらのオブジェクトを使って書き直したコードは特に載せませんが、チェックアルゴリズムの表現方法は最初のものとほとんど同じになりそうですよね。もう少し上手い表現方法はないでしょうか?

バリエーションのある部分から抽象化を検討する

問題やコードでバリエーションのある部分を上手く扱うことは、コード設計の重要な関心事の一つです。今回の問題では、どのあたりにバリエーションがありそうでしょうか?

チェックアルゴリズム内にあらわれる「行のチェック」「列のチェック」「領域のチェック」の部分に何かありそうですね。この3つのチェック処理で、具体的には何が異なっているのかを考えてみましょう。どのチェックでも、9つのマスを対象にし、9つのマスに入っている数字に重複がないということをチェックしています。これらは、3つのチェック処理の共通性です。逆に異なっているのは何でしょうか? 答えは、チェック処理の「対象とするデータ範囲の形状」です。これが、チェック処理における可変性です。

チェックアルゴリズムの共通性と可変性 共通性と可変性

この共通性を軸として抽象化を検討していきます。しかし、現段階ではまだ、この抽象を具体的にどのように扱うのかは定まっていません。実装イメージを持ちながら、順に検討していきましょう。

数学的な抽象を使う道

チェック対象とするデータのバリエーションである行、列、領域ですが、数学的に言えば、「行」と「列」のいずれも「領域」とみなすことができます。「行」は「縦が1マス、横が9マスの領域」であり、「列」は「縦が9マス、横が1マスの領域」だからです。この見方を採用すると、行や列という特化した表現は捨てて領域という表現に一本化できます。すると、チェック処理からバリエーションを取り除くことができそうですね。

この抽象を採用すると、Checker クラスのコードはどうなるでしょうか。チェック対象のデータは、「領域」という概念に一本化されます。Checker クラスにあるチェック用プライベートメソッドは checkRanges() だけが残ることになります。コード量が減って一見良さそうです。 しかし、checkRanges() メソッドのコードがチェック処理として本質的なのかどうか、疑問が残らないでしょうか。

データ抽象を使う道

今回のチェック処理で必要としている本質的なデータを考えてみます。数独のチェックに必要なのは、「9つのマスに1から9の数字が重複なく入っている」ということだけです。9つのマスの並びが行であっても列であっても領域であっても、このチェック内容を表現した文章はそのまま適用できます。つまり、チェック処理はマスの形状に依存しないということです。そうすると、チェック処理には「9つのマス(並び方は関係ない)」だけが渡されれば十分ですね。

このように、扱っているデータから、今着目している部分以外を取り除き、必要な部分に絞って取り扱う技法をデータ抽象と呼びます。

「並び方に依存しない9つのマス」を扱うために、次のような CellCollection クラスを用意します。実装を簡単にするために、LaravelのCollectionクラスを継承しています。

// CellCollection.php
use Tightenco\Collect\Support\Collection;

class CellCollection extends Collection
{
}

問題に表れる行、列、領域である Row Column Range は、基本的にはセルの集まりでもある(Row is a CellCollection)ため、CellCollection を継承するようにしておきます。

// Row.php
class Row extends CellCollection
{
}

アプリケーションのどこかで、盤面である CellMatrix から、行に対応する Row、列に対応する Column、領域に対応する Range が切り出されるものとします(後述)。 この3種類はどれも CellCollection を継承しています。Checker のチェックアルゴリズムが対象領域の形状に依存しないよう、CellMatrix だけを使って書き直してみます。

// Checker.php
class Checker
{
    /**
     * @var array|CellCollection[]
     */
    private $targets = [];

    /**
     * @param CellCollection $range
     * @return $this
     */
    public function addTarget(CellCollection $range)
    {
        $this->targets[] = $range;

        return $this;
    }

    /**
     * @return bool
     */
    public function check(): bool
    {
        foreach ($this->targets as $target) {
            if ($this->checkOneTarget($target) === false) return false;
        }

        return true;
    }

    /**
     * @param CellCollection $cellCollection
     * @return bool
     */
    private function checkOneTarget(CellCollection $cellCollection): bool
    {
        return $cellCollection->map(function($item, $key) {
            return $item->getNumber();
        })->unique()->count() === 9;
    }
}

最後に、CellMatrixChecker を構成するコードを App.php に記述します。数独の盤面の構造を表す CellMatrix の構造、および、Checker でチェックする行、列、領域の構造はアプリケーションのライフサイクルの中で変わることはないため、App.phpのコンストラクタに記述しています。

// App.php
class App
{
    /**
     * @var CellMatrix
     */
    private $cellMatrix;

    /**
     * @var Checker
     */
    private $checker;

    public function __construct()
    {
        $this->cellMatrix = new CellMatrix();
        $this->checker = new Checker();

        for ($i = 0; $i < 9; $i++) {
            // 行
            $row = $this->cellMatrix->getRow($i);
            $this->checker->addTarget($row);

            // 列
            $column = $this->cellMatrix->getColumn($i);
            $this->checker->addTarget($column);

            // 領域
            $left = (int)($i / 3) * 3;
            $top = ($i % 3) * 3;
            $range = $this->cellMatrix->getRange($left, $top, $left + 2, $top + 2);
            $this->checker->addTarget($range);
        }
    }
    // ...

これで一通りの修正が完了しました。修正前と修正後の Checker を比べてみてください。修正前のコードにどのような問題があったのかも浮かび上がっています。

  • 複数のチェックメソッドに重複して記述されていたチェック処理 → 一本化された
  • 行や列、領域といった詳細な事情(=対象となるセル群の形状に関する情報) → チェック処理から切り離された

修正後のクラス図 修正後のクラス図

CellCollection は、今回の問題空間におけるデータ抽象です。データ抽象を導入したことで、盤面の構造に関心のあるコードと、正解かどうかのチェックに関心のあるコードの接点が小さくなりました(情報隠蔽)。

  • 盤面の構造に関心のあるコード
    • Cell
    • CellMatrix
    • (CellCollection)
    • Row
    • Column
    • Range
  • 正解かどうかのチェックに関心のあるコード
    • CellCollection
    • Checker

おわりに

抽象化というのは、コード内で抽象クラスやインターフェイスを使うことだけを指すのではありません。問題の捉え方そのものに抽象化を使うことが本質です。そしてこのようにして見出した本質的な構造は、ある状況における問題の形態(Form)であり、それこそがソフトウェアの骨格を作るアーキテクチャとなっていくものだと思います。

そんなアーキテクチャを、たとえ小さな箇所においてでも見つけられることが、ソフトウェア設計の楽しさですよね。

参考:ジェームス・O・コプリン著『新装版 マルチパラダイムデザイン』


カルテット開発部では、抽象化に一家言ある仲間を募集しています!


このエントリーをはてなブックマークに追加

はじめに

この記事は型クラスの便利さについて分かち合う記事です。
理解が目的ではないので、なんとなくええやんと思ってもらえれば十分です。

型クラスのイメージ

型クラスとは主に関数型言語に実装されている機能の一つです。(※正確には知りません)

型クラスがあるとこんな関数を作ることができます。

※サンプルコードは全てscalaです。

def plus[A](left: A, right: A): A

どんな型でも足せてしまう関数・・・何だか良く分かりませんが凄そうですね!

どんな型でも足せてしまう関数の作り方

まず型クラス Plus[A] を作ります。

ソースのイメージはscalaです

trait Plus[A] {
  def plus(left: A, right: A): A
}

そしてどんな型でも足せてしまう関数 plus[A](A, A): A の実装を書きます。

def plus[A: Plus](left: A, right: A): A = implicitly[Plus[A]].plus(left, right)

完成です!
さすがにソースコード少なすぎでは?・・・何だか良く分かりませんが凄そうですね!

実行してみる

scala> plus(1, 2)
<console>:13: error: could not find implicit value for evidence parameter of type Plus[Int]
       plus(1, 2)
           ^
scala>

・・・コンパイルエラーで動きませんでした。どうやら完成というのは嘘だったようです。
エラーメッセージによると、 型クラス Plus[Int] の値が見つからなかったみたいですね。

Plus[Int] を作る

implicit val intPlus = new Plus[Int] {
  def plus(left: Int, right: Int) = left + right
}

Plus[Int]を作ってみました。Plus[A]Aの足し方を表しているようですね。

するとどうでしょう。

scala> plus(1, 2)
res1: Int = 3

今度はIntを足すことができました。
関数には手を加えていないので、関数が完成していたというのは嘘ではなかったようです。

もちろんPlus[String]Plus[Foo]を定義すれば、StringFooも足すことができるようになります。  

implicit val stringPlus = new Plus[String] {
  def plus(left: String, right: String) = left + right
}

scala> plus("foo", "bar")
res3: String = foobar

勘のいい人は気づいているかもしれませんが「どんな型でも足せる関数」plus[A](A, A): Aは、与えられた引数の型と一致するPlus[A]を利用する事で実現されています。
適切なPlus[A]を探し出す仕事はコンパイラがコンパイルタイムにやってくれるので、あのソースコードだけで成立できていたのです。

利点をもう少し具体的に挙げてみました。

  • 適切なPlus[A]を探し出す処理はコンパイラが頑張ってくれるので実装が不要
  • コンパイルタイムに適切なPlus[A]を探し出してくれるので、ランタイムにPlus[A]が見つからずにエラーになる可能性がない
  • つまり適切なPlus[A]が探し出される事のテストを書く必要もない

要はコンパイラがせっせと我々の代わりに働いてくれる訳です。
個人的には一種の自動化のように思えて気に入っています。実際に手を動かさなくて済むので楽ですし、良くないですか?

様々な型クラス

実は既に多くの素晴らしい型クラスが頭の良い人たちによって考案され公開されています。それらを提供しているライブラリの中でもscalaではscalazcatsがメジャーでしょうか。

例えば、今回の「AAの足し方」の他に「Aの空の値」が定義されている型クラスの場合はどうでしょう?

どんな型のリストでも合計値を導けるsum[A](items: List[A]): Aのような関数も作ることができたり、
どんな型でもn倍の値を導けるmultiply(value: A, n: Int): Aのような関数を作ることができます。

ちなみにsum[A](items: List[A]): Aは、さらに一般化する事でListを取り払いsum[M[_], A](xs: M[A]): Aとする事もできるらしいです。

このような関数の実装を可能にする型クラスはMonoid[A]として提供されていています。

scalazcatsは型クラスを利用した関数も多く提供されているので、インスタンスを準備するだけで良かったりします。

これはかなり簡単な部類なので、興味がある人は面白い発見があると思うのでぜひ他の型クラスについても調べてみてください。
sum[A](items: List[A]): Amultiply(value: A, n: Int): Aが実現できる理由が気になる人はMonoidでググってみましょう!


このエントリーをはてなブックマークに追加

オープン・クローズドの原則に則ってコードを書こうと思うとResolverクラスをよく使うことになると思います。

PHPerKaigi2018でベストトーク賞を受賞した @hidenorigoto「SOLIDの原則ってどんなふうに使うの?」 の最終形態である PHPカンファレンス関西2018で「続・SOLIDの原則ってどんなふうに使うの? オープン・クローズドの原則 センパイのコーディングノート編」 の発表中には IF文禁止ギブス なる言葉も飛び出しました :sweat_smile:
つまり、コードを書いていてIF分岐したくなった箇所はinterfaceに外出ししたうえで、Resolverで解決して使うことができるというわけです。

そのResolverクラスをPhpStormで楽に書くためのコードテンプレを作ったのでシェアします。

設定方法

PreferencesEditorFile and Code TemplatesFile+ で新しいテンプレートを追加。

_2018-09-11_13_16_06

  • Name: 任意。 PHP ResolverClass とか
  • Extension: .php (さすがにイマドキ .inc の人はいないと思いたいですが、いればそうしても良いかと)

テンプレートの内容

<?php

namespace ${NAMESPACE};

#set($TARGET=$NAME.replace('Resolver', ''))
#set($VARNAME_START = $TARGET.substring(0,1).toLowerCase())
#set($VARNAME_REST = $TARGET.substring(1))
#set($VARNAME=$VARNAME_START + $VARNAME_REST)
#set($PROPERTYNAME=$VARNAME + 's')

class ${NAME}
{
    /**
     * @var ${TARGET}Interface[]
     */
    private ${DS}${PROPERTYNAME} = [];

    public function add${TARGET}(${TARGET}Interface ${DS}${VARNAME})
    {
        ${DS}this->${PROPERTYNAME}[] = ${DS}${VARNAME};

        return ${DS}this;
    }

    public function resolve(${DS}target)
    {
        foreach (${DS}this->$PROPERTYNAME as ${DS}${VARNAME}) {
            if (${DS}${VARNAME}->supports(${DS}target)) {
                return ${DS}${VARNAME};
            }
        }

        throw new \LogicException('No $TARGET defined');
    }
}

コードテンプレートにPHP ResolverClassを登録

OK を押します。

使い方

Resolverクラスを作りたいディレクトリのコンテキストメニューを開き、 NewPHP Class を選びます。

ContextMenuからNew PHP Class

いつもの新規クラス作成画面ですが、 Template で先ほど追加した PHP ResolverClass が選べるようになっているので、これを選びます。

CreateNewPHPClassでTemplateとしてPHP ResolverClassを選ぶ

Nameに Resolverクラス名 を指定してOKします。

CreateNewPHPClassでnameにFooResolver TemplateにPHP ResolverClassを選んだところ

テンプレからResolverクラスが自動で作られました。

できあがりのFooResolver

あとは実際にFooInterfaceを書いて、FooInterface::supports() の引数に合わせてresolve($target)をちょちょっと調整すればResolverクラスが完成です。

楽ですね!