Open40

Arrow の Either.kt を読む

mskmsk

概要

OSS コードリーディングの一環として、Arrow の Either.kt を読む

mskmsk

目的

  • OSS を読む経験を得る
  • Kotlin の仕様に対する理解を深める
  • 関数型プログラミングの知見を得る
mskmsk

Arrow の Either.kt である理由

  • Either.kt に絞れば比較的軽い
  • 自身の書籍でも利用しているので、理解を深めたい
mskmsk

進め方

mskmsk

理想は以下の手順でやりたい。

  1. 25 分間で進められる範囲を決める
  2. 該当箇所の EitherTest.kt を写経
  3. 該当箇所の Either.kt を写経
  4. テストを通す
  5. 学んだことを zenn の scrap に記述

だけど最初のうちは、以下のようになりそう

  1. 該当箇所の Either.kt を写経
  2. コンパイルを通す
  3. 学んだことを zenn の scrap に記述
mskmsk

進捗・学んだこと

4月24日(水) Arrow 2.0 が main ブランチにマージされた。

https://github.com/arrow-kt/arrow/pull/2778

そのため、4月25日(木)から、一からやり直すことにした。

mskmsk

2024/03/28

進捗

isRight()isLeft() の実装

実装
fun main(args: Array<String>) {
    val left: Either<String, Int> = Either.Left("foo")
    val right: Either<String, Int> = Either.Right(1)

    println("left $left")
    println("left.isRight() ${left.isRight()}")
    println("left.isLeft() ${left.isLeft()}")

    println("right $right")
    println("right.isRight() ${right.isRight()}")
    println("right.isLeft() ${right.isLeft()}")
}

public sealed class Either<out A, out B> {
    @Deprecated(
        RedundantAPI + "Use isRight()",
        ReplaceWith("isRight()")
    )
    internal abstract val isRight: Boolean

    @Deprecated(
        RedundantAPI + "Use isLeft()",
        ReplaceWith("isLeft()")
    )
    internal abstract val isLeft: Boolean

    public fun isLeft(): Boolean {
        contract {
            returns(true) implies (this@Either is Left<A>)
            returns(false) implies (this@Either is Right<B>)
        }
        return this@Either is Left<A>
    }

    public fun isRight(): Boolean {
        contract {
            returns(true) implies (this@Either is Right<B>)
            returns(false) implies (this@Either is Left<A>)
        }
        return this@Either is Right<B>
    }

    public class Left<out A> constructor(val value: A): Either<A, Nothing>() {
        override val isLeft = true
        override val isRight = false

        override fun toString(): String = "Either.Left($value)"

        public companion object {
            @Deprecated("Unused, will be removed from bytecode in Arrow 2.x.x", ReplaceWith("Left(Unit)"))
            @PublishedApi
            internal val leftUnit: Either<Unit, Nothing> = Left(Unit)
        }
    }

    /**
     * The right side of the disjoint union, as opposed to the [Left] side.
     */
    public data class Right<out B> constructor(val value: B) : Either<Nothing, B>() {
        override val isLeft = false
        override val isRight = true

        override fun toString(): String = "Either.Right($value)"

        public companion object {
            @PublishedApi
            internal val unit: Either<Nothing, Unit> = Right(Unit)
        }
    }
}

public const val RedundantAPI: String =
    "This API is considered redundant. If this method is crucial for you, please let us know on the Arrow Github. Thanks!\n https://github.com/arrow-kt/arrow/issues\n"


学んだこと

Contracts

スマートキャストの正体。例えば、null チェックをすると、後続の処理では null 安全の保証が自動でされる。

たとば、Arrow の以下の部分。Boolean が true だったら Either が Left 型にスマートキャスト、false だったら Right 型にスマートキャストされる。

    public fun isLeft(): Boolean {
        contract {
            returns(true) implies (this@Either is Left<A>)
            returns(false) implies (this@Either is Right<B>)
        }
        return this@Either is Left<A>
    }


https://kotlinlang.org/docs/whatsnew13.html#contracts

以下の資料がわかりやすかった。

https://speakerdeck.com/ntaro/kotlin-contracts-number-m3kt

利用するには、以下のアノテーションが必要

// ファイル全ての場合、ファイルの先頭に以下を記述
@file:OptIn(ExperimentalContracts::class)

