Abelian Actions

Abelian Actions on a Zipper

The goal here is to write an Action class which depends on an Abelian data type
and acts on a Zipper type. Composition of left Abelian actions Ab x G -> G and
evaluation are then given in the instance declaration for Action (Zipper v).

I begin by importing some useful modules and then defining a Zipper.

import System.Random
import Text.Printf
import Data.Char

data Zipper a = Z {left :: [a], focus :: a, right :: [a]} deriving (Eq, Ord)

shiftLeft :: Zipper a -> Zipper a
shiftLeft (Z (a:as) b cs) = Z as a (b:cs)

shiftRight :: Zipper a -> Zipper a
shiftRight (Z as b (c:cs)) = Z (b:as) c cs

instance Show a => Show (Zipper a) where
   show (Z a b c) = printf format (ff reverse a) (show b) (ff id c)
      format = "[..%s { %s } %s..]\n"
      ff f = unwords.(map show).f.(take 10)

Notice that we can shiftLeft and shiftRight along our Zipper and further
there is a homespun Show instance so that these potentially infinite Zippers
can be displayed easily.

integers :: Zipper Integer
integers = Z (map negate [1..]) 0 [1..]

alphabet :: Zipper Char
alphabet = Z sahpla 'a' (tail alphas)
    alphas = [chr $ mod n 26 + 97  | n<- [0..]]
    sahpla = [chr $ 122 - mod n 26 | n<- [0..]]
[..'q' 'r' 's' 't' 'u' 'v' 'w' 'x' 'y' 'z' { 'a' } 'b' 'c' 'd' 'e' 'f' 'g' 'h' 'i' 'j' 'k'..]

Ok, so now there are Zippers. Now for an Abelian data type which can be extended
naturally to the Monoid class.

data Abelian = P Int | N Int

instance Eq Abelian where
  (==) (P n) (N m) = (n==m) && (n==0)
  (==) (P n) (P m) = n == m
  (==) (N n) (N m) = n == m

instance Monoid Abelian where
  mappend (P n) (P m) = P $ n + m
  mappend (P n) (N m) | n - m >= 0 = P $ n - m
                      | otherwise = N $ n - m
  mappend (N n) (P m) | m - n >= 0 = P $ m - n
                      | otherwise = N $ m - n
  mappend (N n) (N m) = P $ n + m
  mempty = P 0

Underlying Abelian is the type Int, which can be immediately recognized
as the de facto Abelian Object. Abelian is first extended to the Eq class
so that we can tell when two elements are the same. Next, instances for what is
meant by mempty and mappend are given for Abelian objects. mappend is really
just addition and mempty just 0.

Next, the Action class is defined so that given some Action v one can
compose Abelian operations and evaluate with respect to v. In other words,
the Action class characterizes left actions on v.

Lastly, I give an instance of Action Zipper.

class Action v where -- actions: Ab x G -> G
  compose :: [Abelian] -> v a -> v a
  eval :: Abelian -> v a -> v a

instance Action Zipper where
  compose abs = eval (foldr mappend mempty abs)
  eval (P n) = (!! n).iterate shiftRight
  eval (N n) = (!! n).iterate shiftLeft

Now to test it out! Let’s apply shortRandomWalk :: [Abelian], a list of random Abelian operations, to alphabet and return the zipper’s focus.

shortRandomWalk :: [Abelian]
shortRandomWalk = take (2^15) $ run.(randomRs (-10, 10)).mkStdGen $ 32
    run (x:xs) | x >= 0 = P x : run xs
               | otherwise = N (abs x) : run xs

focus.compose shortRandomWalk $ alphabet


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s