[Haskell-cafe] Find a point inside (x,y,z) -> Bool

Olaf Klinke olf at aatal-apotheke.de
Fri Oct 30 19:02:57 UTC 2015


this may be impractical performance-wise, but Haskell offers magic 
data structures for searching. Have a look at Martin Escardo's blog post 
[1] on infinite search in finite time. There is a package on Hackage [2] 
implementing it. The `shapes` you get are compact, non-empty subsets of 
types. If you have a shape

shape :: Data.Searchable.Set a


Data.Searchable.search (const True) shape

will return some element of your shape. As far as I know nobody has ever 
used this data structure for solid geometry. You'd need to combine it with 
some implementation of exact reals [*] to have geometry in a product of 
closed intervals. A downside is that general intersections don't exist, 
since the shapes must be non-empty. But since images of searchable sets 
are searchable, you could define complicated shapes by starting with a 
simple one and distort it with a function. 
If your type of space is discrete, then the search function might resort 
to brute force enumeration if the shape was defined that way.

-- Olaf

As far as I am aware there is no appropriate package on Hackage, but 
Haskell implementations exist in several theses.

More information about the Haskell-Cafe mailing list