// クラスまたは関数に付与する場合。class または fun に以下を記述
@OptIn(ExperimentalContracts::class)

mskmsk

3月29日(金)

kotest のインストール。

build.gradle.kts
dependencies {
    testImplementation(kotlin("test"))

    // kotest の依存関係
    implementation("io.kotest:kotest-runner-junit5:4.1.3")
    testImplementation("io.kotest:kotest-property:4.1.3")
}


学んだこと

  • kotest の import 方法
  • kotest には property based testing がデフォルトで組み込まれていること

わからなかったこと

quick start だとインストール方法がピンと来なかったので、chatGPT に聞いた

https://kotest.io/docs/quickstart

テストを実装しようとしたけど、Arb.either は either の拡張関数が必要っぽい。

class EitherTest : StringSpec({
    val ADB = Arb.either(Arb.string(), Arb.int())

})

mskmsk

3月30日(土)

Arb に拡張関数の実装。これで EIther 型が使えるようになったっぽい。

fun <E, A> Arb.Companion.either(arbE: Arb<E>, arbA: Arb<A>): Arb<Either<E, A>> {
  val arbLeft = arbE.map { Either.Left(it) }
  val arbRight = arbA.map { Either.Right(it) }
  return Arb.choice(arbLeft, arbRight)
}


学んだこと

ジェネリクスつきの拡張関数の使い方。

https://kotlinlang.org/docs/extensions.html

https://kotlinlang.org/docs/generics.html

わからなかったこと

kotest の依存の import まわり、以下の package をインストールできない。

import io.kotest.core.names.TestName
mskmsk

3月31日(日)

Law.kt の実装

package test

import io.kotest.core.names.TestName
import io.kotest.core.spec.style.StringSpec
import io.kotest.core.spec.style.scopes.StringSpecScope
import io.kotest.core.spec.style.scopes.addTest
import io.kotest.core.test.TestContext

interface LawSet {
  val laws: List<Law>
}

data class Law(val name: String, val test: suspend TestContext.() -> Unit)

fun StringSpec.testLaws(lawSet: LawSet): Unit = testLaws(lawSet.laws)

fun StringSpec.testLaws(vararg laws: List<Law>): Unit = laws
  .flatMap { list: List<Law> -> list.asIterable() }
  .distinctBy { law: Law -> law.name }
  .forEach { law: Law ->
    addTest(TestName(null, law.name, false), false, null) {
      law.test(StringSpecScope(this.coroutineContext, testCase))
    }
  }

kotest バージョンは以下の通りだった。

build.gradle.kts
dependencies {
    testImplementation(kotlin("test"))

    // kotest の依存関係
    testImplementation("io.kotest:kotest-runner-junit5:5.8.1") // KotestのJUnit5ランナー
    testImplementation("io.kotest:kotest-assertions-core:5.8.1") // Kotestのアサーションライブラリ
    testImplementation("io.kotest:kotest-property:5.8.1") // Kotestのプロパティベースのテスト
    testImplementation("io.kotest:kotest-framework-engine:5.8.1") // Kotestのプロパティベースのテスト
}

学んだこと

arrow の kotest のバージョン確認方法。
PR を見つけたので、それを参照した。

https://github.com/arrow-kt/arrow/pull/3392

そして、gradle/libs.versions.toml というものを知った。
これを使うと toml ファイルで、バージョン管理ができるらしい。

https://docs.gradle.org/current/userguide/platforms.html

わからなかったこと

後付けで libs.versions.toml を利用する方法。
Spring Boot でプロジェクトを作成するときには、デフォルトで利用で導入できていないので、後付けでやる方法を調べる必要がある。

Monoid、LawSet について。
テストを書く際に、これらも改めて定義しているけど、関数型の概念なのか不明。

mskmsk

4月1日(月)

SemigroupLaws.kt、MonoidLaws.kt の実装、Laws.kt に追加実装

package test.laws

import io.kotest.property.Arb
import io.kotest.property.PropertyContext
import io.kotest.property.checkAll
import test.Law
import test.LawSet
import test.equalUnderTheLaw

