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

From: David Powers <david.powers_at_flinders.edu.au>

Date: Wed, 29 Oct 2014 23:22:12 +0000

On 29 Oct 2014, at 10:54 pm, Michael Hanus <mh_at_informatik.uni-kiel.de<mailto:mh_at_informatik.uni-kiel.de>> wrote:

On 10/29/2014 12:10 AM, David Powers wrote:

...

I would also propose to put up some programs that test the definition of

the language and/or have different behaviour under the different Curry systems.

What do you have in mind? Different Curry systems differ in their

computational power, e.g., KiCS2 supports various search strategies

and is sometimes "lazier" than PAKCS, but the computed results,

if they are computed, should be the same.

...

Best regards,

Michael

There are four things that have come up in my play with Curry (as a Logic Programmer) with various qsort variations - all four occur in a difference list version that implements median of medians for true O(nlogn) qsort without O(n^2) worstcase, but the first can be illustrated in a simpler context. (I don’t have access to a working curry install right now though and these examples were created and run a year or two ago: I was looking to replace Prolog and address limitations of Prolog.)

The differences are as to which/whether results are produced, which clearly is a matter of search strategy.

But I also had in mind syntactic/semantic limitations that seem unnecessarily restrictive, and derestricted implementations.

1. Some things I expected in relation to let/where didn’t work but seem to fit syntactic/semantic definitions.

This example is a three-way quicksort where I was surprised that the first version doesn’t work as it is well defined, as illustrated by splitting the problem pattern into separate wheres - I think this should be handled/extended:

qsort list =

let

part _ [] = ([], [], [])

part p (x:xs) | x <p = (x:ls,es,gs)

| x==p = (ls,x:es,gs)

| x >p = (ls,es,x:gs)

sort [] = []

sort xs_at_(p:_) = sort ls ++ es ++ sort gs

(ls,es,gs) = part p xs

in sort list

qsort list =

let

part _ [] = ([], [], [])

part p (x:xs) | x <p = (x:ls,es,gs)

| x==p = (ls,x:es,gs)

| x >p = (ls,es,x:gs)

where (ls,es,gs) = part p xs

sort [] = []

sort xs_at_(p:_) = sort ls ++ es ++ sort gs

where (ls,es,gs) = part p xs

in sort list

2. The operator precedences don’t have enough granularity - I wanted a precedence of 4.5 for difference lists

3/4. There are issues relating to free variables and unification models that prevent translation from Prolog.

These don’t work correctly under any model I have tried and give different results for different systems/models.

I think the issues with free would not be a problem if unification implemented occur check.

But it’s a while since I looked at this… I tried rev on smap without success…

Even adding in ensureNotFree doesn’t help as all disjunctions can suspend…

I do have a working (sicstus/swipl) Prolog version of this!

infixr 4 # -- this should really be 4.5 above =:= below ++ and :

-- also pattern not allowed at top level without brackets

data DList a = [a] # [a] -- a list and a list suffix (acts as nil if free)

-- rangequicksort with DList - incorporating quicksearch and median of medians

sort cmp list lr hr = (slist (srt (dlist list) lr hr))

where

