Monad in TypeScript

tl; dr

• 普段はTypeScriptを書いているオタクが、すごいH本を読んだ📖

  • Haskellには便利な機能や考え方がたくさんあり、その一部はTypeScriptみたいなプログラミング言語でも表現できることがわかった
  • TypeScriptでHaskellみたいなことをしようと思うと、いわゆるモナドライブラリが便利であり、中でもfp-tsが良さそうだった

以下にはfp-tsについて具体的な解説などをコードを交えて書く。

はじめに

前職で、TypeScriptのコードに type Either<Left, Right> = ... みたいなtype aliasを書いていたエンジニアさんにHaskellを勧められ、すごいH本を読んでみた。

Haskellはすごかった。もの凄く強力なチカラを2つ持っている。ガチガチな静的型付けと、モダンな関数型プログラミング技法である。美しく、型安全で、無駄のない処理を書くことができる。

静的型で何でも表す

先ほどのEitherというのも型クラス(Javaなどの一般的なクラスとは違い、どちらかというとインターフェースのようなもの)の一つで、失敗系と成功系の2つの文脈を一つの型として定義できる。HTTPリクエストならエラーメッセージとレスポンスをそれぞれ型として表現できるわけである。

こうした便利な型クラスは他にもたくさんあり、Haskellの他にScalaなんかにも存在する概念らしい。その名をモナドという。モナドをはじめとする"文脈を表現する型クラス"とその扱い方について詳しく知りたい方はMonad, MTL styleなどで調べると良いと思うのだが、厳密さを追求すると高度な数学の話になってしまうし、何より私がわかっていないためこの記事で掘り下げて説明することはしない🙅けれど全くしないわけにもいかないため、他人の解説を引用させて頂いてお茶を濁したい。

Functors, Applicatives, And Monads In Pictures - http://adit.io/posts/2013-04-17-functors,_applicatives,_and_monads_in_pictures.html

画像中の箱は文脈を表している。この画像は、Haskellにおいて箱の種類ごとにどのような演算子(画像中の<$>, <*>, >>=)を使えば、文脈(=箱)を失わずに値を加工できるかを表している。この記事でこれらの記号自体は出てこないため気にしないでほしいのだが、以下の点だけは頭のどこかに記憶しておいてほしい。

• Functor, Applicative は箱の種類であり、Monadの親戚である。
• 箱は型で表現することができる
• 箱に入った値は、そのままでは箱無しの値を取る関数に渡すことができないため、特殊な関数・演算子を使う必要がある

関数型プログラミング

Haskellはいわゆる純粋関数型プログラミング言語であり、副作用のある処理は副作用のない処理と完全に切り離されている。副作用のない処理を書く場所では、値を目的の形式に加工するにあたって型のキャストや代入操作からは完全に解放され、変換処理そのものに集中できるような仕組みが用意されている。

TypeScriptでHaskell, Scalaみたいなことをする

周知の事実であろうが、JavaScriptでもある程度の関数型プログラミングが可能である。オライリー本も出ている。(内容は古くなってしまっている)。具体的には高階関数を使って副作用のない処理を繋げたり、関数をカリー化して他の関数に渡したりすることができる。

それに、TypeScriptやflowなんかを使えば静的型も使える。ならJavaScriptでもHaskell, Scalaっぽいことができるのでは？という考えに至る。そこで便利なのがモナドライブラリである。モナドライブラリは前述の文脈を表現する型・モナドとそれを扱うための関数などを提供してくれる。

さて、TypeScriptで利用可能なモナドライブラリについてはこちらの記事が詳しい。しかし、こちらの記事の公開後にスター数・規模感共にTypeScriptのモナドライブラリでは最大のfp-tsが現れた。今回の記事ではこちらの紹介をしていきたい。

fp-ts

fp-tsは今話題のPureScript, そしてfantasy-landやScalaにインスパイアされたモナドライブラリらしい。他の有名なモナドライブラリが300 Star前後であるのに対して、規模感もあってか倍以上のStar数を持っている。

どんなことができるのかはREADMEのExamplesにまとまっている。Free Monad, MTL StyleなどHaskellでメジャーな(?)テクニックから、Option, Either , Reader , Writer , State, List などの定番モナド、更にはHaskellでよくWriterの代わりに使えと言われている、デバッグに便利な Trace , 依存型を使って型安全に有限オートマトンを記述できる IxIO なんてものまである(2016年に発表された論文を使った実装のようだが、よくわからなかった…)。

モナドを中心に、fp-tsのいくつかの機能をdigってみる。

Optionモナド

Optionモナドは、値がない可能性のある文脈を表現するためのもので、例えばリストから目的の要素を検索する場合などに役立つ。type Option<A> = None | Some<A> として、ある型AについてnoneもしくはAをSomeでラップしたものを返す。noneではなくnull を、 値そのものではなく some で値をラップしたものを使うのは、Option という文脈を損なわないためである。

Scalaから持ち込まれたモナドで、HaskellではMaybeに相当する(はず)。Scalaのことは知らないものでスカラ...😰

