Статьи

Kata — реализация функциональной структуры данных List в Kotlin

Октябрь 9, 2018

Я видел упражнение в главе 3 превосходной книги « Функциональное программирование в Scala», которое посвящено определению функциональных структур данных и использует связанный список в качестве примера того, как приступить к разработке такой структуры данных. Я хотел попробовать этот образец, используя Kotlin, чтобы увидеть, в какой степени я могу воспроизвести образец.

Скелет scala образца доступен в коде компаньона для книги здесь, и моя попытка в Kotlin сильно вдохновлена ​​(скопирована!) Ключом ответа в хранилище.

основной

Вот как выглядит базовое представление List в Kotlin:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
sealed class List<out A> {
 
    abstract val head: A
 
    abstract val tail: List<A>
}
 
data class Cons<out T>(override val head: T, override val tail: List<T>) : List<T>()
 
object Nil : List<Nothing>() {
    override val head: Nothing
        get() {
            throw NoSuchElementException("head of an empty list")
        }
 
    override val tail: List<Nothing>
        get() {
            throw NoSuchElementException("tail of an empty list")
        }
}

Список был определен как запечатанный класс, это означает, что все подклассы запечатанного класса будут определены в одном файле. Это полезно для сопоставления с образцом в типе экземпляра и будет появляться в большинстве функций.

Есть две реализации этого списка —

1. Минусы непустого списка, состоящего из элемента head и хвостового списка,

2. Ноль пустой список

Это уже очень полезно в его текущей форме, рассмотрим следующее, которое создает список и извлекает из него элементы:

1
2
3
4
5
6
val l1:List<Int> = Cons(1, Cons(2, Cons(3, Cons(4, Nil))))
assertThat(l1.head).isEqualTo(1)
assertThat(l1.tail).isEqualTo(Cons(2, Cons(3, Cons(4, Nil))))
 
 
val l2:List<String> = Nil

Соответствие шаблону с выражением «когда»

Теперь перейдем к реализации некоторых методов List. Поскольку List является запечатанным классом, он позволяет обеспечить хорошее сопоставление с образцом, скажем, для получения суммы элементов в List:

1
2
3
4
5
6
fun sum(l: List<Int>): Int {
    return when(l) {
        is Cons -> l.head + sum(l.tail)
        is Nil -> 0
    }
}

Компилятор понимает, что Cons и Nil — это единственные два пути для совпадения в экземпляре списка.

Немного более сложная операция: «удалить» некоторое количество элементов из начала списка и «dropWhile», который принимает предикат и удаляет элементы с начала, соответствующие предикату:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
fun drop(n: Int): List<A> {
    return if (n <= 0)
        this
    else when (this) {
        is Cons -> tail.drop(n - 1)
        is Nil -> Nil
    }
}
 
val l = list(4, 3, 2, 1)
assertThat(l.drop(2)).isEqualTo(list(2, 1))
 
fun dropWhile(p: (A) -> Boolean): List<A> {
    return when(this) {
        is Cons -> if (p(this.head)) this.tail.dropWhile(p) else this
        is Nil -> Nil
    }
}
 
val l = list(1, 2, 3, 5, 8, 13, 21, 34, 55, 89)
assertThat(l.dropWhile({e -> e < 20})).isEqualTo(list(21, 34, 55, 89))

Они демонстрируют силу сопоставления с образцом с выражением «когда» в Kotlin .

Небезопасная дисперсия!

Чтобы коснуться складки, посмотрите, как список определен с параметром типа, который объявлен как «out T», это называется «декларация сайта дисперсии», что в этом случае делает список ко-вариантным для типа T. Объявление сайта дисперсия красиво объясняется с документацией Kotlin . Благодаря тому, как List объявлен, он позволяет мне делать что-то вроде этого:

1
2
val l:List<Int> = Cons(1, Cons(2, Nil))
val lAny: List<Any> = l

Теперь рассмотрим функцию «добавить», которая добавляет другой список:

1
2
3
4
5
6
fun append(l: List<@UnsafeVariance A>): List<A> {
    return when (this) {
        is Cons -> Cons(head, tail.append(l))
        is Nil -> l
    }
}