srt (_#_) lo hi | hi < lo || hi < 1

= y#y

where y free

srt (x#z) lo hi | z =:= x

&> lo <= hi

= y#y

where y free

srt (xs#n) lo hi | ensureNotFree xs =:= (p:qs)

& lo <=: hi

& (ls#es) =:= srt (l#[]) (lo) (hi)

& (es#gs) =:= sbr (e#[]) (lo-lc) (hi-lc)

& (gs#gn) =:= srt (g#[]) (lo-lc-ec) (hi-lc-ec)

= ls#gn

where (l#[],e#[],g#[],lc,ec,gc) = prt p (xs#n)

p, qs, ls, es, gs, gn free

prt _ (x#z) | z =:= x

= (l#l, e#e, g#g, 0, 0, 0)

where l,e,g free

prt p (xs#n) | ensureNotFree xs =:= (x:qs)

= case cmp x p of LT -> (x:l#ln,e#en,g#gn,lc+1,ec,gc)

EQ -> (l#ln,x:e#en,g#gn,lc,ec+1,gc)

GT -> (l#ln,e#en,x:g#gn,lc,ec,gc+1)

where (l#ln,e#en,g#gn,lc,ec,gc) = prt p (qs#n)

x, qs free

= case cmp x p of LT -> (x:l#ln,e#en,g#gn,lc+1,ec,gc)

EQ -> (l#ln,x:e#en,g#gn,lc,ec+1,gc)

GT -> (l#ln,e#en,x:g#gn,lc,ec,gc+1)

where (l#ln,e#en,g#gn,lc,ec,gc) = prt p (qs#n)

x, qs free

sbr (_#_) lo hi | hi < lo

= y#y

where y free

sbr (x#z) lo hi | z =:= x

&> lo <= hi

= y#y

where y free

sbr (xs#n) lo hi | ensureNotFree xs =:= (p:qs)

&> 1 < lo && lo <= hi

= sbr (qs#n) (lo-1) (hi-1)

where p, qs free

sbr (xs#n) lo hi | ensureNotFree xs =:= (q:qs)

& lo <=: 1 & 1 <=: hi

& (es#en) =:= sbr (qs#n) lo (hi-1)

= (q:es#en)

where q, qs, es, en free

dlist [] = (x#x)

where x free

dlist (x:xs) = (x:xd)#xn

where xd#xn = dlist xs

slist ([]#[]) = []

slist (xl#xn) | ensureNotFree xl =:= (x:xs)

= x:slist (xs#xn)

where x, xs free

app (a#b) (c#n) | b =:= c = (a#n)

rev (m#n) | n =:= m

= (m#n)

rev (m#n) | ensureNotFree m =:= (h:t) & (r#h:rn) =:= (rev (t#n))

= (r#rn)

where h, t, r, rn free

qsort xs = qsort [x|x<-xs,x<p] ++ [x|x<-xs,x==p] ++ qsort [x|x<-xs,x>p]

where p = rqsmed xs

rqsort xs = sort compare xs 1 len

where len = length xs

rqsmed xs = sort compare xs mid mid

where len = length xs

mid = ((len+1)//2)

rqsrng xs = sort compare xs

where len = length xs

any comments appreciated

cheers,

David

_______________________________________________

curry mailing list

curry_at_lists.RWTH-Aachen.DE

http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry

Received on Do Okt 30 2014 - 17:59:35 CET

Date: Wed, 29 Oct 2014 23:22:12 +0000

On 29 Oct 2014, at 10:54 pm, Michael Hanus <mh_at_informatik.uni-kiel.de<mailto:mh_at_informatik.uni-kiel.de>> wrote:

On 10/29/2014 12:10 AM, David Powers wrote:

...

I would also propose to put up some programs that test the definition of

the language and/or have different behaviour under the different Curry systems.

What do you have in mind? Different Curry systems differ in their

computational power, e.g., KiCS2 supports various search strategies

and is sometimes "lazier" than PAKCS, but the computed results,

if they are computed, should be the same.

...

Best regards,

Michael

There are four things that have come up in my play with Curry (as a Logic Programmer) with various qsort variations - all four occur in a difference list version that implements median of medians for true O(nlogn) qsort without O(n^2) worstcase, but the first can be illustrated in a simpler context. (I don’t have access to a working curry install right now though and these examples were created and run a year or two ago: I was looking to replace Prolog and address limitations of Prolog.)

The differences are as to which/whether results are produced, which clearly is a matter of search strategy.

But I also had in mind syntactic/semantic limitations that seem unnecessarily restrictive, and derestricted implementations.

1. Some things I expected in relation to let/where didn’t work but seem to fit syntactic/semantic definitions.

This example is a three-way quicksort where I was surprised that the first version doesn’t work as it is well defined, as illustrated by splitting the problem pattern into separate wheres - I think this should be handled/extended:

qsort list =

let

part _ [] = ([], [], [])

part p (x:xs) | x <p = (x:ls,es,gs)

| x==p = (ls,x:es,gs)

| x >p = (ls,es,x:gs)

sort [] = []

sort xs_at_(p:_) = sort ls ++ es ++ sort gs

(ls,es,gs) = part p xs

in sort list

qsort list =

let

part _ [] = ([], [], [])

part p (x:xs) | x <p = (x:ls,es,gs)

| x==p = (ls,x:es,gs)

| x >p = (ls,es,x:gs)

where (ls,es,gs) = part p xs

sort [] = []

sort xs_at_(p:_) = sort ls ++ es ++ sort gs

where (ls,es,gs) = part p xs

in sort list

2. The operator precedences don’t have enough granularity - I wanted a precedence of 4.5 for difference lists

3/4. There are issues relating to free variables and unification models that prevent translation from Prolog.

These don’t work correctly under any model I have tried and give different results for different systems/models.

I think the issues with free would not be a problem if unification implemented occur check.

But it’s a while since I looked at this… I tried rev on smap without success…

Even adding in ensureNotFree doesn’t help as all disjunctions can suspend…

I do have a working (sicstus/swipl) Prolog version of this!

infixr 4 # -- this should really be 4.5 above =:= below ++ and :

-- also pattern not allowed at top level without brackets

data DList a = [a] # [a] -- a list and a list suffix (acts as nil if free)

-- rangequicksort with DList - incorporating quicksearch and median of medians

sort cmp list lr hr = (slist (srt (dlist list) lr hr))

where

srt (_#_) lo hi | hi < lo || hi < 1

= y#y

where y free

srt (x#z) lo hi | z =:= x

&> lo <= hi

= y#y

where y free

srt (xs#n) lo hi | ensureNotFree xs =:= (p:qs)

& lo <=: hi

& (ls#es) =:= srt (l#[]) (lo) (hi)

& (es#gs) =:= sbr (e#[]) (lo-lc) (hi-lc)

& (gs#gn) =:= srt (g#[]) (lo-lc-ec) (hi-lc-ec)

= ls#gn

where (l#[],e#[],g#[],lc,ec,gc) = prt p (xs#n)

p, qs, ls, es, gs, gn free

prt _ (x#z) | z =:= x

= (l#l, e#e, g#g, 0, 0, 0)

where l,e,g free

prt p (xs#n) | ensureNotFree xs =:= (x:qs)

= case cmp x p of LT -> (x:l#ln,e#en,g#gn,lc+1,ec,gc)

EQ -> (l#ln,x:e#en,g#gn,lc,ec+1,gc)

GT -> (l#ln,e#en,x:g#gn,lc,ec,gc+1)

where (l#ln,e#en,g#gn,lc,ec,gc) = prt p (qs#n)

x, qs free

= case cmp x p of LT -> (x:l#ln,e#en,g#gn,lc+1,ec,gc)

EQ -> (l#ln,x:e#en,g#gn,lc,ec+1,gc)

GT -> (l#ln,e#en,x:g#gn,lc,ec,gc+1)

where (l#ln,e#en,g#gn,lc,ec,gc) = prt p (qs#n)

x, qs free

sbr (_#_) lo hi | hi < lo

= y#y

where y free

sbr (x#z) lo hi | z =:= x

&> lo <= hi

= y#y

where y free

sbr (xs#n) lo hi | ensureNotFree xs =:= (p:qs)

&> 1 < lo && lo <= hi

= sbr (qs#n) (lo-1) (hi-1)

where p, qs free

sbr (xs#n) lo hi | ensureNotFree xs =:= (q:qs)

& lo <=: 1 & 1 <=: hi

& (es#en) =:= sbr (qs#n) lo (hi-1)

= (q:es#en)

where q, qs, es, en free

dlist [] = (x#x)

where x free

dlist (x:xs) = (x:xd)#xn

where xd#xn = dlist xs

slist ([]#[]) = []

slist (xl#xn) | ensureNotFree xl =:= (x:xs)

= x:slist (xs#xn)

where x, xs free

app (a#b) (c#n) | b =:= c = (a#n)

rev (m#n) | n =:= m

= (m#n)

rev (m#n) | ensureNotFree m =:= (h:t) & (r#h:rn) =:= (rev (t#n))

= (r#rn)

where h, t, r, rn free

qsort xs = qsort [x|x<-xs,x<p] ++ [x|x<-xs,x==p] ++ qsort [x|x<-xs,x>p]

where p = rqsmed xs

rqsort xs = sort compare xs 1 len

where len = length xs

rqsmed xs = sort compare xs mid mid

where len = length xs

mid = ((len+1)//2)

rqsrng xs = sort compare xs

where len = length xs

any comments appreciated

cheers,

David

_______________________________________________

curry mailing list

curry_at_lists.RWTH-Aachen.DE

http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry

Received on Do Okt 30 2014 - 17:59:35 CET

*
This archive was generated by hypermail 2.3.0
: Do Aug 06 2020 - 07:15:05 CEST
*