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)
where
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)
where
alphas = [chr $ mod n 26 + 97 | n<- [0..]]
sahpla = [chr $ 122 - mod n 26 | n<- [0..]]
alphabet
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
where
run (x:xs) | x >= 0 = P x : run xs
| otherwise = N (abs x) : run xs
focus.compose shortRandomWalk $ alphabet
nice.
Jonathan Zingale 