更新 Haskell 中的值

Question

我正在尝试使用区间作为可能值的范围对一组值应用约束。我很难制定一种方法来在 Haskell.

中应用这些约束

假设我有一个 b = 10 形式的约束和一个 a = f(b,c) 形式的约束，显然第一个约束将改变第二个约束的应用方式，但是我不确定如何在函数式语言。在命令式程序中，我们将更改 b 的间隔并在第二个约束中使用它的新值。

任何帮助将不胜感激，本

Answer 1

这个问题可能与 "too general" 接壤，所以这里可能是 "too general" 的答案，尽管我已经尝试包含一些细节（包括一个工作示例）。

在这样的问题中，典型的命令式方法可能会使用单个数据结构来 (1) 存储输入约束； (2) 在读取约束时充当实时擦除 space 进行处理； (3) 执行任何最终计算以产生结果。

在 Haskell 实施中，通常将其分成不同的步骤：

构建一个表示输入约束系统的纯数据结构，没有很多复杂的处理。
使用状态 monad 遍历数据结构以在处理约束时携带"discoveries"。
通过查询最终状态或作为遍历数据结构的副产品生成最终结果，以更方便的为准。

Haskell 的懒惰求值在这里可以提供帮助。尽管这些步骤的实现是分开的，但按需评估方案意味着计算在实践中是交错的，就像它们在命令式实现中一样，所以结果是在输入约束遍历数据结构时生成的加载到约束系统表示中。但是，单独的功能组件通常更容易构建和推理。

作为一个过度简化的示例，假设您要在变量之间实现等式约束（即一组 x==y 形式的约束）。在这里，对于第 1 步，表示约束系统的纯数据结构非常简单：

type Name = String
data Constraint = Equals Name Name deriving (Show)    -- ^An equality constraint
type System = [Constraint]                            -- ^A constraint system

在一个更实际的示例中，可能有多种约束类型 and/or 您可以选择将它们组织在地图中，该地图由约束引用的变量键入（只要便于处理）。这里的关键见解是数据结构是纯粹的和不可变的，并且没有反映任何对约束的严肃计算。它主要是输入的直接表示。

对于第 2 步，在这种简单的情况下，通过学习约束获得的 "knowledge" 的合理状态表示是一组等价 classes。我们可以使用 Map Name Name——从给定名称 n 到其最终名称 n' 的链给出 class 的代表，因此如果两个名称具有链以相同的最终名称结尾，它们是相等的：

type St = Map Name Name

同样，在一个更现实的示例中，此状态可能包含约束系统表示的副本，并在处理系统时用发现进行注释。这些注释可以通过对数据结构进行常规的功能操作来添加；或者，您可能会发现在这里引入真正的可变数据结构和运行 ST 或 IO monad 中的所有内容很有用。

无论如何，继续我们示例的第 2 步，然后我们可以想象遍历约束 System 来更新此状态。这里 S 是 shorthand for State St，一个状态 monad 与我们的 St 状态。

walk :: System -> S ()
walk = mapM_ learn
learn :: Constraint -> S ()
learn = ...   -- update state to reflect knowledge from constraint

最后，对于第 3 步，我们可以定义一个函数来读取 "solution"，在我们的例子中，它采用 (Name,Name) 对列表的形式，其中 ("x","u") 表示变量 "x" 等于其代表 "u"（具有该代表的任何其他变量也等于 "u" 和 "x"s）。这可以在 S monad 之外完成，作为对 walk 返回的最终状态的纯粹计算，但我在 S monad here 中完成了它。

solution :: S [(Name,Name)]
solution = do ns <- gets (Map.keys)
              zip ns <$> mapM rep ns

这里，函数 rep :: Name -> S Name 使用状态来跟踪从提供的名称 n 到其代表 n'.

的链

唯一缺少的部分是 learn 的实现。这是一个完整的工作示例。我希望这能给你一些关于如何开始的想法

module Constraint where

import Control.Monad.State
import Data.List
import Data.Maybe (catMaybes)
import Data.Map (Map)
import qualified Data.Map as Map

type Name = String
data Constraint = Equals Name Name deriving (Show)    -- ^An equality constraint
type System = [Constraint]                            -- ^A constraint system

-- |State representing evolving computation as collection of
-- equivalence classes.  Each name `n` maps to smaller `n'` and
-- following chain leads to class representative.  A much more
-- efficient implementation is possible (see the "equivalence"
-- package, for example, which uses a mutable data structure).
type St = Map Name Name   -- ^Our state
type S = State St         -- ^Monad w/ our state
evalS = flip evalState Map.empty
runS  = flip runState Map.empty

-- |Get equivalence class representative
rep :: Name -> S Name
rep n = do
  s <- gets (Map.lookup n)
  case s of Just n' | n /= n' -> rep n'
                    | otherwise -> error "rep: cycle in chain"
            Nothing -> return n

-- |Set link in equivalence class chain
set :: Name -> Name -> S ()
set n n' = when (n /= n') $ modify (Map.insert n n')

-- |Learn a new constraint
learn :: Constraint -> S ()
learn (Equals x y) = do rx <- rep x
                        ry <- rep y
                        unify rx ry

-- |Unify equivalence classes for two names
unify :: Name -> Name -> S ()
unify n n' | n < n'    = unify n' n
           | otherwise = set n n'

-- |Walk a system of constraints, learning them as we go
walk :: System -> S ()
walk = mapM_ learn

-- |Generate solution from complete state
solution :: S [(Name,Name)]
solution = do ns <- gets (Map.keys)
              zip ns <$> mapM rep ns


test :: [(Name, Name)]
test = evalS $ do -- Step 1: a pure representation of the constraint system
                  let sys = [ Equals "x" "y"
                            , Equals "u" "v"
                            , Equals "v" "z"
                            , Equals "a" "b"
                            , Equals "x" "w"
                            ]
                  -- Step 2: walk the system, learning state as we go
                  walk sys
                  -- Step 3: produce the solution from the state
                  solution

更新 Haskell 中的值

Updating values in Haskell

haskell

constraints

intervals