data class SemigroupLaws<F>(
    val name: String,
    val combine: (F, F) -> F,
    val G: Arb<F>,
    val eq: (F, F) -> Boolean = { a, b -> a == b }
): LawSet {
    override val laws: List<Law> =
        listOf(Law("Semigroup Laws ($name): associativity"){semigroupAssociate()})

    private suspend fun semigroupAssociate(): PropertyContext =
        checkAll(G, G, G) { A, B, C ->
            combine(combine(A, B), C).equalUnderTheLaw(combine(A, combine(B, C)), eq)
        }

    private suspend fun semigroupAssociative(): PropertyContext =
        checkAll(G, G, G) { A, B, C ->
            combine(combine(A, B), C).equalUnderTheLaw(combine(A, combine(B, C)), eq)
        }
}

package test.laws

import io.kotest.matchers.shouldBe
import io.kotest.property.Arb
import io.kotest.property.PropertyContext
import io.kotest.property.arbitrary.list
import io.kotest.property.checkAll
import test.Law
import test.LawSet
import test.equalUnderTheLaw

data class MonoidLaws<F>(
    val name: String,
    val empty: F,
    val combine: (F, F) -> F,
    val GEN: Arb<F>,
    val eq: (F, F) -> Boolean = { a, b -> a == b }
): LawSet {
    override val laws: List<Law> =
        SemigroupLaws(name, combine, GEN, eq).laws +
            listOf(
                    Law("Monoid Laws ($name): Left identify") { monoidLeftIdentity() },
                    Law("Monoid Laws ($name): Right identity") { monoidRightIdentity() },
                    Law("Monoid Laws ($name): combineAll should be derived") { combineAllIsDerived() },
                    Law("Monoid Laws ($name): combineAll of empty list is empty") { combineAllOfEmptyIsEmpty() },
                )

    private suspend fun monoidLeftIdentity(): PropertyContext =
        checkAll(GEN) { a ->
            combine(empty, a).equalUnderTheLaw(a, eq)
        }

    private suspend fun monoidRightIdentity(): PropertyContext =
        checkAll(GEN) { a ->
            combine(a, empty).equalUnderTheLaw(a, eq)
        }

    private suspend fun combineAllIsDerived(): PropertyContext =
        checkAll(5, Arb.list(GEN)) { list ->
            list.fold(empty, combine).equalUnderTheLaw(if (list.isEmpty()) empty else list.reduce(combine), eq)
        }

    private fun combineAllOfEmptyIsEmpty() {
        emptyList<F>().fold(empty, combine).equalUnderTheLaw(empty, eq) shouldBe true
    }
}

package test

import io.kotest.assertions.fail
import io.kotest.core.names.TestName
import io.kotest.core.spec.style.StringSpec
import io.kotest.core.spec.style.scopes.StringSpecScope
import io.kotest.core.spec.style.scopes.addTest
import io.kotest.core.test.TestContext

interface LawSet {
  val laws: List<Law>
}

data class Law(val name: String, val test: suspend TestContext.() -> Unit)

fun <A> A.equalUnderTheLaw(b: A, f: (A, A) -> Boolean = {x, y -> x== y}): Boolean =
  if (f(this, b)) true else fail("Found $this but expected: $b")

fun StringSpec.testLaws(lawSet: LawSet): Unit = testLaws(lawSet.laws)

fun StringSpec.testLaws(vararg laws: List<Law>): Unit = laws
  .flatMap { list: List<Law> -> list.asIterable() }
  .distinctBy { law: Law -> law.name }
  .forEach { law: Law ->
    addTest(TestName(null, law.name, false), false, null) {
      law.test(StringSpecScope(this.coroutineContext, testCase))
    }
  }


学んだこと

suspend は coroutine の考え方。
メイン処理に対してバックグラウンドでできたりするらしい。

Semigroup は関数型や圏論の考え方

http://pantodon.jp/index.rb?body=semigroup

https://old.arrow-kt.io/docs/arrow/typeclasses/semigroup/

わからなかったこと

suspend の具体的な利用方法。個人レベルでは利用できない。

Semigroup の深堀。過去に学んだことがない分野なので、まったくわからなかった。

mskmsk

4月2日(火)

やったこと

combine の実装。
これで、EitherTest の実装ができるようになった?

