Dear Sebastian,
thanks for this new view on set functions.
I was aware of the fact that set functions do not strongly
encapsulate all non-deterministic computations.
One motivation for set functions is to restrict the features
for encapsulating non-deterministic computations in order to
obtain a form of encapsulation which is independent of the
evaluation strategy, e.g., one can reason about the expected
results of a computation by a call-by-value strategy but use
call-by-need as a more efficient implementation.
Although one can implement set functions in MCC via findall
(which is a good point!), I think one should use the limited
form of set functions (which is more comprehensible) rather than
the general findall with its known drawbacks.
Best regards,
Michael
On 03/06/2012 02:06 AM, Sebastian Fischer wrote:
> Dear FLP folks,
>
> while preparing a talk about encapsulated search, it occurred to me
> that set functions are a special case of weak encapsulation, not
> exposing the encapsulation primitive.
>
> Assuming a weak encapsulation function
>
> values :: a -> {a} -- set of values of type a
>
> we can implement set functions as follows. For
>
> f x = x + (0?1)
>
> we can implement
>
> f_set x = values (f x)
>
> which will satisfy
>
> f_set (10?20) = {10,11} ? {20,21}
>
> I have not thought about set functions like this before. Have you?
>
> This suggests that set functions can be added to MCC easily:
>
> f_set x = findall (\y -> y =:= f x)
>
> already behaves like 'set_f' above in MCC because, there, findall
> implements weak encapsulation. All that remains is using an abstract
> datatype to hide the order of list element, like the Values type used
> in PAKCS:
>
> http://www.informatik.uni-kiel.de/~pakcs/lib/CDOC/SetFunctions.html#Values
>
> Unlike PAKCS's implementation, the MCC implementation would not be
> restricted by evaluating arguments call-by(-deep)-value, so
>
> const_set (0?1) failed = {0} ? {1}
>
> would work in MCC while it, currently, does not work in PAKCS.
>
> Best,
> Sebastian
>
> P.S. During my talk, Ken Shan suggested an implementation of permsort
> that I find particularly appealing. It uses set functions and function
> patterns so it works only in PAKCS. It can be rewritten to use weak
> encapsulation and equality constraints, sacrificing some efficiency
> due to destroying the laziness of function patterns.
>
> import SetFunctions
>
> sort :: [Int] -> [Int]
> sort l | isEmpty (set1 descending p) = p
> where p = perm l
>
> descending :: [Int] -> ()
> descending (_++x:y:_) | x > y = ()
>
> perm :: [a] -> [a]
> perm [] = []
> perm (x:xs) = insert x (perm xs)
>
> insert :: a -> [a] -> [a]
> insert x xs = (x:xs) ?
> case xs of
> y : ys -> y : insert x ys
> _______________________________________________
> curry mailing list
> curry_at_lists.RWTH-Aachen.DE
> http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on Di Mär 06 2012 - 10:42:56 CET