Day 28. 生命遊戲 - Store

17th鐵人賽 comonad store 生命遊戲 life game

olddunk

2025-09-28 07:24:51

41 瀏覽

分享至

使用Comonad類別的時機在於新值的產生要利用上下文的內容，生命遊戲裏，每個細胞的生與死由周圍細胞的活著個數決定；而影像處理在進行影像強化、影像模糊…等影像轉換時，都必須依賴每一像素周圍的值來計算新的影像，這兩者的情境都適合Comonad類別上場，今天就用Comonad類別的另一個模組Store來處理生命遊戲與影像處理。

Store

Store型別容器的定義如下：

interface Store<S, A> {
  readonly peek: (s: S) => A
  readonly pos: S
}

其中：

peek: 將型別 S 的狀態轉換成型別 A 的函數
pos : 當前的狀態
Store中的extract函數和extend函數定義如下：

const extract: <E, A>(wa: Store<E, A>) => A = (wa) => wa.peek(wa.pos)

const extend: <E, A, B>(f: (wa: Store<E, A>) => B) => (wa: Store<E, A>) => Store<E, B> = (f) => (wa) => ({
  peek: (s) => f({ peek: wa.peek, pos: s }),
  pos: wa.pos
})

Grid Store

現在開始實作今天的Grid Store，首先定義型別S是代表坐標[number, number]的元組，而Store則由下列函數產生：

const createGridStore = (matrix: number[][], pos: Pos): Grid => ({
  peek: ([x, y]) => matrix[y]?.[x] ?? 0, 
  pos,
});

extract(s: Grid)會取得矩陣中pos位置的值。

接下來我們要替matrix中的每個位置將它的九宮格鄰居的值放在一個陣列之中，所以函數neighbors的型別是Grid => number[]。

type Neighbors = ({ peek, pos }: Grid) => number[];
const neighbors: Neighbors = ({ peek, pos }) => {
  const [x, y] = pos;
  const mask = [-1, 0, 1];

  return pipe(
    mask,
    A.flatMap((dx) =>
      pipe(
        mask,
        A.map((dy) => [dx, dy])
      )
    ),
    /**
     * 上一步得到的陣列如下所示：
     * [
     *  [-1, -1], [-1,  0], [-1, 1]
     *  [ 0, -1], [ 0,  0], [ 0, 1]
     *  [ 1, -1], [ 1,  0], [ 1, 1]
     * ]
     */
    // A.filter(([dx, dy]) => !(dx === 0 && dy === 0)),
    A.map(([dx, dy]) => peek([x + dx, y + dy])) // 得到一個由pos位置周圍的值所成的一維陣列
  );
};

Rule型別則是Grid => number，可以做為extend的參數，這裏我們先給一個生命遊戲的規則，如果這個位置的生命是活的，而且鄰居有2個或3個活著，則這個位置繼續活著；如果這個位置是死的，但是鄰居有3個人活著，那這個位置也是活著；其它的情形，這個位置便會死去。

type Rule = (s: Grid) => number;
const lifeRule: Rule = (s) => {
  const alive = S.extract(s);
  const count = A.reduce(0, (a, b: number) => a + b)(neighbors(s));
  if (alive === 1 && (count === 3 || count === 4)) return 1;
  if (alive === 0 && count === 3) return 1;
  return 0;
};

我們的演化矩陣(evolve)會接受一個規則參數，然後回傳一個number[][] => number[][]的函數。

type Evolve = (rule: Rule) => (matrix: number[][]) => number[][];
const evolve: Evolve = (rule) => (matrix) => {
  const height = matrix.length;
  const width = matrix[0].length;
  return Array.from({ length: height }, (_, y) =>
    Array.from({ length: width }, (_, x) =>
      pipe(
        createGridStore(matrix, [x, y]), // 輸出是Grid型別
        S.extend(rule), // 根據規則, extend :: Grid -> Grid
        S.extract // 提取所在位置的值, extract :: Grid -> number
      )
    )
  );
};

最後要將矩陣的內容呈現在Terminal上，Render是number[][] => string型別的函數，我們先定義了一個Render型別的binaryRender函數。

type Render = (matrix: number[][]) => string;
const binaryRender: Render = (matrix) =>
  matrix
    .map((row) => row.map((cell) => (cell === 1 ? '⬜' : '⬛')).join(''))
    .join('\n');

然後定義我們的delay和forever函數。

