/
Datalog.elm
144 lines (113 loc) · 3.99 KB
/
Datalog.elm
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
132
133
134
135
136
137
138
139
140
141
142
143
144
module Datalog exposing (Atom, Rule, Term, atom, rule, ruleToPlan, string, var)
import Database exposing (Constant)
import Dict
type Problem
= CannotPlanFact
type Rule
= Rule Atom (List Atom)
rule : Atom -> List Atom -> Rule
rule =
Rule
ruleToPlan : Rule -> Result Problem Database.QueryPlan
ruleToPlan (Rule (Atom _ headTerms) bodyAtoms) =
let
planned =
case bodyAtoms of
[] ->
Err CannotPlanFact
[ only ] ->
Ok (atomToPlan only)
first :: rest ->
List.foldl
(\nextAtom ( rightNames, rightPlan ) ->
let
( leftNames, leftPlan ) =
atomToPlan nextAtom
in
( leftNames ++ rightNames
, Database.Join
{ left = leftPlan
, right = rightPlan
, fields =
Dict.merge
(\_ _ soFar -> soFar)
(\_ left right soFar -> ( left, right ) :: soFar)
(\_ _ soFar -> soFar)
(Dict.fromList (List.indexedMap (\i field -> ( field, i )) leftNames))
(Dict.fromList (List.indexedMap (\i field -> ( field, i )) rightNames))
[]
}
)
)
(atomToPlan first)
rest
|> Ok
in
planned
|> Result.map
(\( names, plan ) ->
Database.Project
(List.filterMap
(\term ->
case term of
Variable name ->
-- TODO: validate that all atoms in the head appear in
-- the body
indexOf name names
Constant _ ->
-- TODO: validate that constant terms don't appear in the
-- head, or deal with them somehow.
Nothing
)
headTerms
)
plan
)
indexOf : a -> List a -> Maybe Int
indexOf =
indexOfHelp 0
indexOfHelp : Int -> a -> List a -> Maybe Int
indexOfHelp idx item items =
case items of
[] ->
Nothing
first :: rest ->
if first == item then
Just idx
else
indexOfHelp (idx + 1) item rest
type Atom
= Atom String (List Term)
atom : String -> List Term -> Atom
atom =
Atom
atomToPlan : Atom -> ( List String, Database.QueryPlan )
atomToPlan (Atom name terms) =
terms
|> List.indexedMap Tuple.pair
|> List.foldr
(\( fieldNum, term ) ( termNames, plan ) ->
case term of
Variable var_ ->
( var_ :: termNames, plan )
Constant constant ->
( "_" :: termNames
, plan
|> Database.Select
(Database.Predicate
fieldNum
Database.Eq
(Database.Constant constant)
)
)
)
( [], Database.Read name )
type Term
= Variable String
| Constant Constant
var : String -> Term
var =
Variable
string : String -> Term
string =
Constant << Database.String