Kotlin FP: моноиды и сортировки

[euroUK]

Как тяжело жить без Linq

[kkirsanov2]

Странно что слово полугруппа не произнесено.

[ivanlardis]

Хотелось поменьше теории) Побольше практики

[skymorp]

Где можно посмотреть код целиком?

[ivanlardis]

Создал gist

[skymorp]

Благодарю за gist (на самом деле в статье присутствует весь код, просто оно у меня не собиралось из-за неподходящих версий kotlin'а и jdk) и за статью (поставил бы +, но недостаточно кармы для голосования).

Вопросы:

• зачем Order реализует интерфейс Monoid?
• ComparatorMonoid::plus() — не делает ли данная функция лишние сравнения? (я так понял что делает; хотя смысл сравнивать дальше есть только в случае, если compare() вернул Order.EQ)

[ivanlardis]

зачем Order реализует интерфейс Monoid?

Это сделано для очевидности доказательства

Чтобы доказать, что (A, A) -> Order.
Мы должны были доказать, что Order это моноид

ComparatorMonoid::plus — не делает ли данная функция лишние сравнения?

Правильное замечание, делает.
Но тут есть два пути развития
1)Следующим шагом, после того, как мы доказали что (A, A) -> Order моноид
Оптимизировать его, чтобы он не делал лишних сравнений

fun interface ComparatorMonoid<A> : Monoid<ComparatorMonoid<A>> {
    fun compare(a: A, other: A): Order

    override fun plus(rh: ComparatorMonoid<A>) =
        ComparatorMonoid<A> { a, other ->
            val order = compare(a, other)
            when (order) {
                Order.EQ -> rh.compare(a, other)
                else -> order
            }
        }

    override fun empty() = ComparatorMonoid<A> { _, _ -> Order.EQ }
}

2)Либо пойти по правильному функциональному пути
Так, как обсуждалось ранее
Если область значения функции моноид, то такая функция также моноид
Реализуем это в коде

fun interface Function2Monoid<A, B : Monoid<B>> : Monoid<Function2Monoid<A, B>> {

    fun invoke(a: A, other: A): B

    override fun plus(rh: Function2Monoid<A, B>): Function2Monoid<A, B> =
        Function2Monoid { a, other -> invoke(a, other) + rh.invoke(a, other) }

    override fun empty() = Function2Monoid<A, B> { a, a1 ->
        invoke(a, a1).empty()
    }
}

И теперь нам не нужно создавать ComparatorMonoid
Мы можем пользоваться Function2Monoid
Тут и пригодится знание о том, что Order это моноид, которое легко доказать
Переписав функции в такой вид

fun <A> Iterable<A>.sort(comparatorMonoid: Function2Monoid<A, Order>) =
    sortedWith { a, b -> comparatorMonoid.invoke(a, b).compareValue }

fun <A : Comparable<A>> A.compare(other: A) = when {
    this > other -> Order.GT
    this == other -> Order.EQ
    else -> Order.LT
}

val <A, B : Comparable<B>> ((A) -> B).comparator
    get():Function2Monoid<A, Order> = Function2Monoid<A, Order> { a, b ->
        invoke(a).compare(invoke(b))
    }

Не хотел этим усложнять статью.
Но, видимо, стоило.

[skymorp]

Большое спасибо за развернутый ответ (вижу, вы в теме) %)
Больше вопросов нет.

[ivanlardis]

+

[funca]

ivanlardis, расскажите как изменится решение, чтобы отсортировать пользователей не как на скриншоте, а в натуральном порядке (user8, user9, user10, user11)? Как добавить сортировку по адресу, если у отдельных пользователей адрес может быть не указан?

[ivanlardis]

расскажите как изменится решение, чтобы отсортировать пользователей не как на скриншоте, а в натуральном порядке (user8, user9, user10, user11)

Как мы обсуждали ранее

Списки могут работать с Function2, которые являются моноидом
Iterable.sort(function2: Function2Monoid<A, Order>)

Function2 имеет тип (A, A) -> Order. Как раз она решает что и как сортировать
То есть если нам нужен любой другой вид сравнения,
мы реализуем Function2 по-другому

val <A> ((A) -> String).customComparator
    get():Function2Monoid<A, Order> = Function2Monoid<A, Order> { a, other ->
        val aString = invoke(a)
        val otherString = invoke(other)

        //сравниваем значения строк как нам нужно
        //возвращаем Order, который нам нужен при сравнении
        return@Function2Monoid Order.EQ
    }

И после этого можем его использовать в сортировке

 users.sort(
        User::name.stringComparator +
        User::address.andThen(Address::city).comparator
    ).forEach(::println)

Как добавить сортировку по адресу, если у отдельных пользователей адрес может быть не указан?

Учим наши функции работать с nullable)

infix fun <A, B, C> ((A) -> B?).andThen(g: (B) -> C): (A) -> C? = { a: A ->
    this(a)?.let(g)
}

val <A, B : Comparable<B>> ((A) -> B?).comparator
    get():Function2Monoid<A, Order> = Function2Monoid<A, Order> { a, other ->
        val b = invoke(a)
        val bOther = invoke(other)
        when {
            b != null && bOther != null -> b.compare(bOther)
            b != null -> Order.GT
            bOther != null -> Order.LT
            else -> Order.EQ
        }
    }

Плюс для улучшения Api можно посмотреть в сторону оптики

val <A, B : Comparable<B>> Lens<A, B>.comparator
    get():Function2Monoid<A, Order> = ::get.comparator

val <A, B : Comparable<B>> Optional<A, B>.comparator
    get():Function2Monoid<A, Order> = (::getOption andThen Option<B>::orNull).comparator


    users.sort(
        AppUser.name.comparator +
        AppUser.address.city.comparator
    ).forEach(::println)