Lazy Functional State Threads

Vaibhav Sagar

What

Strict stateful computation in Haskell

Why

Source: Three Word Phrase
Source: Three Word Phrase

But seriously

  • Union find
  • Hashtables
  • Performance

Overview

State Transformers

                                        Result
               +---------------------+    ^
               |                     |    |
               |                     +----+
               |                     |
               |                     |
      +------->+                     +-------->
 State in      +---------------------+  State out

Multiple inputs/outputs

Inputs                                   Results
 +   +       +---------------------+     ^   ^
 |   |       |                     |     |   |
 |   +------>+                     +-----+   |
 +---------->+                     +---------+
             |                     |
 +-----------+                     +--------->
   State in  +---------------------+  State out

returnST

thenST

A pattern emerges

thenST_

seqST

References

API

Example

Encapsulation

An incorrect implementation

A broken program

A correct implementation

Array references

API

Example

Input/output

API

Example

ccall

  • A builtin that allows the programmer to interface with C

ccall

mainIO

  • Plays the same role as main() in C

Implementation

Update in place

  • State is single-threaded
  • State is strict
  • In-place updates are fine

Efficiency

Transformation

Transformation

Transformation

Passing the state around

freezeArray

  • Can be optimised if we know no further mutations are performed

IO

Equality

Interleaved and parallel operations

Conclusion

Have we turned Haskell into C?

Eating your cake and having it too

Questions?