beautiful non-determinism

From: Sebastian Fischer <>
Date: Sun, 19 Jul 2009 22:18:39 +0200


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


[1] inspired by:

Underestimating the novelty of the future is a time-honored tradition.
curry mailing list
Received on Mo Jul 20 2009 - 09:50:07 CEST

This archive was generated by hypermail 2.3.0 : Do Jan 21 2021 - 07:15:04 CET