Archive for the ‘haskell’ Category

Using Monads for State

March 30, 2010

One of the things that monads have been very useful for is State. Most of the time there is some intermediate structure that is not necessarily part of the result however it is needed in the intermediate calculation in order to come out with the final output. I was very lucky in finding Wadler’s Paper that explains monads by examples, which inspired me to create my own. Conveniently enough, I remembered a function that I wrote a while back for Project Euler where every number that is not the sum of two abundants is added up. The function takes as input a number to check as well as a list of all its known abundant numbers so far.


accumIfNotSumOfTwoAbundants (result,abundants) num
| isAbundant num == True  && isSumOfTwoAbundants abundants num == True  = 
  (result,num:abundants)
| isAbundant num == False && isSumOfTwoAbundants abundants num == True  = 
  (result,abundants)
| isAbundant num == True  && isSumOfTwoAbundants abundants num == False = 
  (num+result,num:abundants)
| isAbundant num == False && isSumOfTwoAbundants abundants num == False = 
  (num+result,abundants)


The function has a "side effect", in that it checks if the passed number is abundant before checking if the number is the sum of two previously known abundants. If the number itself is abundant, the number needs to be added to the currently passed list of abundants for the next round of calculation. Along with that, the result must be passed, which is the accumulated result so far plus the number passed if the number is sum of two abundants, otherwise only the accumulated result. So, how do we go about finding the result? In order to gain an appreciation of monads, let's not use folds but instead write the recursive calls manually, which will look something like


main = let (a,x) = accumIfNotSumOfTwoAbundants (0,[]) 12
           (b,y) = accumIfNotSumOfTwoAbundants (a,x)  13
           (c,z) = accumIfNotSumOfTwoAbundants (b,y)  14
        in putStrLn (show (c,z))


where c is the result and z is the intermediate list. Now the question is "can we abstract the list in a type since it is essentially global state", and the answer is yes we can! The inputs to the original function need to be slightly modified so that the list "state" is the last parameter being passed rather than being passed as a tuple along with the result. Let's define a new type now


type StateTrans s a = s -> (a,s)


As guessed, s is a generic state and a is the result. Now is the time to define the two famous functions, composition and return.


(>>>=) :: StateTrans s a -> (a -> StateTrans s b) -> StateTrans s b
p >>>= k = \s0 -> let (a,s1) = p s0
                      (b,s2) = k a s1
                   in (b,s2)

unit :: a -> StateTrans s a
unit a = \s -> (a,s)


Notice that I have defined composition as >>>= rather than >>= and return as unit to avoid compiler confusion. Now comes the main driver that pipes everything together.


main = let eval   = accumIfNotSumOfTwoAbundants 0 12 >>>=
             \a  -> accumIfNotSumOfTwoAbundants a 13 >>>=
             \b  -> accumIfNotSumOfTwoAbundants b 14 >>>=
             \c  -> unit c
        in putStrLn . show $ eval []


As noticed, the intermediate list does not need to be passed around every single time, only the result. The initial empty list is passed only once to the function eval. However, the function eval does not take any parameters, so how can we pass an extra parameter? Due to the magic of partial application it turns out that when we call accumIfNotSumOfTwoAbundants 0 12, it is actually a function with type [Integer] -> (Integer, [Integer]). Wow, that looks exactly like our type that we defined earlier! Well, it is just so convenient that it is the first parameter of input of >>>= function as well. That means that p in this case is really the expression accumIfNotSumOfTwoAbundants 0 12. With the combined power of lazy evaluation and partial application s0 does not need to be extracted right away and is instead a thunk that will be evaluated later. So then k a is really the anonymous function \a -> accumIfNotSumOfTwoAbundants a 13. Notice that here a is the result of the first function which is the first parameter to the anonymous function as well. Here, s1 is the intermediate state that came as a result of calculating the first expression, which is then passed to k a, which in turn becomes (\a -> accumIfNotSumOfTwoAbundants a 13) s1. As can be observed, multiple functions may be strung together in such a fashion, in a very similar fashion to unix pipes. It is time to talk about the function unit. It is not necessary in the following example and writing main without unit call would yield same result as with it. However it is good practice to have it since you know exactly the value that you are returning. Interesting to note is that unit may return an intermediate value as well such as


main = let eval   = accumIfNotSumOfTwoAbundants 0 12 >>>=
             \a  -> accumIfNotSumOfTwoAbundants a 13 >>>=
             \b  -> accumIfNotSumOfTwoAbundants b 14 >>>=
             \c  -> unit a
        in putStrLn . show $ eval []


The main thing to realize is that unit takes as a parameter the intermediate, and raises it to the monad which in this case is (result,state). From here on out an actual instance of a monad may be used so that main may be rewritten in a do style notation.

In order to create an instance of Monad, we will have to create a newtype and cannot use type synonym anymore.


