Saturday, July 25, 2009

Haskell Variables

The Haskell community seems to have an aversion to anything imperative. IMO this has led to a fair amount of confusion, in particular about variables. A majority of people that learn Haskell are at least somewhat familiar with imperative languages, and almost all other languages rely heavily on mutable variables. When asking about variables the Haskell beginner is usually referred to let/in or where, but those are definition conveniences, not variables.

So one of the things that happens is heavier reliance on recursion, the values passed to the function can change like a variable, but they're still parameters. Which leads to encapsulating values in a state monad, and then passing the monadic values around.

What is a monad? That is where most people get very confused. Mathematically a monad is different than how it is implemented in Haskell! In Haskell a monad is really just a data type pointer. So you have something like IO Integer and it's a pointer to an Integer. Unfortunately the IO monad has no good constructor, you need to use IOArray, IORef, TVar or some other monad to create a variable. For now let's stick to using IORef since it's intended for this.

module Main where

import Data.IORef

main = do
-- a new variable called var
var <- newIORef (1::Integer)

-- the contents of var
a <- readIORef var

-- add one to var
modifyIORef var (+1)

-- the contents of var
b <- readIORef var

-- set var to 3
writeIORef var 3

-- the contents of var
c <- readIORef var

putStrLn $ show a
putStrLn $ show b
putStrLn $ show c

This is how variables are done in Haskell, with the following caveat: in general IORef isn't thread safe. So you might rather use something like:

module Variables (Variable, newVar, setVar, getVar, modVar, showVar) where

import Control.Monad
import Control.Concurrent
import Control.Concurrent.STM

type Variable a = TVar a

-- initialize a new variable
newVar :: a -> IO (Variable a)
newVar value = atomically $ newTVar value

-- get the value of a variable
getVar :: Variable a -> IO a
getVar pntr = atomically $ do
value <- readTVar pntr
return value

-- set the value of a variable
setVar :: Variable a -> a -> IO a
setVar pntr value = atomically $ do
writeTVar pntr value
return value

-- apply a function to a variable
modVar :: Variable a -> (a -> a) -> IO a
modVar pntr fn = atomically $ do
value1 <- readTVar pntr
let value2 = fn value1
writeTVar pntr value2
return value2

-- a show function for a variable (for GHCI)
showVar :: (Show a) => Variable a -> IO ()
showVar pntr = do
value <- atomically $ readTVar pntr
putStrLn $ show value

This is thread safe on top of TVar. Variables.hs
So using this we'd have:

module Main where

import Variables

main = do
-- a new variable called var
var <- newVar (1::Integer)

-- the contents of var
a <- getVar var

-- add one to var
modVar var (+1)

-- the contents of var
b <- getVar var

-- set var to 3
setVar var 3

-- the contents of var
c <- getVar var

putStrLn $ show a
putStrLn $ show b
putStrLn $ show c

Which is almost the same as using IORef, but thread safe.

Tuesday, July 7, 2009

Ternary Trees

I ran across an interesting data structure, the ternary tree. Unlike binary trees, a ternary tree splits three ways at every branch. I went ahead and implemented it in Haskell. It should be able to store dictionary type data, or variable name-value look ups.

The basic idea is that a tree consists of branches, leafs, leafy branches, and stubs. Having a leafy branch allows for words to be prefixes of other words, as in the example.


newTrie a b :: (Ord a) => [a] b -> Trie a b

Create a tree from a single word [a] and associate a value b with it.

insert :: Ord a => [a] -> b -> Trie a b -> Trie a b

Insert a word [a] and a value b into a tree. Insert will return an error if the word already is part of the tree.

lookup :: Ord a => [a] -> Trie a b -> Maybe b

Find the value b associated with a word [a].

map :: (b -> c) -> Trie a b -> Trie a c

Apply a function (b -> c) to all the values b in a tree.

toList :: Ord a => Trie a b -> [([a],b)]

Convert a tree to a list of word-value pairs.

fromList :: Ord a => [([a],b)] -> Trie a b

Convert a list of word-value pairs to a tree.

instance (Binary a, Binary b) => Binary (Trie a b)

An instance of binary for efficient storage of trees. Example: encodeFile "filename" tree