prune-lang 0.2.1

Prune is a constraint logic programming language with branching heuristic.
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

datatype Tree[a] where
| Empty
| Node(Tree[a], a, Tree[a])
end

function insert(tree: Tree[Int], x: Int) -> Tree[Int]
begin
    match tree with
    | Empty => Node(Empty, x, Empty)
    | Node(left, y, right) =>
        condition
        | x < y => Node(insert(left, x), y, right)
        | x > y => Node(left, y, insert(right, x))
        | x == y => tree
        end
    end
end

function is_sorted(tree: Tree[Int]) -> Bool
begin
    match tree with
    | Empty => true
    | Node(left, x, right) =>
        is_sorted_max(left, x) && is_sorted_min(right, x)
    end
end

function is_sorted_min(tree: Tree[Int], min: Int) -> Bool
begin
    match tree with
    | Empty => true
    | Node(left, x, right) =>
        x > min &&
        is_sorted_min_max(left, min, x) && is_sorted_min(right, x)
    end
end

function is_sorted_max(tree: Tree[Int], max: Int) -> Bool
begin
    match tree with
    | Empty => true
    | Node(left, x, right) =>
        x < max &&
        is_sorted_max(left, x) && is_sorted_min_max(right, x, max)
    end
end

function is_sorted_min_max(tree: Tree[Int], min: Int, max: Int) -> Bool
begin
    match tree with
    | Empty => true
    | Node(left, x, right) =>
        x > min && x < max &&
        is_sorted_min_max(left, min, x) && is_sorted_min_max(right, x, max)
    end
end

function example(tree: Tree[Int], x: Int)
begin
    guard is_sorted(tree) = true;
    guard is_sorted(insert(tree, x)) = false;
end

query example(depth_step=5, depth_limit=25, answer_limit=1)