const delay = (ms: number) => new Promise((r) => setTimeout(r, ms));

const forever = async (
  step: (iteration: number) => Promise<void>,
  ms: number,
  iteration: number = 0
): Promise<never> => {
  await step(iteration);
  await delay(ms);
  return forever(step, ms, iteration + 1);
};

最後是我們的主程式generateGrid，它需要一個Rule型別的參數和一個Render型別的參數，程式裏我們用readline模組從在Terminal中讀取鍵盤，我們還需要一個能產生一個只有0和1的矩陣的函數，以下是完整的程式碼。

const genRandomMatrix =
  (f: () => number) =>
  (width: number, height: number): number[][] =>
    pipe(
      A.replicate(height, undefined), // replicate height times
      A.map(() => pipe(A.replicate(width, undefined), A.map(f)))
    );

const randomMatrix = genRandomMatrix(() => (Math.random() < 0.3 ? 1 : 0))

const generateGrid =
  (rule: Rule) =>
  (render: Render): Task<void> =>
  async () => {
    const width = 30;
    const height = 15;
    let matrix = randomGrayMatrix(width, height);
    let paused = false;

    const rl = readline.createInterface({
      input: process.stdin,
      output: process.stdout,
    });

    readline.emitKeypressEvents(process.stdin, rl);
    if (process.stdin.isTTY) process.stdin.setRawMode(true);

    type AcceptedKey = 'p' | 'q' | 'r';
    const acceptedKeys = ['p', 'q', 'r'];
    const handleKeyPressed = {
      q: () => {
        rl.close();
        process.exit(0);
      },
      p: () => {
        paused = !paused;
      },
      r: () => {
        matrix = randomMatrix(width, height);
      },
    };

    process.stdin.on('keypress', (_, key) => {
      if (!key || !acceptedKeys.includes(key.name)) return;
      handleKeyPressed[key.name as AcceptedKey]();
    });

    await forever(async (gen) => {
      if (!paused) {
        console.clear();
        console.log(`Generation ${gen} — [p]ause [r]eset [q]uit`);
        console.log(render(matrix));
        matrix = evolve(rule)(matrix);
      }
    }, 1000);
  };

generateGrid(averageRule)(grayRender)();

將每個像素的值用周圍鄰居值的平均取代是影像處理常用的技巧，它可以我們的影像變得模糊，在這裏我們提供了averageRule、grayRender以及灰階值矩陣的函數(randomGrayMatrix)，可用來取代lifeRule、binaryRender和randomMatrix。

const averageRule: Rule = (s) =>
  pipe(
    neighbors(s),
    A.reduce(
      [0, 0] as [number, number],
      ([sum, count], v) => [sum + v, count + 1] as [number, number]
    ),
    ([sum, count]) => sum / count
  );
// 轉換 0–127 至 ANSI 灰階顏色碼 232–255
const valueToColorCode = (v: number): number =>
  232 + Math.floor((v / 127) * 23);

const reset = '\x1b[0m';

const grayRender: Render = (matrix) =>
  pipe(
    matrix,
    A.map((row) =>
      pipe(
        row,
        A.map((v) => {
          const color = valueToColorCode(v);
          return `\x1b[48;5;${color}m  ${reset}`;
        }),
        (rowStr) => rowStr.join('')
      )
    )
  ).join('\n');

const randomGrayMatrix = genRandomMatrix(() => randomInt(0, 127));

\x1b[48;5;${color}m ${reset}這一段字串的解釋如下：

\x1b → 逃脫字元（ASCII 碼 27），它告訴終端機：“接下來是控制序列，而不是一般文字。”。
[ → 控制序列導引字符(Control Sequence Introducer, CSI).
48 → 設定背景顏色
; → 分隔符號
5 → 使用256顏色模式
m → 終止符號

以上是今日全部的程式碼，有興趣的朋友可以試試，看看像素的變化，你也可以設計別的Rule來，看看有什麼不同的效果。

今日小結

利用上下文計算的情境在時間序列的問題常常遇到，在機器學習的領域中，LSTMI(Long Short-Term Memory)，RNN的類神經網路架構，甚至是Transformer都有上下文計算的情境中，相信Store或Comonad類別都有發揮的機會。希望今天分享的內容能讓你對Store初步的認識，也能對Comonad這個類別及其相關的函數(extract, extend)有更熟悉的感覺。

今天分享的內容就到這裏，明天再見。