Difference between revisions of "Open research problems"

From HaskellWiki
Jump to navigation Jump to search
m (tweaked formatting)
m
(13 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
[[Category:Research]]
  
[[Category:Research]]
   
  +
== 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.
 
   
  ⚫
=== Efficiency of lazy functional languages ===
⚫
The general problem is whether these purely functional languages can implement all algorithms that can be implemented in a language like C as efficiently in an amortized sense ignoring space-usage.
 
  +
:{|
  +
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.<br>
  +
<br>
  ⚫
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?
  +
|}
   
−
===Specific problems===
 +
=== I/O ===
  +
−
As for a specific problem:
 
  +
:See [[Open_research_problems/The_I/O_quandary|the I/O quandary]].
⚫
Implement <code>Data.STRef</code> and <code>Control.Monad.ST.runST</code> without using the built-in <code>ST</code>/<code>IO</code> monad. This needs to happen with operations that all run in O(1) amortized time.
  
  +
  +
== Specific problems ==
  +
  +
=== 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.
  +
|}

Revision as of 04:59, 4 March 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 quandary.

Specific problems

Implement encapsulated-state interface entirely in Haskell (no primitives)

Implement Data.STRef and Control.Monad.ST.runST without using the built-in monadic ST or IO types. This needs to happen with operations that all run in O(1) amortized time.
Retrieved from "https://wiki.haskell.org/index.php?title=Open_research_problems&oldid=64996"