在阅读了克里斯·彭纳(Chris Penner)在Conway‘s Game of Life Using Represable and Comonads上的博客文章后，我决定为一维自动机规则110实现一个类似的解决方案。作为一个如此简单的算法，我认为它的实现将是微不足道的。然而，事实证明，在Store Comonad中使用任意限定的空间需要巧妙地使用依赖类型来应用回忆化，如Chris'；blog中所述。
这篇博客文章讲述了我尝试使用Store(可在Haskell中表示)来实现规则110的经历，很难找到合适的可表示实例，然后转向Idris，在那里我能够使用有限集类型Fin n来解决问题。
规则110算法采用布尔值的向量，并应用一组简单的规则，用于基于每个索引的邻居来转换每个索引。你可以把它想象成康威的“生活的游戏”的1维变体，但有一点不同，那就是矢量的第一个和最后一个元素被认为是邻居。换句话说，规则110中的自动机存在于圆而不是线段上。
这篇文章不假定事先了解Comonad、可表示的函数器、Fin n。前几节旨在通过重点介绍它们的API的实际实现来介绍这些概念。
Store类型可以被认为是一种查询某些可索引状态的方式，以及在某个索引处查询到存储区的游标。
状态隐式保存在您的查询函数中，稍后我们将看到，状态可以通过组合进行转换。
例如，我们可以构造一个Store，其隐式状态是使用Integer对其进行索引的布尔值的无限列表：
InitialStore：：Store Int Bool initialStore=Store query 0 where query：：int->；Bool query i=(Cycle[True，False])！！腹肌I
然后，Store API允许我们执行查询任意索引、移动光标以及通过其函数器和Comonad实例对查询函数内的隐式状态执行转换等操作。
Peek：：s->；Store s a->；a Peek s(Store Query_)=查询s Peek：：(s-&>s)->；Store s a->；a Peek f(Store Query S)=query(F S)。
PEEK忽略当前游标，转而将新游标应用于商店的查询函数。PEEKS使用函数s->；s修改当前游标，然后使用新游标查询商店。
Seek：：s->；Store s a->；Store s a查找f(Store Query S)=Store Query(F S)。
这个封面是基本的getter和setter，但是如果我们想要一种向我们的商店查询多个索引的方法，该怎么办呢？
PeekMany：：[s]->；Store s a->；[a]peekMany Xs store=FMAP(翻转peek store)Xs。
此函数看起来相当不错，但请注意我们使用的是FMAP。我们可以在这里利用多态性，允许使用任何函数器：
PeekFunctor：：functor f=>；f s->；Store s a->；f a peekFunctor fs store=FMAP(翻转peek store)fs
现在我们可以使用任何我们想要的函数器，但是请注意我们是如何根本不使用光标的。这是一个线索，表明我们也许能够进一步推广这个函数。
如果我们可以修改peekFunctor以使用我们的游标值，而不会丢失函数的当前行为，那就太好了。
如果我们用函数s->；f s替换f s参数，那么我们可以将当前游标应用于我们的函数，并生成f s来生成我们的f a输出。然后，如果我们想要peekFunctor的精确行为，我们可以简单地应用const(x：：fs)并忽略当前游标！
实验：：Functor f=>；(s->；f s)->；store s a->；f a实验f store=FMAP(Flip Peek Store)(f(Pos Store))。
POS：：Store s a-&>；a Peek：：S-&>；Store s a-&>；a Peek：：(S-&>；Store s a-&>；a Seek：：S-&>；Store s a->；a Seek：：(S-&>)Store s a-&>；a实验：：Functor f=>；(s-&>；f s)->；商店s a->；f a。
系统的状态隐含地存储在查询函数内，而不是存储在某种数据结构中。因此，修改状态的唯一方法是修改查询函数本身。
为此，我们可以首先查询当前存储以获得a值，然后对该值应用某个a->b函数，以生成该索引处的状态的修改版本。
我们可以通过在Store上进行模式匹配来实现这一点，然后将a-&>b函数与我们的查询函数组合在一起：
UpdateStoreState：：(a->b)->；Store s a->；Store s b updateStoreState f(Store Query S)=Store(f.。查询)%s。
UpdateStoreState允许您修改Store隐式状态内所有可能值的查询结果。这个签名看起来应该很熟悉，因为它是FMAP，而Store实际上是一个函数器。
实例函数(Store S)，其中FMAP：：(a->b)->；Store s a->；Store s b FMAP f(Store Query S)=Store(f.。查询)%s。
现在，我们可以通过应用FMAP来建模状态的连续转换。例如，使用前面的Store Int Bool示例，我们可能希望应用Not：：Bool->；Bool来反转系统的状态：
InitialStore：：Store Int Bool initialStore=Store query 0 where query i=(Cycle[True，False])！！I NewState：：Store Int Bool NewState=FMAP NOT InitialStore。
NewState=FMAP NOT InitialStore=FMAP NOT(Store Query S)=Store(NOT.。查询)%s。
使用此技术对系统的3个操作进行建模，显示了对隐式状态的每次修改如何构建更大的组合查询函数：
NewState：：(a-&>b)-&>；(b-&>；c)-&>；(c-&>d)->；Store s a->；Store s b Newstate h g f store=FMAP f(FMAP g(FMAP H Store))=FMAP f(FMAP g(FMAP h(Store Query S)=FMAP f(FMAP g(Store(h.。查询)s)=FMAP f(存储(g。H.。查询)s)=存储(f.。G。H.。查询)%s
虽然优雅，但将状态转换建模为函数组合意味着每次查询Store中的索引时，都必须重新计算返回到原始Store查询的每个先前的转换。如果不缓存这些中间计算，这将变得非常昂贵。
幸运的是，Chris Penner使用可表示的函数器向我们展示了一个奇妙的解决方案。我们很快就会看一下Reportable，但现在让我们忽略性能问题，将重点放在我们需要的工具上，以便天真地实现规则110。
Comonad是单曲的对偶。单音节通过a->；m b形式为论点引入一些效果，而单音节则引入查询数据结构的概念(共同效果)：
--一元a-&>m a重复：：a-&>；[a]--并元w a->；a长度：：[a]->；整数。
类函数w=>；Comonad w其中Extract：：w a->；a副本：：w a->；w(W A)扩展：：(w a->；b)->；w a->；w b。
提取：：w a->；a返回：：a->；m副本：：w a->；w(W A)联接：：m(M A)->；m a扩展：：(w a->；b)->；w a->；w b(=<；<；)：：(a->；m b)->；m a->；m b。
如果Haskell中Comonad的一个定义特征是提供一种查询数据结构的机制，那么我们几乎可以肯定地说Store是一个Comonad。存储实际上是查询结构以产生数据的机制！
实例Comonad(Store S)WHERE Extract：：Store s a->；a Extract(Store Query S)=查询s Extension：：(Store s a-&>b)->；Store s a->；Store s b Extension f(Store Query S)=Store(\s&39；-&>f(Store Query s&39；))s
Extract将当前游标应用于查询函数，并扩展链状态转换查询。
在这种情况下，Extract相当简单，但Extension则稍微棘手一些。这有助于考虑与我们的FMAP实现相关的问题。
与FMAP一样，它使用一个函数来修改我们的隐式状态，但是当FMAP使用我们的查询组成一个纯a->b函数时，Extended通过将整个存储应用于一个共同的操作来创建一个新的查询函数。这允许我们在修改商店中的特定点时将整个当前商店纳入范围。
Extension非常强大，允许我们做一些非常有趣的事情，比如创建窗口函数和执行内核卷积。它允许我们使用整个状态作为上下文来修改并行中的每个单独的点。
EXTEND的一个有趣的例子是对一些时间序列数据执行移动平均。
首先，我们需要一个存储建模时间排序的数据。我们将使用Int作为索引，它将表示数据流中的单个时间单位。我们需要一些相当动态的数据源，所以我选择了Fibbonaci序列。在每个时间点(每个指数)，我们得到下一个Fibbonaci数。
FiStore：：store Int Int fib Store=store query 0 where query：：int->；Int query 0=0 query 1=1 query n=query(n-1)+query(n-2)。
现在，如果我们想要从给定的游标开始计算一个窗口，需要某种方法来查询后续的时间点。体验将在这里完美发挥作用：
现在请注意，窗口的形状是Store Int a->；[a]。这看起来很像EXTEND：STORE s a->；b的共同操作。我们可以使用EXTEND将窗口应用于Enter Store：
现在，如果我们看一看商店中的任何指数，我们会看到一个随后的斐波纳奇数字的窗口！
有了现在可用的工具，我们可以第一次尝试我们的规则110算法。
Type Index=Int initializeStore：：[Bool]->；Store Index Bool InitializeStore xs=Store query 0 where query：：index->；Bool query i=xs！！我。
我们将初始状态建模为列表，并对查询使用不安全的列表查找函数。这不是很理想，但我们只是在试着起草一份粗略的草稿。
接下来，我们需要一种查询索引及其邻居的方法。就像我们的窗口函数一样，我们可以在这里使用实验。
_lookupIndices是我们需要填充的类型空洞。从Neighbor Values开始，我们让GHC告诉我们lookupIndices需要什么形状：
但这解释了我们的自动机生活在一个圆上，而不是一条线上。我们需要能够识别第一个和最后一个索引，并使用该信息选择正确的邻居。
第一个也是最简单的解决方案是将列表的长度作为值传入：
Type Index=Int type size=Int lookupIndices：：size->；Index->；[Index]lookupIndices size I|i==0=[size-1，0，1]|i==size-1=[i-1，i，0]|否则=[i-1，i，i+1]邻居：size-gt；Store Int Bool->；[Bool]Neighbors size=实验(LookupIndices Size)。
通过一种机制来查找索引及其邻居的状态，我们接下来需要使用该信息来计算索引的下一个状态。我们可以通过使用NeighbValues的输出大小写来实现这一点：
现在，我们需要对邻居的状态进行案例分析，并应用我们的准则来确定索引处的新状态：
NewState：：Size->；存储索引Bool->；Bool Newstate Size Store=案例邻居大小存储[False，False，False]->；False[True，False，False]->；False[True，True，True]->；False_->；True。
最后，我们需要一种将此转换应用于整个商店的方法，以创建下一代自动机。伸出援手去营救！
NextGen：：Size->；商店索引Bool->；商店索引Bool NextGen Size=EXTEND(新州大小)。
让我们使用等式推理来仔细看看调用NextGen时会发生什么：
下一代大小STORE=EXTEND(Newstate Size)STORE=EXTEND(Newstate Size)(Store Query S)=Store(\s'；-&>；(Newstate Size)(Store Query s'；))s。
下一代大小(NextGen Size Store)=EXTEND(NESTATE SIZE)(EXTEND(NESTATE SIZE)STORE)=EXTEND(NESTATE SIZE)(EXTEND(NESTATE SIZE)(存储查询))=EXTEND(NESTATE SIZE)(Store(\s&39；->；(Newstate Size)(Store Query s'；))s)=Store(\s'；&39；->；(NEWSTATE SIZE)(STORE(\s&39；->；(新州大小)(商店查询s'；))s'；'；))%s。
这有点难理解，但是如果您稍微眯着眼睛就可以看到，我们正在通过链接商店上的newstate调用来构建我们的查询函数。因此，无论何时查询索引，组合查询函数都会多次将NEWSTATE应用到您的商店。
工作实现的最后一步是以列表形式查看商店的函数。这本身并不是算法的一部分，但我们确实想要一种查看结果的方式！
ViewStore：：Size->；Store Index Bool->；[Bool]viewStore Size store=实验(const[0..size])store。
要运行模拟，我们可以在IO中使用递归函数来重复打印viewStore的结果，然后调用NextGen来更新状态：
运行模拟：：SIZE->；存储索引Bool->；IO()Run模拟大小STORE=DO PRINT$viewStore SIZE STORE Run模拟大小$NextGen SIZE STORE。
这个实现确实可以工作，但是如果您尝试运行它，您会发现它存在严重的性能问题。延长新一代意味着增加到新州的一系列电话。
这个不断增长的查询函数在您每次查看索引时都必须进行完整的计算。当我们调用runSimulation时，我们对每一代的每个索引都这样做。
不过，实际上比那更糟！要计算每个指数的新状态，我们还必须查看其邻居。因此，这意味着对于每个索引，我们将重复相同的巨大查询3次！
函数f是可表示的，如果它具有完全索引f的对应类型Rep f。对于Rep f的每个值，必须有一个有效的f索引，同时我们必须能够构造一个容器，其中容器中的每个元素都是从其Rep f索引中产生的。
另一种更正式的表述方式是，f a和Rep f->；a之间必须存在同构。来自可表示类型类的表格和索引函数证明了这种同构：
类函数f=>；可表示f，其中类型Rep f：：*Tablate：：(Rep f->；a)->；f a索引：：f a->；(Rep f->；a)。
很难确切地看出这对我们有什么用处，但我们可以玩一个聪明的把戏，让代表人免费获得备忘录。
TABLATE将接受一些函数，该函数从Repf值生成a值，然后构造一个可表示的f，其中包含每个可能的Repf值的a值。
索引允许您使用Rep f来查询a值的可表示f。RETRACTABLE的一个很好的属性是，如果你有一个合法的实例，那么索引必须是一个安全的函数，而不需要可能！
函数器最明显的首选是[]，但是我们会对rep f使用什么呢？Int不起作用，因为您不能在[]中使用负索引。NAT几乎可以工作，但是如果列表为空会发生什么呢？遗憾的是，[]没有可表示的实例。
NonEmpty解决了这些问题，但是对于每个NAT，仍然可以有一个没有元素的NonEmpty。
Newtype Stream a=CONS a(Strema A)数据NAT=Z|S NAT实例functor Stream Where FMAP：：(a->b)->；Stream a->；Stream b FMAP f(Stream A As)=CONS(F A)(FMAP F As)实例可表示流，其中type Rep f=NAT Tablate：：(NAT-&>a)->；Stream a Tablate f=CONS(F Z)(Tablate(f.。S))index：：stream a-&>；NAT-&>；a index(CONS A As)Z=a index(CONS_AS)(SN)=index as n。
数据标识a=标识实例函数器标识，其中FMAP f(标识a)=标识(F A)实例可表示标识，其中类型表示f=()TABLATLE：：(()->；a)->；标识a表f=标识$f()index：：标识a->；()->；a索引(标识a)()=a。
由于标识只能包含单个a，并且()由单个值驻留，因此此实例是合法的和完全的。：)。
如果我们的Store只有一个元素，那么标识将非常适合表示对它的查询，同样，如果它有无限数量的元素，则Stream可能是完美的。然而，我们正在寻找介于两者之间的东西。
我们需要的是某种有界数据结构，但是为了使其可表示，我们还需要相应的有界索引类型Rep f。Identity和()就是这样的有界可表示的一个很好的例子，但是它的界限是1个元素的固定大小。我们想要一些函数器f和代表f，在那里我们可以将边界固定在我们想要的任何大小。
另一种说法是，我们想要的是一个可表示函数族和一个对应的Rep f类型族，每个可能的大小边界对应一个配对。
我们可以使用Vect n a和Fin n a来实现这一点。Vect是一个固定长度的向量，其长度用类型级别NAT编码。FIN是有限自然数，其最大值使用类型级别NAT进行编码。
Data Vect(n：：NAT)a WHERE VNIL：：Vect Z a VCons：：A->；Vect n a->；Vect n a->；Vect(SN)a Data FIN(n：：NAT)Where FZ：：FIN(SN)FS：：FIN n->；Fin(SN)。
就这样，我们进入了依赖类型的世界。哈斯克尔的世界非常混乱和令人困惑。现在是时候切换到Idris了，但是不要担心到目前为止所有的实现都是相同的，只是稍有一些语法上的变化。
接口函数f=>；可表示(f：type->；type)(rep：type)|f其中TABLATE：(rep->；a)->；f a索引：f a->；rep->；a可表示(Vect N)(Fin N)，其中TABLATE f{n=Z}=[]TABLATE f{n=(S K)}=f FZ：：TABLATE(f.。Fs)index(x：：_)fz{n=(Sk)}=x index(_：：xs)(FS X){n=(Sk)}=index xs x。
在Idris中，"；类型Level"；和"；Term Level之间没有区别。"；类型是一流的值，可以像任何其他值一样传递和使用。
相应地，类型参数(如Vect n(Fin N)中的n)与术语级别参数相同，可以传递到匹配的函数和模式中。您可以在上面的TABLATE定义中看到这一点，其中来自Vect n的n用大括号括起来，并被当作函数参数对待。
大括号表示它是一个隐式参数。这意味着类型检查器能够推断参数的值，调用者永远不需要显式地传入值。这可能看起来很神奇，但它非常类似于您在Haskell中习惯的类型推断。
使用此REFACTABLE实例，索引类型Fin n永远不能生成大于n-1的值，并且函数器的大小必须为n。这在编译时是有保证的。
这意味着通过为n选择一个不同的值，我们可以为任意固定长度的向量提供一个可表示的实例。
现在我们已经切换到Idris，我们需要重写Store类型。我们还需要使其与可代表合作：
数据存储：(类型->类型)-&>；类型-&>；类型-&>类型MkStore：rep->；f a->；Store f rep a。
这个版本的Store包含我们的当前索引(现在称为rep)和我们可表示的类型f a。我们不再有查询函数。相反，我们将把我们的状态存储为R中的数据。
.