On Wednesday, March 8, 2017 at 2:57:40 PM UTC+1, Evgenii Moiseenko wrote:
>
> Association list was my first idea, and I actually use them currently.
>
> But I am curious is there more efficient solution ?
>
> O(1) for lookup would be the best option, but intuitively it seems hard to
> implement something like hash-tables in relational manner.
> Implementing a search tree seems to be more feasible.
>
> Nevertheless is there any research or papers in that area ? (efficient
> relational map-like data structures).
>
The way the algorithm might be different and the datastructure can be
different, you might not need build map to solve the problem you face.
Using microkanren we can define the following problem
(run * (X00)
(fresh (X01 X10 X11)
(== X00 X10)
(== X01 X11)))
of course it outpus that run* can be anything!
(run * (X11)
(fresh (name birthday)
(== name "amirouche")
(== birthday X11)))
of course it produce anything. BTW the problem look like a hashmap problem.
Now They exist programs that don't have useful solution, I mean I don't
know a
program that does something useful with only the a named variable as
output.
That said you can add new rules to ground the variables. In the above case
I
can imagine another rule that does allow to resolve the problem:
(run * (X11)
(fresh (name birthday)
(== name "amirouche")
(== birthday X11)
(== X11 42))) ;; epoc time
We could also model the problem differently, like feature structure does.
For instance:
(run* (birthday)
(fresh (problem)
(== probleme `((name amirouche)
(birthday ,birthday))
;; we can simply create another rule that will allow to set birthday
to something)
(== birthday 42)))
Here are three minikanren programs, that do something using map. But don't
seem very
useful to me. Maybe this is A/B problem?
I am not entirely understanding minikanren myself. Just trying to help. For
instance, I try
to represent the dependency problem using minikanren.
Given 4 softwares ff2, ff3, gk2, gtk3 there is the following depenendencies
between them
ff2 → !ff3
ff3 → !ff2
ff2 → gtk2
ff3 → gtk3
In terms of CNF form it translates to the following:
(and (or (not (ff2) (not ff3)
(or (not (ff3) (not ff2)
(or (not (ff2) gtk2)
(or (not (ff3) gtk3)))
Otherwise said ff2 can not be installed with ff3. When installing ff2
install gtk2, if you install ff3 you must install gtk3
среда, 8 марта 2017 г., 5:21:42 UTC+3 пользователь Dan Friedman написал:
>>
>> Use assv as a model to look up variable in an alist.
>> Then take that code of assv and write assvo.
>>
>> ... Dan
>>
>> On Tue, Mar 7, 2017 at 7:17 PM, Evgenii Moiseenko <[email protected]>
>> wrote:
>>
>>> I was wondering how the implementation of map-like data structure should
>>> look like in MiniKanren.
>>> I am writing an interpreter of imperative language in MiniKanren and I
>>> need a data structure to represent a mappings between variables and their
>>> values.
>>>
>>> Is there any code that implements that ?
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "minikanren" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
>>> an email to [email protected].
>>> To post to this group, send email to [email protected].
>>> Visit this group at https://groups.google.com/group/minikanren.
>>> For more options, visit https://groups.google.com/d/optout.
>>>
>>
>>
--
You received this message because you are subscribed to the Google Groups
"minikanren" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/minikanren.
For more options, visit https://groups.google.com/d/optout.