public fun <A, B> Either<A, B>.combine(other: Either<A, B>, combineLeft: (A, A) -> A, combineRight: (B, B) -> B): Either<A, B> =
    when (val one = this){
        is Either.Left -> when (other) {
            is Either.Left -> Either.Left(combineLeft(one.value, other.value))
            is Either.Right -> one
        }

        is Either.Right -> when(other) {
            is Either.Left -> other
            is Either.Right -> Either.Right(combineRight(one.value, other.value))
        }
    }

わからなかったこと

comibne とはなんなんだ?
関数の合成?

mskmsk

4月3日(水)

やったこと

kotest まわりの実装。
semigroup、monoidlawas は実は Either だけを動かすのならば不要だった。


学んだこと

kotest を Intellij IDEA で動作するなら、kotest の plugin が必要だった。

わからなかったこと

semigroup、monoid まわり。

mskmsk

4月5日(金)

やったこと

foldfoldLeft を写経


学んだこと

昔は foldLeft もあったが現在は非推奨。

わからなかったこと

昨日と同じ内容

mskmsk

4月6日(土)

やったこと

foldMapbifoldLeftbifoldMap、 を写経

ついでに、Monoid、Semigroup も一部写経


学んだこと

Monoid、Semigroup は現在非推奨
どちらも combine に統合されている。

わからなかったこと

Monoid と Semigroup

Monoid は Monoid Interface に対して、型(BooleanIntLong など)ごとに実装し、Monoid のメソッドを持たせていた。

mskmsk

4月7日(日)

やったこと

Monod.EitherMonoid の comibine のビルドを通せずに時間を溶かした。
-> 最終的に写経用のディレクトリで、package 構成を見直して、ビルドを通すことに成功した。

現時点での Monoid と Semigroup を写経した結果。Monoid が Semigroup を実装しているので、Monoid の実装には empty と combine が必要になっている。
これで実現しているらしい。


学んだこと

Monoid.kt
public const val MonoidDeprecation: String =
  "Monoid is being deprecated, use combine (A, A) -> A lambdas or method references with initial values instead."

@Deprecated(MonoidDeprecation)
public interface Monoid<A> : Semigroup<A> {
  /**
   * A zero value for this A
   */
  public fun empty(): A

  public companion object {
    @JvmStatic
    @JvmName("Integer")
    public fun int(): Monoid<Int> = IntMonoid

    @JvmStatic
    public fun string(): Monoid<String> = StringMonoid

    @JvmStatic
    public fun <A, B> either(SGA: Semigroup<A>, MB: Monoid<B>): Monoid<Either<A, B>> =
      EitherMonoid(SGA, MB)

    private object IntMonoid : Monoid<Int> {
      override fun empty(): Int = 0
      override fun Int.combine(b: Int): Int = this + b
    }

    private object StringMonoid: Monoid<String> {
      override fun String.combine(b: String): String = "${this}$b"
      override fun empty(): String = ""
    }

    private class EitherMonoid<L, R>(
      private val SGOL: Semigroup<L>,
      private val MOR: Monoid<R>
    ) : Monoid<Either<L, R>> {
      override fun empty(): Either<L, R> = Either.Right(MOR.empty())

      override fun Either<L, R>.combine(b: Either<L, R>): Either<L, R> =
        combine(SGOL, MOR, b)
    }
  }
}

Semigroup.kt
public const val SemigroupDeprecation: String =
    "Semigroup is being deprecated, use combine (A, A) -> A lambdas or method references instead."

@Deprecated(SemigroupDeprecation)
public fun interface Semigroup<A> {
    public fun A.combine(b: A): A
}

@Deprecated(SemigroupDeprecation)
public fun <A> Semigroup<A>.combine(a: A, b: A): A =
    a.combine(b)

mskmsk

4月8日(月)

やったこと

combine のテストの写経。不明な部分が多い
getOrElse の実装。


学んだこと

getOrElse の実装について。
意外とシンプルだった。

Either.kt
/**
 * Get thr right value [B] of this [Either],
 * or compute a [default] value with the left value [A].
 *
 * ```kotlin
 * import arrow.core.Either
 * import arrow.core.getOrElse
 * import io.kotest.matchers.shouldBe
 *
 * fun test() {
 *   Either.Left(12) getOrElse { it + 5 } shouldBe 17
 * }
 * ```
 */
public inline infix fun <A, B> Either<A, B>.getOrElse(default: (A) -> B): B {
    contract { callsInPlace(default, InvocationKind.AT_MOST_ONCE)}
    return fold(default, ::identity)
}

