我如何使用类型系统编码和执行合法的 FSM 状态转换？

Question

假设我有一个状态为属性 A | B | C,
的类型 Thing 合法的状态转换是 A->B, A->C, C->A.

我可以写：

transitionToA :: Thing -> Maybe Thing

如果 Thing 处于无法转换到 A 的状态，则 return Nothing。

但我想定义我的类型和转换功能，以便只能在适当的类型上调用转换。

一个选项是创建单独的类型 AThing BThing CThing 但这在复杂的情况下似乎不可维护。

另一种方法是将每个状态编码为它自己的类型：

data A = A Thing
data B = B Thing
data C = C Thing

和

transitionCToA :: C Thing -> A Thing

这对我来说似乎更干净。但我突然想到，A、B、C 是仿函数，除了转换函数外，所有事物函数都可以映射。

有了类型类，我可以创建类似这样的东西：

class ToA t where  
    toA :: t -> A Thing

看起来更干净。

还有其他适用于 Haskell 和 PureScript 的首选方法吗？

Answer 1

这是一个相当简单的方法，它使用（可能是虚幻的）类型参数来跟踪 Thing 处于哪个状态：

{-# LANGUAGE DataKinds, KindSignatures #-}
-- note: not exporting the constructors of Thing
module Thing (Thing, transAB, transAC, transCA) where

data State = A | B | C
data Thing (s :: State) = {- elided; can even be a data family instead -}

transAB :: Thing A -> Thing B
transAC :: Thing A -> Thing C
transCA :: Thing C -> Thing A

transAB = {- elided -}
transAC = {- elided -}
transCA = {- elided -}

Answer 2

由于您的目标是防止开发人员执行非法转换，您可能需要查看 幻像类型。 Phantom 类型允许您在不利用类型系统的更高级功能的情况下对类型安全转换进行建模；因此它们可以移植到多种语言。

这是您上述问题的 PureScript 编码：

foreign import data A :: *
foreign import data B :: *
foreign import data C :: *

data Thing a = Thing

transitionToA :: Thing C -> Thing A

当你有属性两个不同的状态不能转换到相同的状态（除非所有状态可以转换到那种状态）。您可以使用类型类 (class CanTransitionToA a where trans :: Thing a -> Thing A) 解决此限制，但此时，您应该研究其他方法。

Answer 3

您可以使用类型 class（在 PureScript 中可用）以及 John 建议的幻像类型，但使用类型 class 作为路径类型的最终编码：

data A -- States at the type level
data B
data C

class Path p where
  ab :: p A B -- One-step paths
  ac :: p A C
  ca :: p C A
  trans :: forall a b c. p c b -> p b a -> p c a -- Joining paths
  refl :: forall a. p a a

现在您可以创建一类有效路径：

type ValidPath a b = forall p. (Path p) => p a b

roundTrip :: ValidPath A A
roundTrip = trans ca ac

只能使用您提供的一步路径构建路径。

您可以编写实例来使用您的路径，但重要的是，任何实例都必须遵守类型级别的有效转换。

例如，这里有一个计算路径长度的解释：

newtype Length = Length Int

instance pathLength :: Path Length where
  ab = Length 1
  ac = Length 1
  ca = Length 1
  trans (Length n) (Length m) = Length (n + m)
  refl = Length 0

Answer 4

如果您想存储转换列表以便稍后处理，您可以这样做：

{-# LANGUAGE DataKinds, GADTs, KindSignatures, PolyKinds #-}

data State = A | B | C
data Edge (a :: State) (b :: State) where
    EdgeAB :: Edge A B
    EdgeAC :: Edge A C
    EdgeCA :: Edge C A

data Domino (f :: k -> k -> *) (a :: k) (b :: k)  where
    I :: Domino f a a
    (:>>:) :: f a b -> Domino f b c -> Domino f a c

infixr :>>:

example :: Domino Edge A B
example = EdgeAC :>>: EdgeCA :>>: EdgeAB :>>: I

您可以通过为 Domino:

编写连接函数将其转换为的实例

{-# LANGUAGE FlexibleInstances #-}
instance Path (Domino Edge) where
    ab = EdgeAB :>>: I
    ac = EdgeAC :>>: I
    ca = EdgeCA :>>: I

    refl = I
    trans I es' = es'
    trans (e :>>: es) es' = e :>>: (es `trans` es')

事实上，这让我想知道 Hackage 是否已经有一个定义 "indexed monoids":

的包

class IMonoid (m :: k -> k -> *) where
    imempty :: m a a
    imappend :: m a b -> m b c -> m a c

instance IMonoid (Domino e) where
    imempty = I
    imappend I es' = es'
    imappend (e :>>: es) es' = e :>>: (es `imappend` es')

我如何使用类型系统编码和执行合法的 FSM 状态转换？

How can I encode and enforce legal FSM state transitions with a type system?

haskell

purescript