Open research problems

From HaskellWiki
Revision as of 15:51, 11 May 2007 by Fasta (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

This is a problem that came up during IRC discussions. We consider a purely function language. By purely functional we mean a language that has value semantics. I.e. there is no function s.t. after evaluation of the function the value that was referred to by something else changed. 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.

Given a list of numbers, implement a data type s.t. every number is stored in a structure, all structures together holds the numbers exactly once. One operation that needs to be supported is to move one element to another structure (possibly creating a new structure). A second operation is that given a number one should be able to return the structure holding that number. All operations should run in amortized O(1) time.