turing.hs

$ cat turing.hs 

-- this is a finite memory tape with dereference and assign

import Control.Monad.State
import qualified Data.Map as Map
import Data.Word

type Ptr = Word64
-- a C-like array (char *) which maps int64 to int8
-- the implementation is as a sparse binary tree. values are zero by default.
type Machine a = State (Map.Map Ptr Word8) a

deref :: Ptr -> Machine Word8
deref ptr = do
  memory <- get
  return $ Map.findWithDefault 0 ptr memory

zero :: Ptr -> Maybe Ptr
zero 0 = Nothing
zero n = Just n

assign :: Ptr -> Word8 -> Machine ()
assign ptr x = do
  memory <- get
  put $ if x == 0
    then Map.delete ptr memory
    else Map.insert ptr x memory