Re: beautiful non-determinism

From: Jan Christiansen <jac_at_informatik.uni-kiel.de>
Date: Tue, 28 Jul 2009 10:04:47 +0200

Hi,

On 19.07.2009, at 22:18, Sebastian Fischer wrote:

> For those who consider |foldr1| a way too suspicious function, here
> is another example: computing a sublist non-deterministically is
> *filtering* it with a predicate that yields either True or False [1]:
>
> sublist = filter (\_ -> True?False)
>
> The filter function is probably much more tangible than foldr1 and
> this definition of sublist has a very declarative reading: for each
> element in the list do or do not keep it non-deterministically.

This is very cool. It looks like most of the higher order functions
that take a predicate can be used in a similar way.

   takeWhile (\_ -> False ? True) -- non-deterministic
version of inits

   dropWhile (\_ -> False ? True) -- non-deterministic version
of tails

   fromJust . find (\_ -> False ? True) -- non-deterministic
enumeration of all list elements

   sortBy (\_ _ -> False ? True) -- all permutations

   insertBy (\_ _ -> False ? True) -- inserts an element at a
non-deterministic position

I especially like the implementation of perms by means of sortBy. In
fact this is exactly the definition you provided as we have sortBy le
= foldr (insertBy le) [].

Cheers, Jan
_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on Di Jul 28 2009 - 11:02:15 CEST

This archive was generated by hypermail 2.3.0 : Do Feb 01 2024 - 07:15:09 CET