tkykmw code

学びたいことを学ぶ

アンダースタンディング・コンピュテーション6.1.10まで

後半、説明が飛ばし飛ばしでややわかりにくいので、補足を試みる。

リストの作り方

PAIRが入れ子になっていることへの説明がないので、混乱する。要は、リストの一つの要素を、3つのフィールドで構成しているのだ。

  • リストの末尾かどうか判定するフラグ
  • 値へのポインタ
  • 次の要素へのポインタ

lispでいう nil に相当する値を表現するのに、一番目のフィールドを使っている。

FOLD

RubyEnumerable#inject に似ていると書いてあるが、違いが説明されていない。

違いは、inject が先頭から処理する(fold-left)のに対して、FOLD は末尾から処理する(fold-right)。

inject 相当のfold-leftも書ける。

FOLD_LEFT = Z[-> f {
  -> l { -> x { -> g {
    IF[IS_EMPTY[l]][
      x
    ][
      -> y {
        f[REST[l]][g[x][FIRST[l]]][g][y]
      }
    ]
  }}}
}]

一見、先頭から処理した方が直感的に思われるが、UNSHIFT と組み合わせて新たなリストを作るとき、先頭からの処理だと逆順になってしまう。もっとも、それを利用すればreverseを作ることもできるが。

REVERSE = -> l { FOLD_LEFT[l][EMPTY][UNSHIFT] }

末尾からUNSHIFT していくと、元通りの順序になる。MAPPUSH を書くときに、この方が便利と判断したのだろう。

リストの連結も FOLDUNSHIFT で書ける。FIZZBUZZPUSHはこの方がわかりやすい。

CONCAT = -> l { -> r { FOLD[l][r][UNSHIFT] } }

FIZZBUZZ = CONCAT[FIZZ][BUZZ]
PUSH = -> l { -> x {
  CONCAT[l][UNSHIFT[EMPTY][x]]
}}