discrimination-tree 0.1.1

discrimination tree term indexing
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

use crate::*;
use Term::Variable as X;
use Term::*;

fn constant(c: &'static str) -> Term<&'static str> {
    Function(c, vec![])
}

fn function(
    f: &'static str,
    children: Vec<Term<&'static str>>,
) -> Term<&'static str> {
    Function(f, children)
}

fn build_index() -> Index<&'static str, u32> {
    let mut index = Index::new();

    // f(g(a, *), c)
    index.insert(
        function(
            "f",
            vec![function("g", vec![constant("a"), X]), constant("c")],
        ),
        1,
    );
    // f(g(*, b), *)
    index.insert(
        function("f", vec![function("g", vec![X, constant("b")]), X]),
        2,
    );
    // f(g(a, b), a)
    index.insert(
        function(
            "f",
            vec![
                function("g", vec![constant("a"), constant("b")]),
                constant("a"),
            ],
        ),
        3,
    );
    // f(g(*, c), b)
    index.insert(
        function(
            "f",
            vec![function("g", vec![X, constant("c")]), constant("b")],
        ),
        4,
    );
    // f(*, *)
    index.insert(function("f", vec![X, X]), 5);
    // f(g(b, c), *)
    index.insert(
        function(
            "f",
            vec![function("g", vec![constant("b"), constant("c")]), X],
        ),
        6,
    );

    index
}

#[test]
fn insertion() {
    let index = build_index();
    assert_eq!(index.symbols.len(), 5);
    assert_eq!(index.nodes.len(), 18);
    assert_eq!(index.connections.len(), 11);
}

#[test]
fn generalisation() {
    let index = build_index();
    let query = function(
        "f",
        vec![
            function("g", vec![constant("a"), constant("c")]),
            constant("b"),
        ],
    );
    let mut unifiers = index.possible_unifiers(&query);
    assert_eq!(unifiers.next(), Some(&4));
    assert_eq!(unifiers.next(), Some(&5));
    assert_eq!(unifiers.next(), None);
}

#[test]
fn unification() {
    let index = build_index();
    let query = function(
        "f",
        vec![function("g", vec![constant("b"), X]), constant("a")],
    );
    let mut unifiers = index.possible_unifiers(&query);
    assert_eq!(unifiers.next(), Some(&6));
    assert_eq!(unifiers.next(), Some(&2));
    assert_eq!(unifiers.next(), Some(&5));
    assert_eq!(unifiers.next(), None);
}