这种类型不是广义DFA有什么特别的原因吗？如果是这样,那真的是什么？

Question

我正在Scala中组建一个基本结构库,用于生产或个人学习.我专注于在类型理论,猫理论,集合论中对所述结构的清晰描述.其中一种类型,

abstract case class Fold[A, B]() {
  type I
  def trans: I => A => I
  def start: I
  def output: I => B

  def cojoin: Fold[A, Fold[A, B]] 
  def copoint: B    
  def dimap[Z, C](f: Z => A, g: B => C): Fold[Z, C]
 }

这是(我很确定)同构的,
(信用:http://www.haskellforall.com/2013/08/composable-streaming-folds.html)

abstract case class Fold'[A, B]() {
  type W
  def MonW: Monoid[W]
  def tally: A => W
  def summerize: W => B
}

对我来说,其中一种类型非常类似于DFA,而在https://www.fpcomplete.com/user/edwardk/cellular-automata/part-2中 ,Kmett先生基本上也说了很多.我的问题是,如果不是 DFA,这种类型是什么？

Answer 1

此类型不代表DFA,因为它太笼统.具体而言,该I类型可能能够承担无限多的值.如果你制作I某种类型的序列(或者更好,其中两个)与代表有限状态的东西配对,你可以直接模拟图灵机.