unbound 0.1.2

Locally nameless representation with automatic capture-avoiding substitution and alpha equivalence
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

//! Fresh name generation monad

use std::cell::RefCell;
use std::collections::HashSet;
use std::rc::Rc;

use crate::Name;

/// State for fresh name generation
#[derive(Clone, Debug)]
pub struct FreshState {
    counter: usize,
    used_names: HashSet<String>,
}

impl FreshState {
    pub fn new() -> Self {
        FreshState {
            counter: 0,
            used_names: HashSet::new(),
        }
    }
}

impl Default for FreshState {
    fn default() -> Self {
        Self::new()
    }
}

/// The Fresh monad for generating fresh names
pub struct FreshM<T> {
    computation: Box<dyn FnOnce(Rc<RefCell<FreshState>>) -> T>,
}

impl<T> FreshM<T> {
    /// Create a new FreshM computation
    pub fn new<F>(f: F) -> Self
    where
        F: FnOnce(Rc<RefCell<FreshState>>) -> T + 'static, {
        FreshM {
            computation: Box::new(f),
        }
    }

    /// Return a pure value
    pub fn pure(value: T) -> Self
    where
        T: 'static, {
        FreshM::new(move |_| value)
    }

    /// Run the fresh computation with a new state
    pub fn run_fresh(self) -> T {
        let state = Rc::new(RefCell::new(FreshState::new()));
        (self.computation)(state)
    }

    /// Run with an existing state
    pub fn run_with_state(self, state: Rc<RefCell<FreshState>>) -> T {
        (self.computation)(state)
    }

    /// Map a function over the result
    pub fn map<U, F>(self, f: F) -> FreshM<U>
    where
        F: FnOnce(T) -> U + 'static,
        T: 'static, {
        FreshM::new(move |state| {
            let result = self.run_with_state(state.clone());
            f(result)
        })
    }

    /// Monadic bind operation
    pub fn flat_map<U, F>(self, f: F) -> FreshM<U>
    where
        F: FnOnce(T) -> FreshM<U> + 'static,
        T: 'static,
        U: 'static, {
        FreshM::new(move |state| {
            let result = self.run_with_state(state.clone());
            let next = f(result);
            next.run_with_state(state)
        })
    }

    /// Alias for flat_map
    pub fn and_then<U, F>(self, f: F) -> FreshM<U>
    where
        F: FnOnce(T) -> FreshM<U> + 'static,
        T: 'static,
        U: 'static, {
        self.flat_map(f)
    }
}

/// Trait for types that can provide fresh names
pub trait Fresh {
    /// Generate a fresh variant of this value
    fn fresh(&self) -> FreshM<Self>
    where
        Self: Sized;
}

impl<T> Fresh for Name<T> {
    fn fresh(&self) -> FreshM<Self> {
        let base = self.string().to_string();
        FreshM::new(move |state| {
            let mut st = state.borrow_mut();
            let mut candidate = base.clone();
            let mut suffix = 0;

            // Find a unique name
            while st.used_names.contains(&candidate) {
                suffix += 1;
                candidate = format!("{}{}", base, suffix);
            }

            st.used_names.insert(candidate.clone());
            st.counter += 1;

            Name::with_index(candidate, st.counter - 1)
        })
    }
}

/// Helper to run a FreshM computation
pub fn run_fresh<T>(computation: FreshM<T>) -> T {
    computation.run_fresh()
}