Difference between revisions of "Open research problems"
Jump to navigation
Jump to search
m |
|||
(20 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
[[Category:Research]] |
[[Category:Research]] |
||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
+ | :{| |
||
⚫ | |||
+ | This is a problem that came up during IRC discussions. We consider a purely functional language ''L'': |
||
− | As for a specific problem [1] : |
||
+ | * 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"). |
||
− | Given a list of numbers, implement a data type s.t. every number is stored in a structure, all structures together hold the numbers exactly once. One operation that needs to be supported is to move one element(it doesn't matter which one) to another structure (possibly creating a new structure). |
||
⚫ | |||
+ | <br> |
||
⚫ | |||
+ | |} |
||
+ | === I/O === |
||
− | A structure is anything that can be given a name. Moving in this context means that one structure before the operation contains the element and after it, doesn't and that another structure does contain the element being moved. In Haskell a structure would be isomorphic to a data type. |
||
+ | :See [[The I/O problem|the I/O problem]]. |
||
− | 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. |
||
+ | == Specific problems == |
||
− | [1] It might be the case that this is a trivial problem and that I forgot some further conditions, if that's the case I will correct it later when a solution is posted. |
||
+ | |||
+ | === Implement encapsulated-state interface entirely in Haskell (no primitives) === |
||
+ | :{| |
||
+ | Implement <code>Data.STRef</code> and <code>Control.Monad.ST.runST</code> without using the built-in monadic <code>ST</code> or <code>IO</code> types. This needs to happen with operations that all run in ''O''(1) amortized time. |
||
+ | |} |
Latest revision as of 12:50, 31 May 2022
General problems
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.
Can purely functional languages like L can implement all algorithms that can be implemented in a language like C as efficiently in an amortized sense, ignoring space-usage?
I/O
- See the I/O problem.
Specific problems
Implement encapsulated-state interface entirely in Haskell (no primitives)
-
Implement
Data.STRef
andControl.Monad.ST.runST
without using the built-in monadicST
orIO
types. This needs to happen with operations that all run in O(1) amortized time.