- 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: Wed, 16 Oct 2013 16:05:24 +0900

Hello!

A folklore example of our community is "permutation sort", where a

list of numbers is sorted by "first" permuting all its elements

nondeterministically and "then" checking whether the result is sorted.

An important aspect of this example is pruning thanks to laziness.

Although the program looks like permuting first and then checking for

sortedness, large parts of the search space are pruned by lazy

evaluation, interleaving the generator and the test.

That said, the pruned parts are not large enough to make the resulting

program efficient. Experimental results suggest that it is still

exponential in the worst case.

It just occurred to me that permutation sort can be expressed in a way

that allows significantly more pruning. The essential idea is the

following observation:

isSorted (insert x xs) ==> isSorted xs

or equivalently

not (isSorted xs) ==> not (isSorted (insert x xs))

where `isSorted` checks whether a given list is sorted and `insert`

inserts the first argument into the second at an arbitrary position

nondeterministically.

Thanks to this observation, we can discard subsequent insertions if we

detect that intermediate results are already out of order.

One way to implement a `permute` operation is to use the `foldl`

function like this:

permute :: [a] -> [a]

permute = foldl (flip insert) []

In order to collect intermediate results, we can use `scanl` from the

`List` module instead of `foldl`

insertions :: [a] -> [[a]]

insertions = scanl (flip insert) []

For example, `insertions [1,2]` has two possible results,

`[[],[1],[1,2]]` or `[[],[1],[2,1]]`. The last element of `insertions

l` is always a permutation of `l`.

In analogy to permutation sort defined as

psort :: [Int] -> [Int]

psort xs | isSorted p = p

where

p = permute xs

we can define a function isort that uses `insertions` rather than `permute`.

isort :: [Int] -> [Int]

isort xs | all isSorted ps = last ps

where

ps = insertions xs

Thanks to the above observation (and laziness of `all`), this

definition detects early if the final permutation is unsorted based on

unsortedness of an intermediate insertion.

It seems that unsorted insertions are discarded immediately, just as

if the `isSorted` check would have been incorporated into the

definition of `insert`. Experiments suggest that indeed, the resulting

code has quadratic worst case complexity, just like insertion sort.

The complete code is attached to this email.

Best regards,

Sebastian

P.S. My observation is inspired by a paper [1] shown to me by Keisuke

Nakano after I gave a Curry tutorial at NII Tokyo. Although

`insertions` does not seem to compute an "improving sequence" in the

sense of that paper, the technique seems certainly related.

[1] Pruning with improving sequences in lazy functional programs

Hideya Iwasaki,Takeshi Morimoto,Yasunao Takano

http://link.springer.com/article/10.1007%2Fs10990-012-9086-3

_______________________________________________

curry mailing list

curry_at_lists.RWTH-Aachen.DE

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

Received on Wed Oct 16 2013 - 10:17:28 CEST

Date: Wed, 16 Oct 2013 16:05:24 +0900

Hello!

A folklore example of our community is "permutation sort", where a

list of numbers is sorted by "first" permuting all its elements

nondeterministically and "then" checking whether the result is sorted.

An important aspect of this example is pruning thanks to laziness.

Although the program looks like permuting first and then checking for

sortedness, large parts of the search space are pruned by lazy

evaluation, interleaving the generator and the test.

That said, the pruned parts are not large enough to make the resulting

program efficient. Experimental results suggest that it is still

exponential in the worst case.

It just occurred to me that permutation sort can be expressed in a way

that allows significantly more pruning. The essential idea is the

following observation:

isSorted (insert x xs) ==> isSorted xs

or equivalently

not (isSorted xs) ==> not (isSorted (insert x xs))

where `isSorted` checks whether a given list is sorted and `insert`

inserts the first argument into the second at an arbitrary position

nondeterministically.

Thanks to this observation, we can discard subsequent insertions if we

detect that intermediate results are already out of order.

One way to implement a `permute` operation is to use the `foldl`

function like this:

permute :: [a] -> [a]

permute = foldl (flip insert) []

In order to collect intermediate results, we can use `scanl` from the

`List` module instead of `foldl`

insertions :: [a] -> [[a]]

insertions = scanl (flip insert) []

For example, `insertions [1,2]` has two possible results,

`[[],[1],[1,2]]` or `[[],[1],[2,1]]`. The last element of `insertions

l` is always a permutation of `l`.

In analogy to permutation sort defined as

psort :: [Int] -> [Int]

psort xs | isSorted p = p

where

p = permute xs

we can define a function isort that uses `insertions` rather than `permute`.

isort :: [Int] -> [Int]

isort xs | all isSorted ps = last ps

where

ps = insertions xs

Thanks to the above observation (and laziness of `all`), this

definition detects early if the final permutation is unsorted based on

unsortedness of an intermediate insertion.

It seems that unsorted insertions are discarded immediately, just as

if the `isSorted` check would have been incorporated into the

definition of `insert`. Experiments suggest that indeed, the resulting

code has quadratic worst case complexity, just like insertion sort.

The complete code is attached to this email.

Best regards,

Sebastian

P.S. My observation is inspired by a paper [1] shown to me by Keisuke

Nakano after I gave a Curry tutorial at NII Tokyo. Although

`insertions` does not seem to compute an "improving sequence" in the

sense of that paper, the technique seems certainly related.

[1] Pruning with improving sequences in lazy functional programs

Hideya Iwasaki,Takeshi Morimoto,Yasunao Takano

http://link.springer.com/article/10.1007%2Fs10990-012-9086-3

_______________________________________________

curry mailing list

curry_at_lists.RWTH-Aachen.DE

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

- application/octet-stream attachment: permsort.curry

*
This archive was generated by hypermail 2.3.0
: Mon Nov 18 2019 - 07:15:08 CET
*