[Haskell-cafe] Converting Types to Terms

Klaus Ostermann ostermann at informatik.tu-darmstadt.de
Sun Jan 28 15:11:33 EST 2007

I would like to have a program that can synthesize programs for a
given type, composing only functions from a given library.

For example, suppose my library has

isZero :: Int -> Bool
map :: (a -> b) -> [a] -> [b]
and :: Bool -> Bool -> Bool
fold :: (a -> b -> a) -> a -> [b] -> a
True :: Bool
(.) :: (b -> c) -> (a -> b) -> a -> c

then I want to ask, say, for a program of type

  [Int] -> Bool

and get as answer

(fold and True) . (map isZero)

I have found two approaches in this direction. The first one
is the De-Typechecker

and the other one is Djinn

However, with none of these approaches I managed to do anything with list 

What else is available (besides Djinn and De-Typechecker)? Are lists a problem? 
In general, what are the practical and theoretical limits of these program 
synthesizers? Are there any overview papers for this topic?


More information about the Haskell-Cafe mailing list