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
Received on Di Mär 06 2012 - 10:39:18 CET