I am learning how to handle graph-like things in Haskell using the snap-in technique. I suppose looping is just an endless internal implementation of a list, so in an ideal world, you should not worry about subj. But this can have a dramatic effect on computational complexity, consider an example of 1D cellular automata with a looped world:
ribbon = let x = 0 : y y = 1 : x in x update_cycle :: Num a => [a] -> [a] update_cycle lst@ (_:xs) = ( f lst : update_cycle xs) update_cycle [] = error "infinite cycle assumed" f :: Num a => [a] -> a -- some arbitrary list reduction f (x:(y:_)) = traceShow "f called" $ x - y
This is a two-cell loop. Let's take a step:
*Main> take 2 $ update_cycle ribbon [-1,1] "f called" "f called"
Ok, now two steps:
*Main> take 2 $ (update_cycle . update_cycle) ribbon [-2,2] "f called" "f called" "f called" "f called" "f called"
These are five calls instead of four, and it actually means increasing the number of calls at each step, so we have quadratic complexity for the total number of steps instead of linear. I can make cyclic expressions explicit:
newtype UserDefCyclic a = UserDefCyclic { fromTC :: [a] } udcToList :: UserDefCyclic a -> [a] udcToList (UserDefCyclic x) = cycle x update_udc :: Num a => UserDefCyclic a -> UserDefCyclic a update_udc (UserDefCyclic core) = UserDefCyclic $ take (length core) (update_cycle ( cycle core ))
But this is ugly, although I am really interested in more complex structures such as graphics. Question: is there a way to have the code here both pleasant and fast? Or is there a hope that the compiler will do better with the code above in some bright future?
source share