5

我正在研究使用“打结”技术在 Haskell 中处理类似图形的事物。我想，循环列表只是一种无限列表内部实现，所以在理想世界中，人们不应该关心主题。但它会对计算复杂性产生显着影响，考虑以下示例，具有循环世界的一维元胞自动机：

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

这是一个只有两个单元的循环。让我们迈出一步：

*Main> take 2 $ update_cycle ribbon
[-1,1]
"f called"
"f called"

很好，现在分两步：

*Main> take 2 $ (update_cycle . update_cycle) ribbon
[-2,2]
"f called"
"f called"
"f called"
"f called"
"f called"

这是 5 次调用而不是 4 次，这实际上意味着增加每一步的调用次数，所以我们在总步数上具有二次复杂度而不是线性。我可以使循环明确，如下所示：

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 ))

但这很丑，虽然我真的对更复杂的结构感兴趣，比如图形。问题：有没有办法让这里的代码既好又快？还是希望编译器在某个光明的未来能够更好地处理上面的代码？

4

0 回答 0