newtype StateTrans s a = ST( s -> (a,s) )


The new monad instance will look such as


instance Monad (StateTrans s)
  where
    (ST p) >>= k = ST( \s0 -> let (a,s1) = p s0
                                  (ST q) = k a
                              in q s1 )
                                  
    return a = ST( \s -> (a,s) ) 


The ST function essentially acts as a lifting function which transforms into StateTrans type. Another function is necessary, applyST, which drops the result into something usable by other functions.


applyST :: StateTrans s a -> s -> (a,s)
applyST (ST p) s = p s            


Now, we are able to write the main portion of our code in a style that is similar to C syntax.


main = let eval = do 
       {
                a <- ST (accumIfNotSumOfTwoAbundants 0 12);
                b <- ST (accumIfNotSumOfTwoAbundants a 13);
                c <- ST (accumIfNotSumOfTwoAbundants b 14);
                return c
       }        
       in putStrLn . show $ applyST eval []


Reference: Haskell and Monads

A tic-tac-toe implementation using haskell

March 30, 2008

After about half a year, I can finally say that I am comfortable using haskell as a language. Dealing with the functional part, the biggest stumbling block for me were the Data types, just because you cannot declare Data types in other languages as you do in haskell. In languages like Java or Python you can’t really really declare your own Data types. You can create classes, but that is different since they may not be just containers, they may change the outside world somehow. In haskell, a Data type is just that, a container, kind of like a slot for some value. That value may be restricted to a certain subset, or it may be a special kind of slot (for instance, a tree), but it cannot be executed to change some state outside of itself. The other thing that I haven’t seen before anywhere else is the use of higher-order functions, and mainly being able to pass a function as a parameter to another function. I have never seen this property in math either, but I’m sure it exists, I just haven’t taken such advanced courses yet. That leads me to my topic, which is an AI agent for a tic-tac-toe implementation that I made using haskell. It is available at hackage if anyone wants to try it out. I used two references when I was coding the project, Principles of Artificial Intelligence by Nils Nilsson, and the paper Why Functional Programming Matters by John Hughes. Both of these were excellent references, especially the paper. The program makes extensive use of higher-order functions and function composition. It uses minimax and alpha-beta pruning for its algorithm. Using these functions, I could test out certain functionalities one by one. What I used to do before in imperative languages was print statements, which would get very messy. Here I can just test the input of a function, and as long as it returns the desired output for all my tests, I don’t have to worry about that function at all. That lets me concentrate on one problem, without thinking about other functions introducing some errors. I also used maps and zips in a nice way. I first made a function that given a board, returns a list of all the possibilities of that board, calling it moves. After that, I made a recursive function reptree that in this case takes moves (a function!) as parameter, and a Tree with only one root, mainly the board that we wanted to pass into moves. The reptree function constructs another tree with the board as root, and since the children of the root is a list, it maps reptree moves over the list generated by moves called with the root board as parameter. Therefore, it becomes a recursive function that given a certain board as parameter, can generate a tree of all the possible possibilities ever to occur! OK, that however generates only the board moves, what I really want the actual values of the moves. Therefore I have a function getValue, that for a certain board, outputs a number and that’s all it does. How it actually generates this number is explained in the comments of the source code. All I do then is map the function getValue over the tree that I generated and I get as output a tree of the values. I can then just simply feed that output to maximise which would return to me the most advantageous value. One thing that the paper doesn’t mention and something I didn’t find anywhere is how to get the actual board, since you get a value from maximise but you can’t really do anything with it, all it tells you is the value of the best move, but the actual move is lost. Therefore, I just made a tree zipper that zips the two trees together and returns a tree of tuples consisting of the value and the actual board. We then feed the tuple to maximise, with it only looking at the first value, but actually returning a tuple of the value and the best move. That gives you a best move that the agent should make some time in the future however, considering both the player and the enemy play optimally. We need the best move right for the next move that we need to make, not the move a couple of plies down the line. It’s good thing that I provide a list of history that tells us what moves the board has already generated, so I just backtrack to one move after the current move and I have my best move for the next ply. My code is still not as pretty as I would like it to be, due to a couple of hacks I had to make, but it is a lot better than what I would have had to go through if I wrote this in an imperative language.

gentoo-haskell ebuild

December 25, 2007

I just got done with another semester of college. It was tougher than usual since I had 6 classes. With the little time that I have had, I’ve been intently trying to learn Haskell, which is nothing like I have seen before, since it is purely functional, unlike all the other imperative languages I’m used to. It seems promising, but will probably take a while to fully grasp it. In trying to learn the languages, I’ve thought about making libmpd-haskell work with xmonad to play and stop music with a button. Midway through, someone changed something some feature in xmonad, and it stopped working anymore. Rather than try to fix this in a language I don’t know, I made a nice ebuild for gentoo instead.