set functions and weak encapsulation

From: Sebastian Fischer <sebf_at_informatik.uni-kiel.de>
Date: Tue, 06 Mar 2012 10:06:53 +0900

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 Tue Mar 06 2012 - 10:39:18 CET

This archive was generated by hypermail 2.3.0 : Fri Sep 20 2019 - 07:15:08 CEST