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

[Olaf Klinke]

Martin,

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

then

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

[1]
http://math.andrej.com/2008/11/21/a-haskell-monad-for-infinite-search-in-finite-time/
[2]
http://hackage.haskell.org/package/infinite-search
[*]
As far as I am aware there is no appropriate package on Hackage, but 
Haskell implementations exist in several theses.