beautiful non-determinism

From: Sebastian Fischer <sebf_at_informatik.uni-kiel.de>
Date: Sun, 19 Jul 2009 22:18:39 +0200

Hi,

every now and then I have an aha!-moment recognising how beautiful it
can be to combine non-determinism with higher-order list functions.
One of these moments was when I recognised that permuting a list means
folding it with the insert operation - i.e., inserting every element
recursively at an arbitrary position:

   permute = foldr1 insert
     where insert x (xs++ys) = xs++x:ys

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.

I'd like to see more of those, so if you have other examples, please
share!

Cheers,
Sebastian

[1] inspired by: http://www.haskell.org/pipermail/haskell-cafe/2009-July/064337.html


-- 
Underestimating the novelty of the future is a time-honored tradition.
(D.G.)
_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on Mo Jul 20 2009 - 09:50:07 CEST

This archive was generated by hypermail 2.3.0 : Mo Mär 18 2024 - 07:15:10 CET