Functional Programming


This is an implementation of an array—using a size-balanced binary search tree under the hood—for a course in programming languages this summer. Some functions may look awkward as they are based on catamorphisms.

Global definitions

fromList, singleton, toList, set, get, size, contains, inverse, and trim

 

Test

Array1

 

As a functor

array functor

 

As a monad

array monad

 

 

Download

 

Download

 

Read More

Background

The concept of state refers to a function/computation global or non-local state of memory at any given time. When the output of a function/computation depends solely on its inputs, we say it is stateless — an example of this is combinatory logic. Conversely, when the output depends not only on the received input but also on history of previous executions, we say it is stateful — this is the case in sequential logic. Notice variables local to some scope are not considered state as they die together with their scope and thus cannot keep history of previous executions. So we only consider global and non-local variables to be state.

Imperative languages describe computations as series of modifications to state. Pure functional languages like Haskell, on the other hand, describe them as function evaluations and have no concept of state.  While being stateless comes with several advantages (I won’t talk about it), certain programs require to keep track of previous executions. The problem then becomes: how to implement state in a language that cannot, by definition, have state? We simulate it. From the point of view of the function caller — living in an outer scope than the function callee — functions being called can do only two things: take input, and return a value. Thereby the state has to come from input parameters, and can only survive a function return if returned by the callee once it has been altered. Then the caller is responsible for sequentially feeding the state to a function, collecting the new state from the callee upon evaluation, and feeding it to the next function in the execution chain. Let me illustrate it through an example.

 

Example

Consider the following example, where we implement a tiny interpreter for a tiny language that supports only variable lookups and variable updates. To represent memory we use a list of pairs of strings, where the first element in the pair is the variable name, and the second one is the value for that variable name:

 

type Memory = [(String, String)]

 

We start by writing a function for looking up elements in memory — Given a variable name, and memory, we get its correspondent value (the second element in the pair whose first element matched the variable name).

 

varLookUpList :: String -> Memory -> Maybe String
varLookUpList name [] = Nothing
varLookUpList name ((n,v):xs) = if name == n 
                                then Just v 
                                else varLookUpList' name xs

 

Next we need to return the modified data structure to the caller so that the caller can pass it to the new callee, and thus preserve the modifications that have been made during the current call. Perhaps this is not the case when we are just “looking up” values, but in general it is. To do this we need an extra input to receive the state, and an extra output to give back the mutated state together with whatever output the function was returning anyway.

In general we want to turn something like this (for functions that lookup values):

 

function ::  a -> state -> b

 

or like this (for functions that alter a data structure):

 

function ::  a -> state -> state

 

into something like this:

 

function :: a -> state -> (b, state)

 

Our example then gets modified as follows — Notice we return back the memory unmodified :

 

varLookUp :: String -> Memory -> (String, Memory)
varLookUp name mem = case varLookUpList' name mem of
		       (Just s) -> (s, mem)
			Nothing -> ("Not found", mem)
    where
        varLookUpList' :: String -> Memory -> Maybe String
	varLookUpList' name [] = Nothing
	varLookUpList' name ((n,v):xs) = if name == n 
                                         then Just v 
                                         else varLookUpList' name xs

 

Updating state is an assignment’s side effect. Other than that, assignments evaluate to the value of the variable on the left hand side of the assignment… at least on our language. So this is our update function updating state and returning it along with the new value that was stored [EDIT NOTE: THIS REQUIRES FURTHER EXPLANATION]:

 

varUpdate :: String -> String-> Memory -> (String, Memory)
varUpdate name nval mem = let newMem = varUpdate' name nval mem in (nval, newMem)
	where
		varUpdate' :: String -> String -> Memory -> Memory
		varUpdate' name nval [] = [(name,nval)]
		varUpdate' name nval ((n,v):xs) = if name == n 
 						  then (n,nval):xs
						  else (n,v):(varUpdate' name nval xs)

 

Then, running our interpreter requires a sequence of function calls where the output of the previous function call is used as input to the next one. Notice initially execution starts with empty memory, and at last we return the memory as evaluated by the last function call. This is achieved — at least in this case — by nested let expressions.

 

emptyMemory = [] 

main =  print $ run emptyMemory

run :: Memory -> Memory
run mem =  let (val0, mem0) = (varUpdate "myVar1" "7.0" mem) in 
		let  (val1, mem1) = (varUpdate "myVar2" "11.0" mem0) in 
			let  (val1, mem2) = (varUpdate "myVar2" "7.0" mem1) in mem2

 

A less simple interpreter would require an actual program to be interpreted, and would quickly become tedious and awkward to deal with, due to the pipelining required to transfer state from function to function. To simplify this, Haskell provides the State Monad, where all the pipelining is hidden from the programmers within a monad. Something important is that the State Monad uses, to some extent, the configuration state -> (value, state) that we just saw in the previous example. Except there is no need to explicitly pass the state as input and the tuple as output, but instead a few functions to read/change both elements of the tuple are provided while passing the passing around is done automatically. Again, let us try an example.

 

Example using the State Monad

The idea behind this tutorial is an attempt to complement existing tutorials that directly introduce the State Monad and its functionality from more complicated examples and without a generic explanation of its use, as well as lack of code that actually runs. Therefore, there is no need to repeat content on the specificities of the monad which are otherwise very well covered in other online tutorials (wikibooks, wikibooks advanced). Instead, this is the state-monadic version of the mini interpreter used above — Before I’d like to highlight a few things though. First, varLookUp and varUpdate now take one less parameter as now we don’t receive/pass the state explicitly. Also, one can think of functions as performing their task in 3 steps: (1) get the state using get; (2) if needed, modify state and putting it back in the tuple being returned using put; and (3) put some value in the tuple being returned using return. Finally, there is no need for nested let expressions:

 

varLookUp :: String -> State Memory String
varLookUp str = do 		 
		mem <- get		
		let varLookUpList' str mem in
		    (Just s) -> return s
		    Nothing -> return "not found" 
		    where
			varLookUpList' :: String -> Memory -> Maybe String
			varLookUpList' name [] = Nothing
			varLookUpList' name ((n,v):xs) = if name == n 
							 then Just v 
							 else varLookUpList' name xs

varUpdate :: String -> String-> State Memory String
varUpdate str val = do
			mem <- get
			put( varUpdate' str val mem)
			return val
	where
		varUpdate' :: String -> String -> Memory -> Memory
		varUpdate' name nval [] = [(name,nval)]
		varUpdate' name nval ((n,v):xs) = if name == n 
						  then (n,nval):xs 
						  else (n,v):(varUpdate' name nval xs)

run :: Memory -> Memory
run initMem =  let (val, mem) = runState( do 
				varUpdate "myVar1" "1.0"; 
				varUpdate "myVar2" "7.0"
				x <- varLookUp "myVar2" 
				varUpdate "myVar1" x
				  ) initMem in mem

main =  print $ run emptyMemory

 

Output:

statemonad_ex_output

 

 

Complete code:

 

Download

 

 

Read More