Deprecated にはレベルがあって、DeprecationLevel.HIDDEN を指定すると参照できなくなってビルドが通らなくなる。

@Deprecated(
    RedundantAPI + "This API is overloaded with an API with a single argument",
    level = DeprecationLevel.HIDDEN
)
public inline fun <B> Either<*, B>.getOrElse(default: () -> B): B =
    fold({ default() }, ::identity)

わからなかったこと

combine まわり。
Monoid の combine は Deprecated されているから、必死に追いかける必要はないけど、関数型を理解するには必要そう。

mskmsk

4月9日(火)

やったこと

getOrNull の写経

    /**
     * Returns the unwrapped value [0] of [Either.Right] or `null` if it is [Either.Left]
     *
     * ```kotlin
     * import arrow.core.Either
     * import io.kotest.matchers.shouldBe
     *
     * fun test() {
     *   Either.Right(12).getOrNull() shouldBe 12
     *   Either.Left(12).getOrNull() shouldBe null
     * }
     * ```
     *
     * @return
     */
    public fun getOrNUll(): B? {
        contract {
            returns(null) implies (this@Either is Left<A>)
            returnsNotNull() implies (this@Either is Right<B>)
        }
        return getOrElse { null }
    }


まなんだこと

v2 に向けて Deprecated な機能が多い。

わからなかったこと

今回は特になし

mskmsk

4月10日(水)

やったこと

orNonegetONonegetOrHandle メソッドと、Option.kt (一部)の写経。

Either.kt
    @Deprecated(
        "orNone is being renamed to getOrNone to be more consistent with the Kotlin Starndard Library naming",
        ReplaceWith("getOrNone()")
    )
    public fun orNone(): Option<B> = getOrNone()

    public fun getOrNone(): Option<B> = fold({ None }, { Some(it) })

Option.kt
public sealed class Option<out A> {

    @Deprecated(
        "Duplicated API. Please use Option's member function isNone. This will be removed towards Arrow 2.0",
        replaceWith = ReplaceWith("isNone()")
    )
    public abstract fun isEmpty(): Boolean
}

public object None : Option<Nothing>() {
    @Deprecated(
        "Duplicated API. Please use Option's member function isNone. This will be removed towards Arrow 2.0",
        replaceWith = ReplaceWith("isNone()")
    )
    public override fun isEmpty(): Boolean = true

    override fun toString(): String = "Option.None"
}

public data class Some<out T>(val value: T) : Option<T>() {
    @Deprecated(
        "Duplicated API. Please use Option's member function isNone. This will be removed towards Arrow 2.0",
        replaceWith = ReplaceWith("isNone()")
    )
    public override fun isEmpty(): Boolean = false

    override fun toString(): String = "Option.Some($value)"

    public companion object {
        @PublishedApi
        @Deprecated("Unused, will be removed from bytecode in Arrow 2.x.x", ReplaceWith("Some(Unit)"))
        internal val unit: Option<Unit> = Some(Unit)
    }
}


まなんだこと

Arrow-kt が独自に Option 型を用意していることを思い出した。
v2 になっても Option.kt は残りそう。

わからなかったこと

わからなかったことというか、判断できなかったこと。
Option.kt はどこまで写経すべきか判断できなかった。OptionTest.kt もあるので、EIther.kt の写経を終えたらやってもいいかも。
あと、Option.kt に説明に Scala が利用されていたので、ここらへんにも手を伸ばすのであれば、Scala も学ぶ必要があるかも。

mskmsk

4月11日(木)

やったこと

flatMap の写経


学んだこと

Either 型の合成

わからなかったこと

特になし

mskmsk

4月12日(金)

やったこと

filterOrOtherleftIfNull の写経。


学んだこと

filterOrOtherleftIfNull はどちらも、flatMap に機能が統合されていた。
Arrow は v1 はわりと実験的な部分が多かった?

すべてを読み終えたときに、Deprecated じゃない機能をまとめるか、v2 の API インタフェースを見た方がよさそう。

わからなかったこと

特になし

mskmsk

4月13日(土)

やったこと

existsrightIfNotNullrightIfNullswap の写経


学んだこと

existsisRight に、rightIfNotNullrightIfNull は Kotlin の null ハンドリングをつかようになっていた。
swap は今後も利用可能

