Personal tools

Open research problems

From HaskellWiki

Revision as of 18:11, 20 May 2007 by Fasta (Talk | contribs)

Jump to: navigation, search

1 Efficiency of lazy functional languages

This is a problem that came up during IRC discussions. We consider a purely functional language L. By purely functional we mean a language that has value semantics. That is, there is no function such that after evaluation of the function the value that was referred to by something else changed. (Also known as "No Side Effects"). A value is "changed" when it is not the case during an evaluation that when the old value and the new value would both be fully evaluated, there wouldn't be the same result. This should make sure that laziness is allowed in the purely functional language.

The general problem is whether these purely functional languages can implement all algorithms that can be implemented in a language like C as efficient in an amortized sense ignoring space-usage.

1.1 Specific problems

As for a specific problem [1]: Implement Data.STRef without using the built-in ST/IO monad. It's clear that one can use references in C. How does one do the same in L?