import { Option, some, none, option } from 'fp-ts/lib/Option'
import { array } from 'fp-ts/lib/Array'
import { sequence } from 'fp-ts/lib/Traversable'

export function getAllSomesOrNone<A>(xs: Array<Option<A>>): Option<Array<A>> {
  return sequence(option, array)(xs)
}

console.log(getAllSomesOrNone([some(1), some(2), some(3)])) // => some([1, 2, 3])
console.log(getAllSomesOrNone([some(1), none, some(3)])) // => none

このコードはリポジトリのexercise(一問一答形式でfp-tsについて勉強していくもの)に置いてある。このコードでは、Array<Option<A>> な配列を受け取って、配列にnoneが含まれていなければ some で各要素をラップした配列を、含まれていれば none を返す関数getAllsomesOrNoneを定義している。

getAllSomesOrNone で気になるのは、fp-tsのsequenceの実装であろう。

// Traversable.ts より一部を抜粋

// applicativeはモナドcにくるまった関数a -> bを、c[a] -> c[b]な関数に変換する
export function traverse<F, T>(
  F: Applicative<F>,
  T: Traversable<T>
): <A, B>(ta: HKT<T, A>, f: (a: A) => HKT<F, B>) => HKT<F, HKT<T, B>> {
  return T.traverse(F)
}

export interface Traversable<T> extends Functor<T>, Foldable<T> {
  readonly traverse: <F>(F: Applicative<F>) => <A, B>(ta: HKT<T, A>, f: (a: A) => HKT<F, B>) => HKT<F, HKT<T, B>>
}

// HKT: Higher Kinded Types(高階型)
// "型の型"を定義する
export function sequence<F, T>(
  f: Applicative<F>,
  t: Traversable<T>
): <A>(tfa: HKT<T, HKT<F, A>>) => HKT<F, HKT<T, A>> {
  return tfa => t.traverse(f)(tfa, fa => fa)
}

// URIは、Monadの識別子で単なる文字列("Option", "List"など)
export function sequence<F extends URIS, T extends URIS>(
  f: Applicative1<F>,
  t: Traversable1<T>
): <A>(tfa: Type<T, Type<F, A>>) => Type<F, Type<T, A>>

sequenceは、 前述の文脈を持つ型であるアプリカティブ(option)と、走査して各要素に同じ関数を使うことができるような型(この表現はかなり乱暴ですが!)traversable(array)を引数に取り、関数を返す。その関数とは、二重の入れ子構造になっている高階型(Option<A>[])を引数にとり、入れる順番を逆にした高階型(Option<A[]>)を返すものである。この例ではsequenceが返した関数に対して Array<Opation<A>> を渡しているため、最終的にgetSomeOrNone からは Option<Array<A>> が返ってきている。目的の型を得られるわけである。

では、sequence はどのようにしてApplicative と Traversable から (tfa: HKT<T, HKT<F, A>>) => HKT<F, HKT<T, A>> を得ているのだろうか？答えはsequense が呼び出している Traversable.traverse 関数にある。この関数は定義にある通り、いかにも部分適用して使ってくださいね😉というような型定義になっている。実際、この関数はt.traverse(f)(tfa, fa => fa) と呼び出されている。ここで、fはOption, tfa は Array<Option<A>>, fa => fa は Option<A> => Option<A> だと考えてほしい。

もちろん、これはOption以外のアプリカティブ(Eitherなど)やArray 以外のtraversable(tupleなど)にも適用できる。型レベルでここまで高度なことができてしまうのである！

しかし…難しい！めちゃめちゃ難しい！頭が痛くなる！！でも慣れてくるといけそうな気がしてくる。(本当か？)何より便利なことは確かなので使えるようになったら嬉しいだろう。今書いているのはTypeScriptなのである。これでサーバサイドのコードもフロントエンドのコードも書けるのだ。

Eitherモナド

Eitherは前述の通りで、失敗系と成功系を表現する型である。

import { Either, left, right } from 'fp-ts/lib/Either'

export function elementAt<A>(xs: Array<A>, i: number): Either<string, A> {
  if (i < 0) {
    return left<string, A>('out of lower bound')
  }
  if (i >= xs.length) {
    return left<string, A>('out of upper bound')
  }
  return right<string, A>(xs[i])
}

console.log(elementAt([1, 2, 3], -1)) // => left('out of lower bound')
console.log(elementAt([1, 2, 3], 10)) // => left('out of upper bound')
console.log(elementAt([1, 2, 3], 1))  // => right(2)

これはもはや解説の必要すらないであろう。便利…！

Stateモナド

最後に紹介しておきたいのがStateモナドである。
Haskellで書くこういうコードが、

import Control.Monad.State

main :: IO ()
main = runStateT code [1..] >> return ()
--
-- layer an infinite list of uniques over the IO monad
--

code :: StateT [Integer] IO ()
code = do
    x <- pop
    io $ print x
    y <- pop
    io $ print y
    z <- pop
    io $ print z
    return ()

