CS-429/529 ========== Lecture on "State in Haskell" Nov 29, 2004 To begin, some general observations ----------------------------------- Data structures in Haskell are IMMUTABLE. Consider: > f (a,b,c,d) = (a,b,c,d+1) The 4-tuple argument to f is rebuilt to create the result. Note, however, that the values a, b, and c are not copied unless they are atomic (say, an Int). In fact they are SHARED. [ draw picture of original argument and the result ] In general they can be arbitrarily large, and of course even "infinite". If we do: > data Foo = Foo { name :: String, address :: String > sex :: Bool, age = Int } > > f x = x { age = age+1 } nothing changes -- these two program fragments are isomorphic. Tuples are "flat", but allow constant-time access to their elements, and are thus similar to arrays. Another flat data type is a list, and the same argument as above applies. For example, to replace the nth element in a list we might write: > replace :: Int -> a -> [a] -> [a] > replace n a [] = [] > replace 0 a (x:xs) = a : xs > replace n a (x:xs) = x : replace (n-1) a xs This takes time proportional to n, and also creates n new "cons cells," although note that the elements after the first n are still shared. [ draw picture of original argument and the result ] Trees ----- Recall from SOE: > data Tree a = Leaf a > | Branch (Tree a) (Tree a) > Accessing a leaf element in a tree of n elements takes log n time -- not as good as constant, but better than linear. Futhermore, UPDATING a leaf element takes log n time, AND only requires creating log n new nodes. [ draw picture ] Arrays ------ Haskell's standard arrays, another "flat" datatype, are also immutable. Recall that: > array :: Ix i => (i, i) -> [(i, e)] -> Array i e and consider: > arr :: Array Int Foo > arr = array (1,n) l where l is a list of n elements, each of type (Int,Foo). We can access elements in arr in constant time via "arr!i", whereas note that "l!!i" takes time proportional to i. Also note this equivalence: > (array (0,n) l) ! i == snd (l !! i) [ Side Note: Array access is actually a CHEAT! It relies on hardware to do the address decoding, which is actually a LOGARTHIMIC process. It only works because the word-size in computers is FIXED (32 bits, 64 bits, etc). ] Haskell arrays are also LAZY. Consider this matrix exhibiting a "wavefront" behavior: > m = array ((1,1),(n,n)) [ [((1,i),1) | i <- [1..n]] ++ > [((i,1),1) | i <- [1..n]] ++ > [((i,j),f i j) | i <- [2..n], j <- [2..n]] ] > where f i j = m!(i-1,j) + m!(i-1,j-1) + m!(i,j-1) For example, for n=5 we get: 1 1 1 1 1 1 3 5 7 9 1 5 13 25 41 1 7 25 63 129 1 9 41 129 321 Many numerical analysis problems, including things such as Gaussian Elimination, can be expressed directly as a recursive array in this manner. Array Update ------------ UPDATING a Haskell array is more problematic, because they are immutable -- to change one element requires creating an entirely new array, just as with a tuple. Haskell makes this at least a little easier by providing operations such as: > (//) :: Ix i => Array i e -> [(i, e)] -> Array i e For example, to change the i'th element of "arr" to "u" I would do: > arr // [(i,u)] but this requires copying the entire array -- the elements are shared, but the array structure is rebuilt. [ draw picture ] If we change multiple elements at once, as in: > arr // [(i,u), (j,v), (k,w)] note that still only ONE copy is required, since the "intermediate" arrays are inaccessible to the user. Monadic Arrays -------------- Although the inability to mutate arrays seems problematic, it does have its advantages -- consider, for example, a transaction management system where changes may have to be "undone" if a transaction fails. With Haskell arrays there is nothing to undo, since the old array still exists! Neverthless, it is sometimes desirable to have an array that exhibits constant-time access AND constant-time update, just like a conventional imperative array. To do this in a purely functional way requires "hiding" the array itself, so that "old" versions cannot be accessed -- this is called "single threaded". For example, in: > ((arr // [(i,u)]) // [(j,v)]) // [(k,w)] [ draw picture ] "arr" is clearly "single threaded", but in general this property cannot be inferred -- it needs to be enforced by the language. Imperative languages achieve this with side effects. Haskell achieves this with monads! In fact Haskell provides a very general interface to such arrays using type classes: > class (HasBounds a, Monad m) => MArray a e m > > newArray :: (MArray a e m, Ix i) => (i,i) -> e -> m (a i e) > readArray :: (MArray a e m, Ix i) => a i e -> i -> m e > writeArray :: (MArray a e m, Ix i) => a i e -> i -> e -> m () > ... For example, IOArray is an instance of MArray: > instance MArray IOArray e IO so that the above operations have refined types: > newArray :: Ix i => (i,i) -> e -> IO (IOArray i e) > readArray :: Ix i => IOArray i e -> i -> IO e > writeArray :: Ix i => IOArray i e -> i -> e -> IO () For example: > do arr <- newArray (1,n) 42 > x <- readArray arr i > writeArray arr i (x+1) > y <- readArray arr i > return (x+y) Here x will be 42 and y will be 43, so the result is 85. UnsafePerformIO --------------- Having all imperative things "run in the IO monad" is sometimes a bit annoying. For example, suppose there is some computation that requires computing with an array, but then generates some (pure) result -- why should it have to be in the IO monad? One way to solve this problem is to "cheat" by using: > unsafePerformIO :: IO a -> a However, this is "unsafe" -- there is no guarantee that in fact the IO command will ONLY do array computation, and thus referential transparency is lost. To see this, consider: > (unsafePerformIO getChar, unsafePerformIO getChar) and suppose the user types "a" and then "b". The result could then either be the pair ('a','b') or ('b','a'), depending on which component of the tuple is evaluated first. Furthermore, by equational reasoning, the above should be equivalent to: > let c = unsafePerformIO getChar > in (c, c) in which case the result will be ('a','a'). In fact, in the GHC compiler, you have to TURN OFF optimizations in order to prevent the compiler from doing this as an optimization (i.e. common subexpression elimination). For these reasons unsafePerformIO is NOT in standard Haskell. The ST Monad ------------ A better solution to our problem is to use the ST monad: > data ST s a > runST :: (forall s . ST s a) -> a Note something new here: the "forall" is a NESTED universal quantification of a type variable (recall that all type variables are implicitly universally quantified, but at the OUTERMOST level). This nesting prevents the result type "a" from having any mention of the state "s"! For example, STArray uses the ST monad: > instance MArray (STArray s) e (ST s) (Note the use of the "phantom type variable" s, whose only purpose is to "unify" STArray and ST.) Using this instance, the array operations have refined types: > newArray :: (Ix i) => (i,i) -> e -> ST s (STArray s i e) > readArray :: (Ix i) => STArray s i e -> i -> ST s e > writeArray :: (Ix i) => STArray s i e -> i -> e -> ST s () Now the previous example can be rewritten as: > runST $ do arr <- newArray (1,n) 42 > x <- readArray arr i > writeArray arr i (x+1) > y <- readArray arr i > return (x+y) to yield the PURE result 85, rather than an IO computation that yields the value 85 when executed. Perhaps it goes without saying, but note that this example can be rewritten as: > let doRead = readArray arr i > in runST $ do arr <- newArray (1,n) 42 > x <- doRead > writeArray arr i (x+1) > y <- doRead > return (x+y) but this does not change the result, because "readArray arr i" is a monadic action (i.e. a command). To further convince you that this is "safe", suppose we do the following: > a = runST $ do arr <- newArray (1,n) 42 > return arr If this were allowed, "a" could be used in some OTHER ST Monad contexts, and then all sorts of problems would arise. For example, suppose that it is modified one way in one context, and a different way in another -- then we are back to the same set of problems that we had with unsafePerformIO! To see why this is actually NOT a problem, let me ask a question: What is the type of "a"? (This is a trick question!) The answer is that it has NO type, because in fact this program fragment is ill-typed! To see why, recall newArray's refined type: > newArray :: (Ix i) => (i,i) -> e -> ST s (STArray s i e) So "arr" in the above program fragment must have type STArray s i e. In particular, note that it has an "s" in it. But this means that it cannot be returned as the result of an application of runST, because "s" is only quantified over runST's argument -- it cannot escape! For more info ------------- See the GHC documentation of its "Hierarchical Libraries" for much more about these ideas, including, for example, "unboxed" arrays, which are arrays into which the elements are completely stored, rather than having pointers to the elements. [ draw picture ]