1use crate::{EqPoly, FieldExt};
 2
 3#[derive(Clone, Debug)]
 4pub struct SparseMLPoly<F> {
 5    pub evals: Vec<(usize, F)>,
 6    pub num_vars: usize,
 7}
 8
 9impl<F: FieldExt> SparseMLPoly<F> {
10    pub fn new(evals: Vec<(usize, F)>, num_vars: usize) -> Self {
11        Self { evals, num_vars }
12    }
13
14    pub fn from_dense(dense_evals: Vec<F>) -> Self {
15        let sparse_evals = dense_evals
16            .iter()
17            .filter(|eval| **eval != F::ZERO)
18            .enumerate()
19            .map(|(i, eval)| (i, *eval))
20            .collect::<Vec<(usize, F)>>();
21        let num_vars = (dense_evals.len() as f64).log2() as usize;
22
23        Self {
24            evals: sparse_evals,
25            num_vars,
26        }
27    }
28
29    pub fn eval(&self, t: &[F]) -> F {
30        // Evaluate the multilinear extension of the polynomial `a`,
31        // over the boolean hypercube
32
33        let eq_poly = EqPoly::new(t.to_vec());
34        let eq_evals = eq_poly.evals();
35
36        let mut result = F::ZERO;
37
38        for eval in &self.evals {
39            result += eq_evals[eval.0] * eval.1;
40        }
41
42        result
43    }
44}