- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

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

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
: Thu Nov 14 2019 - 07:15:08 CET
*