здесь второй список берется в качестве параметра для функции добавления, однако Kotlin будет отмечать этот параметр — это потому, что можно возвращать ко-вариантный тип, но не принимать его в качестве параметра. Однако, поскольку мы знаем, что список в его текущей форме неизменен, я могу обойти это, пометив параметр типа аннотацией «@UnsafeVariance».

Раскладной

Операции складывания позволяют «свернуть» список в результат, основанный на некоторой агрегации по отдельным элементам в нем.

Рассмотрим foldLeft:

01
02
03
04
05
06
07
08
09
10
fun <B> foldLeft(z: B, f: (B, A) -> B): B {
    tailrec fun foldLeft(l: List<A>, z: B, f: (B, A) -> B): B {
        return when (l) {
            is Nil -> z
            is Cons -> foldLeft(l.tail, f(z, l.head), f)
        }
    }
 
    return foldLeft(this, z, f)
}

Если список должен состоять из элементов (2, 3, 5, 8), то foldLeft эквивалентен «f (f (f (f (z (2), 3), 5), 8)»

С этой функцией более высокого порядка функция суммы может быть выражена следующим образом:

1
2
val l = Cons(1, Cons(2, Cons(3, Cons(4, Nil))))
assertThat(l.foldLeft(0, {r, e -> r + e})).isEqualTo(10)

FoldRight выглядит следующим образом в Kotlin:

1
2
3
4
5
6
fun <B> foldRight(z: B, f: (A, B) -> B): B {
    return when(this) {
        is Cons -> f(this.head, tail.foldRight(z, f))
        is Nil -> z
    }
}

Если список должен состоять из элементов (2, 3, 5, 8), тогда foldRight эквивалентен «f (2, f (3, f (5, f (8, z))))»

Эта версия foldRight, хотя внешний вид кулера не является хвостовой рекурсией, может быть реализована более дружественная к стеку версия с использованием ранее определенной хвостовой рекурсивной foldLeft путем простого обращения к List и внутреннего вызова foldLeft следующим образом:

1
2
3
4
5
6
7
fun reverse(): List<A> {
    return foldLeft(Nil as List<A>, { b, a -> Cons(a, b) })
}
 
fun <B> foldRightViaFoldLeft(z: B, f: (A, B) -> B): B {
    return reverse().foldLeft(z, { b, a -> f(a, b) })
}

карта и плоская карта

map — это функция, которая преобразует элемент этого списка:

1
2
3
4
5
6
fun <B> map(f: (A) -> B): List<B> {
    return when (this) {
        is Cons -> Cons(f(head), tail.map(f))
        is Nil -> Nil
    }
}

Пример использования этой функции:

1
2
3
val l = Cons(1, Cons(2, Cons(3, Nil)))
val l2 = l.map { e -> e.toString() }
assertThat(l2).isEqualTo(Cons("1", Cons("2", Cons("3", Nil))))

Вариант карты, в котором функция преобразования возвращает другой список, а окончательные результаты сглаживают все, что лучше всего продемонстрировать на примере после реализации:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
fun <B> flatMap(f: (a: A) -> List<@UnsafeVariance B>): List<B> {
    return flatten(map { a -> f(a) })
}
 
companion object {
    fun <A> flatten(l: List<List<A>>): List<A> {
        return l.foldRight(Nil as List<A>, { a, b -> a.append(b) })
    }
}
 
 
val l = Cons(1, Cons(2, Cons(3, Nil)))
 
val l2 = l.flatMap { e -> list(e.toString(), e.toString()) }
 
assertThat(l2)
        .isEqualTo(
                Cons("1", Cons("1", Cons("2", Cons("2", Cons("3", Cons("3", Nil)))))))

Это охватывает основы, связанные с реализацией структуры функциональных списков данных с использованием Kotlin, было несколько грубых моментов по сравнению с версией scala, но я думаю, что это в основном работает. По общему признанию, образец может быть значительно улучшен, если у вас есть какие-либо замечания о том, как улучшить код, пожалуйста, пришлите мне PR на
GitHub репо для этого образца или как комментарий к этому сообщению.

См. Оригинальную статью здесь: Kata — реализация функциональной структуры данных List в Kotlin.

Мнения, высказанные участниками Java Code Geeks, являются их собственными.

44
Share: