15. Функции, closures

29 ноември 2017

Административни неща

Видеото няма да го бъде
Трето домашно, довечера!

Преговор

Списъци!
Едносвързан списък-стек с Box-ове
Persistent списък със споделени Rc-та
Mutable double-ended опашка
Unsafe едносвързана опашка

Итератори

Ще разгледаме част от домашното и как можете да го правите с итератори

Итератори

За контекст така изглежда структурата Polynomial

pub struct Polynomial {
    /// x^3 + 2*x^2 + 3
    /// vec![1.0, 2.0, 0.0, 3.0]
    coefs: Vec<f64>
}

impl Polynomial {
    fn new() -> Self {
        Self {
            coefs: Vec::new()
        }
    }
}

Итератори

Умножение на полиноми

fn mul(self, other: Self) -> Self::Output {
    // Allocations can be optimized significantly
    other.coefs.into_iter().rev().enumerate().fold(Polynomial::new(), |acc, (i, coef)| {
        let base = self.clone();
        base.coefs.resize(self.coefs.len() + i, 0.0);

        acc + base * coef
    })
}

Итератори

Събиране на полиноми

fn add(self, other: Self) -> Self::Output {
    if self.coefs.len() == 0 { return other; }
    if other.coefs.len() == 0 { return self; }

    let endless_zero = ::std::iter::repeat(0.0);
    let rev_self = self.coefs.iter().rev();
    let rev_other = other.coefs.iter().rev();

    // Pad the coefs with 0s to align them
    let mut coefs = if self.coefs.len() < other.coefs.len() {
        rev_self.chain(endless_zero).zip(rev_other).map(|(x, y)| x + y).collect::<Vec<_>>()
    } else {
        rev_self.zip(rev_other.chain(endless_zero)).map(|(x, y)| x + y).collect::<Vec<_>>()
    };

    // Can't use rev on the map iterator since Chain is not ExactSizeIterator
    // and Repeat is not a DoubleEndedIterator
    coefs.reverse();

    Polynomial::from(coefs)
}

Итератори

Интерполация

pub fn interpolate(points: Vec<(f64, f64)>) -> Option<Self> {
    // Skipping validations

    // Split the points into `x` set and `y` set
    let (xs, ys): (Vec<f64>, Vec<f64>) = points.into_iter().unzip();

    // `zero` can be substituted by `new` for performance but this is closer to valid math
    let poly = ys.into_iter().enumerate().fold(Polynomial::zero(), |acc, (i, y)| {
        // Skip calculations when multiplication with 0 is expected
        if y < ::std::f64::EPSILON {
            return acc;
        }

        // Calculate Lagrange basis polynomial
        let basis = xs.iter().enumerate().fold(Polynomial::one(), |acc, (j, x)| {
            if i == j {
                acc
            } else {
                // (x - xj) / (xi - xj)
                acc * (Polynomial::from(vec![1.0, -x]) / (xs[i] - x))
            }
        });

        acc + basis * y
    });

    Some(poly)
}

Функции

Знаем как се пишат функции

fn add_one (x: u32) -> u32 {
    x + 1
}

Но какъв е типът на функция

let _: () = add_one;

Функции

указатели

fn(u32) -> u32 {main::add_one}

Всяка функция има уникален тип
Не можем да го напишем (невалиден синтаксис)
Защо?
Никаква идея. Не се използва за нищо

Функции

указатели

Какво се използва?

fn(u32) -> u32
function pointer
non null
cast to *const () and usize

Функции

указатели

fn add_one (x: u32) -> u32 { x + 1 }
fn add_two (x: u32) -> u32 { x + 2 }

let mut f: fn(u32) -> u32 = add_one;
assert_eq!(f(1), 2);

f = add_two;
assert_eq!(f(1), 3);

Closures

syntax

fn  add_one_v1   (x: u32) -> u32 { x + 1 }
let add_one_v2 = |x: u32| -> u32 { x + 1 };
let add_one_v3 = |x|             { x + 1 };
let add_one_v4 = |x|               x + 1  ;

Closure vs fn

Каква е разликата между функция и closure.

Closures могат да използват променливи дефинирани по-горе в scope-a.

fn main() {
    let other = String::from("дядо");               // <-+
                                                    //   |
    Some("баба").map(|s| s.len() + other.len());    // --+
}

Имплементация

/// Структура в която запомняме променливите, които сме прихванали
struct State {
    other: String,
}

impl State {
    /// Функция която съдържа логиката
    fn call(&self, s: &str) -> usize {
        s.len() + self.other.len()
    }
}

Имплементация

fn map_option(opt: Option<&str>, f: State) -> Option<usize> {
    match opt {
        Some(s) => Some(f.call(s)),
        None => None,
    }
}

fn main() {
    let other = String::from("дядо");

    map_option(Some("баба"), State { other });
}

Move closure

Една подробност - closure-ите не консумират прихванатите променливи

let other = String::from("дядо");

println!("{}", Some("баба").map(|s| s.len() + other.len()));
println!("{}", other);    // Ок

println!("{}", map_option(Some("баба"), State { other }));
println!("{}", other);    // комп. грешка - use of moved value `other`

Move closure

По подразбиране променливите се прихващат по референция

Можем да променим това с ключовата дума move

|s| s.len() + other.len();

// генерира

struct State<'a> {
    other: &'a String
}

move |s| s.len() + other.len();

// генерира

struct State {
    other: String
}

Closures

let other = String::from("дядо");

let closure = |s| s.len() + other.len();

Some("баба").map(closure);

let other = String::from("дядо");

let closure = State { other: &other };

struct State<'a> {
    other: &'a String,
}

impl<'a> ??? for State<'a> {
    fn call(self: ???, s: &str) -> usize {
        s.len() + self.other.len()
    }
}

Some("баба").map(closure);

Fn traits

Fn
FnMut
FnOnce

Синтаксис

Fn()
FnMut(u32, u32) -> bool
FnOnce() -> String

Fn traits

FnOnce

// опростено
trait FnOnce<Args> {
    type Output;
    fn call_once(self, args: Args) -> Self::Output;
}

self
може да се извика само веднъж
в комбинация с move closure може да се използва за прехвърляне на собственост

Fn traits

FnMut

// опростено
trait FnMut<Args>: FnOnce<Args> {
    fn call_mut(&mut self, args: Args) -> Self::Output;
}

&mut self

Fn traits

Fn

// опростено
trait Fn<Args>: FnMut<Args> {
    fn call(&self, args: Args) -> Self::Output;
}

&self

Fn traits

Когато създадем closure, компилатора имплементира всички trait-ове, който може

FnOnce + FnMut + Fn
FnOnce + FnMut
FnOnce

Не можем да имаме само Fn или FnMut заради ограниченията на трейтовете
Ако това ви се струва странно, помислете как бихте имплементирали FnMut и FnOnce ако вече имате Fn

Fn traits

Да имплементираме Fn trait-овете за нашия тип State

error: the precise format of `Fn`-family traits' type parameters is subject to change.
       Use parenthetical notation (Fn(Foo, Bar) -> Baz) instead

error: rust-call ABI is subject to change
...
= help: add #![feature(unboxed_closures)] to the crate attributes to enable

error: use of unstable library feature 'fn_traits'
...
= help: add #![feature(fn_traits)] to the crate attributes to enable

... или пък не

Taking closures

По-популярния начин за взимане на closure е чрез static dispatch

fn eval_and_increment<F>(f: F) -> usize where F: Fn_???() -> usize {
    f() + 1
}

assert_eq!(eval_and_increment(|| 1), 2);

Taking closures

Кой Fn trait да сложим за ограничение?

добре е да налагаме възможно най-малко ограничения
FnOnce - най-добре
FnMut - ок
Fn - в последен случай
пробваме в този ред - което компилаторът ни разреши

Taking closures

fn eval_and_increment<F>(f: F) -> usize where F: FnOnce() -> usize {
    f() + 1
}

assert_eq!(eval_and_increment(|| 1), 2);

Saving closures

Да си направим адаптор за итератор, който работи подобно на адаптора връщан от `Iterator::map()`

struct Map<I, F, B> where
    I: Iterator,
    F: FnMut(I::Item) -> B
{
    iter: I,
    f: F,
}

Saving closures

impl<I, F, B> Iterator for Map<I, F, B> where
    I: Iterator,
    F: FnMut(I::Item) -> B
{
    type Item = B;

    fn next(&mut self) -> Option<Self::Item> {
        match self.iter.next() {
            Some(item) => Some((self.f)(item)),
            None => None,
        }
    }
}

Saving closures

// vec![1, 2, 3].into_iter().map(|x| x * 3)
let map = Map {
    iter: vec![1, 2, 3].into_iter(),
    f: |x| x * 3,
};

let v = map.collect::<Vec<_>>();
println!("{:?}", v);

[3, 6, 9]

Returning closures

fn get_incrementer() -> ??? {
    |x| x + 1
}

Returning closures

Да проверим какъв е типът на closure-а

let _: () = |x| x + 1;

= note: expected type `()`
           found type `[closure@src/main.rs:2:17: 2:26]`

Тип генериран от компилатора, това не ни е полезно

Returning closures

Вариант 1

Ако closure не прихваща променливи, той може автоматично да се сведе до указател към функция

fn get_incrementer() -> fn(i32) -> i32 {
    |x| x + 1
}

Returning closures

Вариант 2

Често се налага да прихванем променливи

fn curry(a: u32) -> ??? {
    |b| a + b
}

Returning closures

Вариант 2

Можем да използваме Trait objects

struct F<'a> {
    closure: &'a Fn()
}

struct F {
    closure: Box<Fn()>
}

Returning closures

Вариант 2

Така дали ще е добре?

fn curry(a: u32) -> Box<Fn(u32) -> u32> {
    Box::new(|b| a + b)
}

Returning closures

Вариант 2

move

fn curry(a: u32) -> Box<Fn(u32) -> u32> {
    Box::new(move |b| a + b)
}

assert_eq!(curry(1)(2), 3);

Closures & lifetimes

fn curry<'a>(a: &'a u32) -> Box<Fn(&u32) -> u32> {
    Box::new(move |b| a + b)
}

error[E0495]: cannot infer an appropriate lifetime due to conflicting requirements
...

Closures & lifetimes

fn curry<'a>(a: &'a u32) -> Box<Fn(&u32) -> u32> {
    struct State<'b> {
        a: &'b u32
    }

    // impl Fn, FnMut, FnOnce for State

    let state = State { a };    // State<'a>
    Box::new(state)             // очаква 'static
}

Closures & lifetimes

Lifetime на структура

Какво означава обект (който не е референция) да има 'static lifetime

Lifetime-а показва максимално ограничение до което може да живее обект

struct Foo<'a> { a: &'a i32 }

{
    let a = 10;                     // ---+- 'a
                                    //    |
    let foo = Foo { a: &a };        // ---+- foo: 'a
                                    //    |
}                                   // <--+

Closures & lifetimes

Lifetime на структура

Когато обект не държи референции няма такова ограничение

Затова се приема че обекта има 'static lifetime

struct Foo { a: i32 }

{
    let a = 10;

    let foo = Foo { a: a };         // foo: 'static
}

Closures & lifetimes

По подразбиране се очаква trait object-а да няма такова ограничение

Box<Fn(&u32) -> u32> -> Box<Fn(&u32) -> u32 + 'static>

Ако имаме ограничение трябва да го окажем изрично

fn curry<'a>(a: &'a u32) -> Box<Fn(&u32) -> u32 + 'a> {
    Box::new(move |b| a + b)
}

assert_eq!(curry(&1)(&2), 3);

EventEmitter

layout

Нека опитаме да напишем прост event emitter със следните изисквания:

Generic по типа на съобщенията и типа на данните които се излъчват
on - регистрира слушател
off - премахва слушател
emit - излъчва съобщение с данни

EventEmitter

usage

let mut emitter = EventEmitter::new();

let _  = emitter.on("boot", |p: String| println!("{}", p));
let id = emitter.on("boot", |_| println!("hi"));

emitter.off(id);

emitter.emit("boot", "woot".to_string());

EventEmitter

structures

Ето как би изглеждала структурата

struct EventEmitter<E, P> {
    map: HashMap<E, Vec<Box<Fn(P)>>>
}

EventEmitter

structures

Изглежда лесно...

EventEmitter

structures

Но нещата не са толкова прости

type Id = u64;

struct Listener<P> {
    id: Id,
    closure: Box<Fn(P) + 'static>
}

struct EventEmitter<E, P> where E: Eq + Hash, P: Clone {
    next_id: Id,
    map: HashMap<E, Vec<Listener<P>>>
}

EventEmitter

constructors

impl<P> Listener<P> {
    fn new<F>(id: Id, f: F) -> Self where F: Fn(P) + 'static {
        Self {
          id,
          closure: Box::new(f)
        }
    }
}

impl<E, P> EventEmitter<E, P> where E: Eq + Hash, P: Clone {
    fn new() -> Self {
        Self {
            next_id: Id::default(),
            map: HashMap::new()
        }
    }
}

EventEmitter

on

Място, където map::Entry ще ни улесни

impl<E, P> EventEmitter<E, P> where E: Eq + Hash, P: Clone {
    fn on<F>(&mut self, event: E, listener: F) -> Id where F: Fn(P) + 'static {
        let id = self.next_id;
        let listeners = self.map.entry(event).or_insert(Vec::new());

        listeners.push(Listener::new(self.next_id, listener));

        self.next_id += 1;
        id
    }
}

EventEmitter

off

fn off(&mut self, id: Id) -> bool {
    for (_, listeners) in self.map.iter_mut() {
        let position = listeners.iter().position(|x| x.id == id);

        if let Some(idx) = position {
            listeners.remove(idx);
            return true;
        }
    }

    false
}

EventEmitter

emit

Ето една възможност да използваме Borrow

impl<E, P> EventEmitter<E, P> where E: Eq + Hash, P: Clone {
    fn emit<B>(&self, event: B, payload: P) -> bool where B: Borrow<E> {
        let event = event.borrow();

        match self.map.get(event) {
            Some(listeners) => {
                // Клонираме данните, за да може да ги подадем на всички слушатели
                listeners.iter().for_each(|f| (f.closure)(payload.clone()));
                true
            },
            None => false
        }
    }
}

Въпроси

http://fmi.rust-lang.bg/