[an error occurred while processing this directive]
An error occured whilst processing this directive
A Monad for Exhaustively Searching Infinite Sets in Finite Time
University of Birmingham
4pm Thursday, 19th of February, 2009
Room 4.31/4.33, Informatics Forum
Abstract
I'll show how monads in functional programming, illustrated by the
language Haskell, can be used to structure exhaustive search over
infinite sets, and indeed get algorithms for free. In previous work, I
investigated what kinds of infinite sets admit exhaustive search in
finite time (and how fast), and how to systematically build such
sets. Here I build them using monads, which makes the algorithms more
transparent, economic and intuitive. In order to attempt to convince
the audience that there might be more to this than just mathematical/
computational fun, I'll show some surprising, but admittedly
contrived, examples that run in a fraction of a second. If time
permits, I'll also show more meaningful examples, pertaining to
automatic verification of programs for real-number computation using
infinite lazy lists of digits.
Although this talk will be primarily addressed to an audience with
functional programming inclinations, it should also appeal an audience
with programming-semantics and/or higher-type computability
inclinations.
An error occured whilst processing this directive