Hi Sebastian,
I agree with your observation. The speedup of "test-of-generate"
compared to "generate-and-test" is impressive but far away from
insertion sort. You'll find a comparison between both versions
in terms of the size of the search space also in the old tech report
http://www.informatik.uni-kiel.de/~mh/reports/LIFO-98-08.html
There you can see that the complexity of "test-of-generate"
is 3^n, which is much better than n! but still bad.
I don't think that the Babel implementation provided a better
strategy.
Best regards,
Michael
On 10/16/2013 12:36 PM, Sebastian Fischer wrote:
> Hi Julio,
>
> that's interesting. The Babel implementation must have been different
> from the Curry implementations I was aware of until today.
>
> Can you provide a reference to the implementation you have in mind?
> After a quick search, I just found [2] which investigates the run time
> of permutation sort on page eleven. Even the best (lazily pruning)
> version there (apparently) still has exponential complexity.
>
> Thanks,
> Sebastian
>
> [2] Efficient Translation of Lazy Functional Logic Programs into Prolog
> Michael Hanus
> www.informatik.uni-kiel.de/~mh/papers/LOPSTR95.ps
>
> On Wed, Oct 16, 2013 at 6:32 PM, Julio Mariņo <jmarino_at_fi.upm.es> wrote:
>> Permutation sort was one of the standard benchmarks of the Babel FL language
>> in the early nineties. The fact that its lazy implementation was equivalent
>> to insertion sort was well known, and we actually used the performance
>> figures to impress the Prolog people ;)
>>
>> Julio
>>
>>
>> On Wed, Oct 16, 2013 at 9:05 AM, Sebastian Fischer
>> <sebf_at_informatik.uni-kiel.de> wrote:
>>>
>>> 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
>>>
>>
>>
>>
>> --
>> Julio Mariņo
>> Babel research group
>> Universidad Politecnica de Madrid
>
> _______________________________________________
> curry mailing list
> curry_at_lists.RWTH-Aachen.DE
> http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
>
_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on Mi Okt 16 2013 - 13:10:03 CEST