わからなかったこと

特になし

mskmsk

4月14日(日)

やったこと

mapmapLeftbimap を写経


学んだこと

mapmapLeftbimapfold のラッパーなのに、Deprecated じゃなかった。

わからなかったこと

Arrow の Deprecated 基準。

mskmsk

4月15日(月)

やったこと

replicatetraverse を写経。


学んだこと

replicatetraverse はどちらも fold に移行。

わからなかったこと

特になし

mskmsk

4月17日(水)

やったこと

recover の写経の続き。
しかし、DSL を読み解くことができず断念。
そのため、combine のテストの写経をした。


学んだこと

特になし

わからなかったこと

わからないことではないが、arrow を clone してもローカルで Intellij IDEA のビルドが通らないため、コードジャンプで追えていない。
そのため、写経のやり方に限界を感じてきた。

mskmsk

4月18日(木)

やったこと

NonEmptyList のテストの写経を開始。


学んだこと

特になし

わからなかったこと

NonEmptyLIst の依存。NonEmptyCollection、NonEmptySet などがあってテストを通すのに時間がかかりそう。

mskmsk

4月19日(金)

やったこと

NonEmptyList クラスと NonEmptyCollection の写経。
昨日記述したテストが通った

学んだこと

AbstractList と NonEmptyCollection の組み合わせで最小限の NonEmptlyList を作成した

わからなかったこと

AbstractList の get メソッドの使い方。
NonEmptlyList では、tail と head の組み合わせで利用できるけど、それ以外の使い方がわからない

mskmsk

4月20日(土)

やったこと

zipOrAccumulate の写経。
DSL を読み解くのを諦めた箇所を除けばテストももうすぐで終わる。


学んだこと

特になし

わからなかったこと

というか悩んでいること

  • DSL をどこまで追うのか
  • NonEmptyList まで手を伸ばすのか
mskmsk

4月21日(日)

やったこと

traverse(fa: (B) -> Option<C>): Option<Either<A, C>> の写経。


学んだこと

特になし

わからなかったこと

特になし

mskmsk

4月23日(火)

やったこと

bitraverse、bimap の写経。

Arrow v2 の写経でよかった感が拭えなくなってきた


学んだこと

特になし

わからなかったこと

特になし

mskmsk

4月24日(水)

やったこと

Either.bisequenceNullableEither.bitraverseNullable の写経。
Validated 系は写経を飛ばしている


学んだこと

特になし

わからなかったこと

特になし

mskmsk

ここから、Arrow 2.0 にマージされたのでやり直し。

mskmsk

4月25日(木)

やったこと

Either.isLeft、Either.isRight、Either.Left、Either.Right の写経。
Deprecated がなくなったので、写経しやすくなった。


学んだこと

特になし。まだ理解できている箇所。

わからなかったこと

Either.Left に記述してあった、public companion object だけを書くやり方。どんな意味があるのかいまいちわからなかった。

    /**
     * The left side of this disjoint union, as opposed to the [Right] side.
     */
    public data class Left<out A> constructor(val value: A) : Either<A, Nothing>() {
        override fun toString(): String = "Either.Left($value)"

        public companion object
    }

mskmsk

4月27日(土)

やったこと

Either.fold と Either.combine の写経


学んだこと

fold がすっきりして綺麗。


    public inline fun <C> fold(ifLeft: (left: A) -> C, ifRight: (right: B) -> C): C {
        contract {
            callsInPlace(ifLeft, InvocationKind.AT_MOST_ONCE)
            callsInPlace(ifRight, InvocationKind.AT_MOST_ONCE)
        }
        return when (this) {
            is Right -> ifRight(value)
            is Left -> ifLeft(value)
        }
    }


わからなかったこと

combine の実装が理解できなかった。

public fun <A, B> Either<A, B>.combine(other: Either<A, B>, combineLeft: (A, A) -> A, combineRight: (B, B) -> B): Either<A, B> =
    when (val one = this) {
        is Either.Left -> when (other) {
            is Either.Left -> Either.Left(combineLeft(one.value, other.value))
            is Either.Right -> one
        }

        is Either.Right -> when (other) {
            is Either.Left -> other
            is Either.Right -> Either.Right(combineRight(one.value, other.value))
        }
    }