proglang-11-05-19.md

Stateful Haskell - Programming Languages - Nov 5th, 2019

What does it mean that Haskell has no state?

• You can't print to the screen
• There's no reserved memory for variables

The only thing that a function can do is return a value

Disadvantages of having no state:

• We're not allowed to print to the screen
• We can't do I/O
  • File I/O
  • Network I/O

Stateful Haskell

How can Haskell do stateful operations without breaking the expecations of how functions work?

Let's look at this stateful version of fibonacci in Java:

public static int fibonacciLoop(int nthNumber) {
	int previouspreviousNumber, previousNumber=0,
	currentNumber = 1;
	for (int i = 1; i < nthNumber; i++) {
		previouspreviousNumber = previousNumber;
		previousNumber currentNumber;
		currentNumber = previouspreviousNumber + previousNumber;
	}
	return currentNumber;
}

Let's try to convert it to Haskell.

First we need a way to represent the state:

data FibState = FibState {
	previousNumber :: Integer,
	previouspreviousNumber :: Integer,
	currentNumber :: Integer
}

type FibStateful a = FibState -> (FibState, a)

-- getPreviousNumber :: FibState -> (FibState, Integer)
getPreviousNumber :: FibStateful Integer
-- `previousNumber oldstate` how we access named fields
getPreviousNumber oldstate = (oldstate, previousNumber oldstate)

-- an empty tuple is the Haskell way of saying `void`
-- setPreviousNumber :: Integer -> FibState -> (FibState, ()) 
setPreviousNumber :: Integer -> FibStateful ()
setPreviousNumber newval oldstate =
	(newstate, ())
	where newstate =
		FibState {
			previousNumber = newVal,
			previouspreviousNumber = previouspreviousNumber oldstate,
			currentNumber = currentNumber oldstate
		}

Now we can make our program:

module Fib where

import FibStateful

-- repeatTimes :: Integer -> (FibState -> (FibState, a))
				-> (FibState -> (FibState, a))
-- repeatTimes numberofTimes statefulFunction state
repeatTimes :: Integer -> FibStateful a -> FibStateful a
repeatTimes 0 _ _ = error "Can't do that"
repeatTimes 1 f state = f state
repeatTimes n f state = 
	let (newstate, x) = f state
		in repeatTimes (n-1) f newstate

fib :: Integer -> Integer
fib n =
	let (finalstate, answer) = fibAlgorithm n initialState
	in answer
	where initialState :: FibState
		initialState = FibState = FibState {
			previousNumber = 0,
			previousPreviousNumber = 0,
			currentNumber = 1
		}

fibAlgorithm :: Integer -> FibStateful Integer
fibAlgorithm n oldstate =
	repeatTimes n (\s -> 
		let (state1, pn) = getPreviousNumber s
			(state2, ()) = setPreviousPreviousNumber pn state1
			(state3, cn) = getCurrentNumber state2
			(state4, ()) = setPreviousNumber cn state3
			(state5, pn') = getPreviousNumber state4
			(state6, ppn) = getPreviousPreviousNumber state5
			(state7, ()) = setCurrentNumber (pn' + ppn) state6
		in getCurrentNumber state7
	) oldstate

We can simulate statefulness by making a function that takes in state and returns state

Let's refactor fibAlgorithm by creating a helper function bind that automatically gets, sets and passes state to the next

bind :: FibStateful a -> (a -> FibStateful b) -> FibStateful b
bind f g s = 
	let (newstate, value) = f s
	in g value newstate

fibAlgorithm :: Integer -> FibStateful Integer
fibAlgorithm n =
	repeatTimes n (\s -> 
		getPreviousNumber `bind`
		setPreviousNumber `bind` \_ -> 
		getCurrentNumber `bind`
		setPreviousNumber `bind` \_ ->
		getPreviousNumber `bind` \pn ->
		getPreviousPreviousNumber `bind` \ppn ->
		setCurrentNumber (pn + pnn)
		in getCurrentNumber
	)