Начало
Учебные материалы
Функциональное программирование на Scheme и Kotlin
История функциональных языков Базовые типы данных Управляющие конструкции Списки, обработка списков Ленивые вычисления, частичное применение, запоминание Классы в Kotlin
Ленивые вычисления, частичное применение, запоминание
##### Ленивые вычисления
```scheme
; Ленивые версии car, cdr, cons
(define lazy-car car)
(define (lazy-cdr ls) (force (cdr ls)))
(define-syntax lazy-cons
(syntax-rules ()
((_ a b) (cons a (delay b)))))
; Ленивая версия map
(define (lazy-map fn . lss)
(if (memq '() lss) '()
(lazy-cons (apply fn (map lazy-car lss))
(apply lazy-map fn (map lazy-cdr lss)))))
; Ленивая версия filter
(define (lazy-filter pred ls)
(if (null? ls) '()
(let
((h (lazy-car ls)))
(if (pred h)
(lazy-cons h (lazy-filter pred (lazy-cdr ls)))
(lazy-filter pred (lazy-cdr ls))))))
; n-й элемент ленивого списка
(define (lazy-ref ls n)
(if (= n 0)
(lazy-car ls)
(lazy-ref (lazy-cdr ls) (- n 1))))
; Первые n элементов ленивого списка
(define (lazy-take ls n)
(if (= n 0)
'()
(cons (lazy-car ls) (lazy-take (lazy-cdr ls) (- n 1)))))
; Бесконечная последовательность через первый элемент и функцию изменения
(define (inf-seq a0 f)
(lazy-cons a0 (inf-seq (f a0) f)))
; Примеры
; Последовательность Фибоначчи
(define fib
(lazy-cons 1
(lazy-cons 1
(lazy-map + fib (lazy-cdr fib)))))
(lazy-take fib 20)
; Последовательность целых чисел с 1
(define intseq1 (inf-seq 1 (lambda (x) (+ x 1))))
(lazy-take intseq1 10)
```
##### Частичное применение функций, функции высшего порядка
```scheme
; Композиция функций
(define (compose f g) (lambda (x) (f (g x))))
; Частичное применение для функции с 2 параметрами
(define (partial2 f)
(case-lambda
((x) (lambda (y) (f x y)))
((x y) (f x y))
))
; Частично применяемый plus
(define plus (partial2 (lambda (x y) (+ x y))))
((plus 2) 3) ; использование карринга: 5
(plus 2 3) ; 5
; Частично применяемый cons
(define part-cons (partial2 cons))
; Редукция определяется с использованием карринга
(define (part-foldr f s x)
(if (null? x) s
((f (car x)) (part-foldr f s (cdr x))) ; карринг
))
; Определение отображения через редукцию
(define part-map (partial2
(lambda (f x) (part-foldr (compose part-cons f) '() x))))
; Использование частнчного применения для создания новой функции
(define inc1 (part-map (plus 1)))
(inc1 '(2 7 5)) ; (3 8 6)
; Конвейер
(define (pipe x . fn)
(if (null? fn) x
(apply pipe ((car fn) x) (cdr fn))
)
)
(define (mul2 x) (* x 2))
(define plus5 (plus 5))
; С использованием конвейера
(pipe 2 mul2 plus5)
; Без использования конвейера
(plus5 (mul2 2))
```
##### Запоминание
```scheme
(define (memoize f)
(let ((memo (make-eq-hashtable)))
(lambda (n)
(if (hashtable-contains? memo n) '()
(hashtable-set! memo n (f n)))
(hashtable-ref memo n '())
)))
(define power (lambda (n)
(if (= n 0) 1
(+ (power (- n 1)) (power (- n 1)))
)))
(power 27) ; медленно
(define power (memoize power))
(power 27) ; теперь быстро
```
### Язык Kotlin
##### Бесконечные последовательности
```kotlin
// через приостанавливаемые (suspend) функции
val fib=sequence {
var a=1L; var b=1L; var c:Long
while(true) {
yield(a)
c=a+b; a=b; b=c
}
}
println(fib.take(20).toList())
// через генератор
val intseq1=generateSequence(1){it+1}
println(intseq1.take(10).toList())
println(intseq1.filter{it%2==0}.map{it*it}.take(10).toList()) // квадраты четных чисел
```
##### Ленивые вычисления
```kotlin
typealias LazyList=Pair<Int,Lazy<Any> >
fun intseq(m:Int):LazyList=LazyList(m, lazy {intseq(m+1)} )
fun take(k:Int, x:LazyList):List<Int> = if(k==0) listOf() else
listOf(x.first)+take(k-1, x.second.value as LazyList)
take(10,intseq(1))
```
##### Частичное применение функций, функции высшего порядка
```kotlin
class Partial<T>
fun <T> partial(): Partial<T> = Partial()
// Для функций с 2 параметрами
operator @Suppress("UNUSED_PARAMETER")
fun <P1, P2, R> ((P1, P2) -> R).invoke(p1: P1,
p2: Partial<P2> = partial()): (P2) -> R {
return { p2: P2 -> this(p1, p2) }
}
// Для функций с 3 параметрами
operator @Suppress("UNUSED_PARAMETER")
fun <P1, P2, P3, R> ((P1, P2, P3) -> R).invoke(p1: P1,
p2: Partial<P2> = partial(), p3: Partial<P3> = partial()): (P2, P3) -> R {
return { p2: P2, p3: P3 -> this(p1, p2, p3) }
}
operator @Suppress("UNUSED_PARAMETER")
fun <P1, P2, P3, R> ((P1, P2, P3) -> R).invoke(p1: P1, p2: P2,
p3: Partial<P3> = partial()): (P3) -> R {
return { p3: P3 -> this(p1, p2, p3) }
}
// Пример использования
val plus={a:Int,b:Int -> a+b} // функция с 2 параметрами
plus(5,15) // 20
plus(5)(15) // карринг тоже работает
val plus5=plus(5) // подстановка 1-го параметра, получаем функцию с 1 параметром
plus5(15) // 20
// Композиция функций
infix fun <X, Y, Z> ((Y) -> Z).compose(f: (X) -> Y): (X) -> Z {
return { p: X -> this(f(p)) }
}
// Пример использования
val mul2 = { i: Int -> i * 2 }
// Новая функция определяется через операцию над функциями
val mul2andPlus5 = plus5 compose mul2
mul2andPlus5(2) // 9
```
##### Конвейер
Конвейер позволяет уменьшить количество скобок, и порядок применения функций читается слева направо.
Аналогичный эффект получается при использовании методов,
так как сначала указывается объект, затем действие. Пример выше
``intseq1.filter{it%2==0}.map{it*it}.take(10).toList()`` было бы сложно понять при использовании обычных функций.
```
infix inline fun <P, R> P.pipe(t: (P) -> R): R = t(this)
// Использование конвейера
2 pipe mul2 pipe plus5 // 9
// То же, без использования конвейера
// Функция, которая применяется последней, указана первой
plus5(mul2(2))
```
##### Запоминание
```kotlin
fun <P, R> ((P)->R).memoize(): (P) -> R {
val memo: MutableMap<P, R> = HashMap()
return { memo.getOrPut(it, { this(it) }) }
// 2-й аргумент метода getOrPut передается
// ленивым способом (call-by-name), т.к. его нужно
// вычислять только при отсутствии ключа в хэш-таблице
}
// Пример использования
lateinit var power:(Int)->Int
power={n:Int->if(n==0) 1 else power(n-1)+power(n-1)}
power(27) // 134217728, несколько секунд
power=power.memoize()
power(27) // теперь мгновенно
power(30) // тоже
```
