Just a quicky, I found a function that returns nice breadth first orderings of the graphs.
gIterate2 :: (b -> [b]) -> [b] -> [[b]]
gIterate2 f xs = iterate (concat. map f) xs
You can even avoid cycles by making the Data type a tuple with a set and then using a function like the following
take 4 $ gIterate2 (\(x,y) -> if member x y then [] else ((x+1), insert x y):[(x-1, insert x y )]) [(1, empty)]
This gets a list of all the nodes 4 iterations away from the original. It does have some limitations compared to the way I did it yesterday in that it can’t return a different type (due to the use of iterate). You can get around this somewhat by using a tuple again with a dummy return value placed in.
Edit from here for added value.
Now that isn’t very pretty lets define a function noRepeat that you can apply to any function a -> [a] to filter out repeats
noRepeat :: (Ord t) => (t -> [a]) -> (t, Set t) -> [(a, Set t)]
noRepeat f (x,y) = if member x y then [] else zip (f x) (repeat (insert x y))
The basic type is (a -> [a]) -> b -> [b]
Let us call this a function transformer. Now the basic output from that is pretty ugly
take 5 $ gIterate2 (noRepeat (\x -> (x+1):[(x-1)])) [(1, empty)]
[[(1,fromList [])],[(2,fromList [1]),(0,fromList [1])],[(3,fromList [1,2]),(1,fromList [1,2]),(1,fromList [0,1]),(-1,fromList [0,1])],[(4,fromList [1,2,3]),(2,fromList [1,2,3]),(0,fromList [-1,0,1]),(-2,fromList [-1,0,1])],[(5,fromList [1,2,3,4]),(3,fromList [1,2,3,4]),(-1,fromList [-2,-1,0,1]),(-3,fromList [-2,-1,0,1])]]
So what can we do? Well if we map (map fst) on it we can get back just the list of nodes. We’ll call the fst the “detransformer” of noRepeat.
So lets create a data type
data TransTriple m a b = Dere {getInit :: a -> b, getTransform :: (a-> m a) -> (b -> m b), getDetrans:: b -> a}
This defines a way to initialise the change, a way to transform the step function given normally and a way to get back to the original value.
gtransformIter pair f xs = Prelude.map (Prelude.map (getDetrans pair)) $ gIterate2 (getTransform pair$ f) (Prelude.map (getInit pair) xs)
We define a new function to take all of these and apply them properly to gIterate2.
a `comp` b = Dere (\x -> getInit a $ getInit b$ x ) (\x -> getTransform a $ getTransform b$ x ) (\x -> getDetrans b $ getDetrans a $ x)
Why do we do this? So we can compose them together. `comp` acts as (.) but for all the functions in the right order. It is not very pretty at the moment.
So let us define a couple of transformer triples.
noRepeat f (x,y) = if member x y then [] else zip (f x) (repeat (insert x y))
stopWhen cond f x = if cond x then [] else f x
noRepeatTriple = Dere (\x -> (x, empty)) (noRepeat) fst
notFiveTriple = Dere id (stopWhen(==5)) id
So you can now call something like
gtransformIter (noRepeatTriple `comp` notFiveTriple) (\x -> (x+1):[(x-1)]) [1]
And it spit out a pure list of numbers, ignoring any branches that get to 5 or any that start to cycle.
I’ll try and do a simple game search next time using this framework.