--
-- pop the next unique off the stack
--
pop :: StateT [Integer] IO Integer
pop = do
    (x:xs) <- get
    put xs
    return x

io :: IO a -> StateT [Integer] IO a
io = liftIO

fp-tsでこう書ける

import * as stateT from 'fp-ts/lib/StateT'
import { io, IO } from 'fp-ts/lib/IO'
import { Monad2 } from 'fp-ts/lib/Monad'
import { Endomorphism } from 'fp-ts/lib/function'
import * as array from 'fp-ts/lib/Array'
import { State } from 'fp-ts/lib/State'

declare module 'fp-ts/lib/HKT' {
  interface URI2HKT2<L, A> {
    StateIO: StateIO<L, A>
  }
}

const stateTIO = stateT.getStateT(io)

export const URI = 'StateIO'

export type URI = typeof URI

export class StateIO<S, A> {
  readonly _A!: A
  readonly _L!: S
  readonly _URI!: URI
  constructor(readonly value: (s: S) => IO<[A, S]>) {}
  run(s: S): [A, S] {
    return this.value(s).run()
  }
  eval(s: S): A {
    return this.run(s)[0]
  }
  exec(s: S): S {
    return this.run(s)[1]
  }
  map<B>(f: (a: A) => B): StateIO<S, B> {
    return new StateIO(stateTIO.map(f, this.value))
  }
  ap<B>(fab: StateIO<S, (a: A) => B>): StateIO<S, B> {
    return new StateIO(stateTIO.ap(fab.value, this.value))
  }
  ap_<B, C>(this: StateIO<S, (b: B) => C>, fb: StateIO<S, B>): StateIO<S, C> {
    return fb.ap(this)
  }
  chain<B>(f: (a: A) => StateIO<S, B>): StateIO<S, B> {
    return new StateIO(stateTIO.chain(a => f(a).value, this.value))
  }
}

const map = <S, A, B>(fa: StateIO<S, A>, f: (a: A) => B): StateIO<S, B> => {
  return fa.map(f)
}

const of = <S, A>(a: A): StateIO<S, A> => {
  return new StateIO(stateTIO.of(a))
}

const ap = <S, A, B>(fab: StateIO<S, (a: A) => B>, fa: StateIO<S, A>): StateIO<S, B> => {
  return fa.ap(fab)
}

const chain = <S, A, B>(fa: StateIO<S, A>, f: (a: A) => StateIO<S, B>): StateIO<S, B> => {
  return fa.chain(f)
}

const stateTget = stateT.get(io)
export const get = <S>(): StateIO<S, S> => {
  return new StateIO(stateTget())
}

const stateTput = stateT.put(io)
export const put = <S>(s: S): StateIO<S, void> => {
  return new StateIO(stateTput(s))
}

const stateTmodify = stateT.modify(io)
export const modify = <S>(f: Endomorphism<S>): StateIO<S, void> => {
  return new StateIO(stateTmodify(f))
}

const stateTgets = stateT.gets(io)
export const gets = <S, A>(f: (s: S) => A): StateIO<S, A> => {
  return new StateIO(stateTgets(f))
}

const stateTliftF = stateT.liftF(io)
export const fromIO = <S, A>(fa: IO<A>): StateIO<S, A> => {
  return new StateIO(stateTliftF(fa))
}

const stateTfromState = stateT.fromState(io)
export const fromState = <S, A>(fa: State<S, A>): StateIO<S, A> => {
  return new StateIO(stateTfromState(fa))
}

export const stateIO: Monad2<URI> = {
  URI,
  map,
  of,
  ap,
  chain
}

//
// Usage (adapted from https://wiki.haskell.org/Simple_StateT_use)
//

import { log } from 'fp-ts/lib/Console'

/** pop the next unique off the stack */
const pop: StateIO<Array<number>, number> = get<Array<number>>().chain(ns =>
  array.foldL(ns, () => of(0), (h, t) => put(t).chain(() => of(h)))
)

const program1: StateIO<Array<number>, void> = pop
  .chain(x => fromIO(log(x)))
  .chain(() => pop)
  .chain(y => fromIO(log(y)))
  .chain(() => of(undefined))

program1.run([1, 2, 3])

コード量が多いので各実装の解説は控えるが、詰まるところはStateT を利用して State と IO の２つのモナドを組み合わせている。of, ap, map みたいなところも(HaskellやScalaに馴染みのない方にはわかりづらいのだが、Haskellのコードを見てわかるようにその手のプログラミング言語では自分で実装する必要はない)自分で定義しなければならないため、コード量がバカみたいに多いが、やりたいことは113~119行目の6行である。

さいごに

もの凄くわかりづらい&ターゲットが不明な説明になってしまいました…ここ間違ってるよとかこう書いたほうがいいよとかそういうフィードバックはガシガシください。

というかそもそもfp-ts以前にHaskellめっちゃ難しくないですか…？すごHの次に読むべきおすすめチュートリアル/OSS情報を教えてください🙏