时间戳

首页 > 解决方案 > Haskell 中用于 DSL 的智能链操作符

haskell - Haskell 中用于 DSL 的智能链操作符

问题描述

我有一个Statesum 类型，我需要评估这些状态列表中序列的有效性：

data State = Running | Idle | Stopped | Heating | Broken | Paused | Starting | Stopping
seq = [Stopped, Starting, Running, Paused, Running, Idle, Stopping, Stopped]

对于 的每个元素seq，我需要评估它是否与它之前的一个或多个项目兼容。通过检查和 (可选)的i值，这很容易做到。seqseq !! (i-1)seq !! (i-2)

但是，出于可读性和维护目的，我正在尝试基于链接运算符构建一个 mini-DSL，以便对于 中的每个元素seq，我可以根据其前面的序列评估它是否有效。

按照下面的玩具示例：

-- current/naive implementation
-- (real-world follows the same model but is much more complex)
isValid :: [State] -> Int -> Bool
isValid seq i =
      ite (curr == Running)    (prev1 `elem` [Starting, Idle, Paused])
    $ ite (curr == Idle)       (prev2 `elem` [Paused] && prev1 `elem` [Running])
    $ ite (curr == Broken)     (prev3 `elem` [Running] && prev2 `elem` [Heating] && prev1 `elem` [Heating])
    $ False
    where curr  = seq !! i
          prev1 = seq !! (i-1)
          prev2 = seq !! (i-2)

-- "ideal" implementation using a (|>) chaining operator
-- (with some syntactic liberties)
isValid :: [State] -> Int -> Bool
isValid seq i =
      Running  =>  [Starting, Idle, Paused]
    $ Idle     =>  [Paused]  |> [Running]
    $ Broken   =>  [Running] |> [Heating] |> [Heating]
    where (=>) curr prev   = -- ...
          (|>) prev1 prev2 = -- ...

我最苦苦挣扎的部分是，如何确保(|>)了解它是否必须查找i-1或i-2取决于i-3它被链接的次数，以便：

[Starting]                         -- seq !! (i-1) == Starting
[Starting] |> [Running]            -- seq !! (i-2) == Starting && seq !! (i-1) == Running
[Starting] |> [Running] |> [Idle]  -- seq !! (i-3) == Starting && seq !! (i-2) == Running && seq !! (i-1) == Idle

我并不特别喜欢遵循与上述“理想”版本中完全相同的语法糖，但任何可以接近它的想法或方法都会受到欢迎。

标签： haskelloperatorsdsl

解决方案

您的 DSL 是一种基于上下文的谓词语言（它们说某事是真还是假）（它们在输入的不同部分进行评估）。

特别是，上下文由输入和其中的索引组成：

type Context = ([State], Int)
type Predicate = Context -> Bool

然后我们可以自上而下地研究语言，isValid从根检查定义。首先，它是一个谓词序列。正如您已经注意到的那样，每一行都是一个逻辑暗示，如果任何暗示被破坏，您希望谓词失败。所以我们从谓词的连接开始：

infixr 4 &&.
(&&.) :: Predicate -> Predicate -> Predicate
p &&. q = \c -> p c && q c

蕴涵可以类似地定义，对应的布尔运算与运算相Ord吻合(<=)。

(=>.) :: Predicate -> Predicate -> Predicate
p =>. q = \c -> p c <= q c

在您建议的语法中，的左侧(=>)实际上不是 a Predicate，而是 a State。您可以将其分解为(=>.)我们刚刚定义的谓词的二元运算，以及将状态视为谓词的操作。当您编写 时Running => ...，您试图说“如果当前状态是Running，那么……”。所以一个状态s对应于谓词“当前状态是s”：

current :: State -> Predicate
current s = \(seq, i) ->
  -- Naive version: (seq !! i) == s
  index i seq == Just s

-- Total indexing function
index :: Int -> [a] -> Maybe a
index i seq = listToMaybe (drop i seq)

我们还想谈谈当前状态之前的状态。一种方法是转换谓词以在指向先前状态的修改后的上下文中对其进行评估：

prev :: Predicate -> Predicate
prev p = \(seq, i) -> p (seq, i-1)

在右侧，您还有状态列表，这意味着如果当前状态是其中任何一个，则匹配的谓词：

currentIn :: [State] -> Predicate
currentIn ss = \(seq, i) ->
  case index i seq of
    Nothing -> False
    Just s -> s `elem` ss

使用所有这些基本构建块，我们可以构建更接近您正在寻找的语法的更高级别的组合器。

(|>)在列表中查找当前状态（第一个参数），并将其第二个参数及时移回：

infixr 9 |>
(|>) :: [State] -> Predicate -> Predicate
ss |> q = currentIn ss &&. prev q

-- End delimiter/identity element for `(|>)`
true :: Predicate
true = \_ -> True

(=>+)是一个状态在其左侧的暗示，但也将第二个参数转移到开始直接查看前一个状态（避免保留语法=>）

infixr 8 =>+
(=>+) :: State -> Predicate -> Predicate
s =>+ q = current s &&. prev q

您的示例的相关操作是(&&.), (|>), (=>+)，我们可以注意运算符优先级以避免括号。

isValid :: Predicate
isValid =
        Running  =>+  [Starting, Idle, Paused] |> true
    &&. Idle     =>+  [Paused]  |> [Running] |> true
    &&. Broken   =>+  [Running] |> [Heating] |> [Heating] |> true

最后，我们需要从一个序列中生成所有相关的上下文，以验证整个序列：

allContexts :: [State] -> [Context]
allContexts seq = [(seq, i) | i <- [0 .. length seq - 1]]

validate :: [State] -> Bool
validate seq = all isValid (allContexts seq)

这应该足以让事情正常进行，但人们可能会抱怨的一个大问题是所有这些列表查找都很昂贵。将上下文的表示更改为更适合 DSL 操作的东西会更有效率。值得注意的是，我们希望能够查看当前状态以及之前的状态。因此，更好的表示应该使那些更直接可用：

type Context = [State]  -- A reversed prefix of the whole sequence, so the current state is at the head, and other states precede it.
-- Example:
-- - Old context: ([a,b,c,d,e], 1)    ("the element at position 1 in the list [a,b,c,d,e]")
-- - New context: [b,a]

allContexts :: [State] -> [Context]
allContexts seq = init (tails (reverse seq))  -- non-empty prefixes, reversed

您必须更新所有组合子，但 的定义isValid应保持不变。（读者练习。）

推荐阅读