Haskell 状态为函数类型

Question

我很难理解本教程：https://acm.wustl.edu/functional/state-monad.php

我正在创建自己的函数来反转列表和 returns 具有最低元素和列表反转的 State。我也是 Haskell 的新手。这是我的代码：

myFunct :: Ord a => [a] -> State a [a]
myFunct t = do
        let s = reverse t
        let a = minimum t
        return s a

我也找不到其他 material。这是我收到的错误。

 Couldn't match type ‘[a]’
                 with ‘StateT a Data.Functor.Identity.Identity [a]’
  Expected type: a -> State a [a]
    Actual type: a -> [a]
• The function ‘return’ is applied to two arguments,
  its type is ‘a0 -> m0 a0’,
  it is specialized to ‘[a] -> a -> [a]’
  In a stmt of a 'do' block: return s a
  In the expression:
    do let s = reverse t
       let a = minimum t
       return s a

Answer 1

由于您使用的是 do 块，我假设您想要使用 State 作为 Monad。这很好，但我建议，然后，将值列表 ([a]) 设为状态，将单个最小值设为 'return value'.

这意味着您可以将函数的类型简化为 myFunct :: Ord a => State [a] a。 [a] 是状态的类型，a 是 return 值的类型。

请注意，没有明确的 'input value'。在 State monad 中，状态是一个始终存在的隐式上下文。

您现在可以像这样重写计算：

myFunct :: Ord a => State [a] a
myFunct = do
  t <- get
  let s = reverse t
  put s
  let a = minimum t
  return a

你可以把计算写得更简洁，但我选择明确地写出来，以便更清楚地了解发生了什么。 get 检索隐式状态的当前值，put 覆盖状态。有关详细信息，请参阅 the documentation。

你可以运行这样：

*Q49164810> runState myFunct [42, 1337]
(42,[1337,42])
*Q49164810> runState myFunct [42, 1337, 0]
(0,[0,1337,42])
*Q49164810> evalState myFunct [42, 1337, 0]
0
*Q49164810> execState myFunct [42, 1337, 0]
[0,1337,42]

runState 采用初始状态，运行是 myFunct 计算，return 是 return 值和最终状态。 evalState 的工作方式相同，但 return 只是 return 值，而 exacState 只是 return 的最终状态。

Answer 2

你很幸运：State 是最容易理解的单子。

请不要因为您的函数根本不需要 State 而气馁，只要您使用标准库中的 reverse 和 minimum。

myFunct' :: Ord a => [a] -> ([a], a)
myFunct' xs = (reverse xs, minimum xs)

（它会运行像这样:)

λ myFunct' [1,2,3]
([3,2,1],1)

但请注意，为了将 reverse 和 minimum 应用于列表，您需要遍历它两次。这是 State 可能派上用场的时候：使用它，您只能遍历列表一次，因此，希望获得一些加速。继续阅读以了解具体方法。

所以，State是一个特殊的函数：你给它的东西（也叫"state"）保存在一个魔法盒里在那里你可以观察它，或者随时用另一个相同类型的东西替换它。如果您有使用命令式语言的经验，您可能会发现很容易将 State 视为命令式过程，将 "state" 视为局部变量。让我们回顾一下您可以用来构建和执行 State:

的工具

您可以观察盒子里的东西（命名不当）函数get .请注意，这不会以任何方式改变状态——您获得的只是其当前值的一个不可变副本；东西留在盒子里。

您通常会将您的观察与一个名称相关联，然后将其用作普通值 - 例如，传递给一个纯函数：

stateExample1 :: State Integer Integer
stateExample1 = do
    x <- get  -- This is where we observe state and associate it with the name "x".
    return $ x * 2  -- (* 2) is an example of a pure function.

λ runState stateExample1 10
(20,10)  -- The first is the return value, the second is the (unchanged) state.

您可以用其他适当类型的东西替换盒子里的东西；使用函数 put:

stateExample2 :: State Integer Integer stateExample2 = do x <- get put $ x * 2 -- You may think of it as though it were "x = x * 2" -- in an imperative language. return x

λ runState stateExample2 10 (10,20) -- Now we have changed the state, and return its initial value for reference.

请注意，虽然我们改变了状态，但我们对它的观察（我们命名为 "x"）仍然具有相同的值。

你可以运行 State 函数，给它一个参数（我们称之为“初始状态"):

y = runState stateExample1 10

等同于：

y = stateExample1(10);

− 在具有 C-like 语法的命令式语言中，除了您同时获得 return 值和 最终状态 .

有了这些知识，我们现在可以像这样重写你提议的 myFunct：

myFunct :: Ord a => [a] -> State (Maybe a) [a] myFunct [ ] = return [ ] myFunct t = do let s = reverse t let a = minimum t put (Just a) return s

λ runState (myFunct [1,2,3]) (Just (-100)) ([3,2,1],Just 1) λ runState (myFunct []) (Just (-100)) ([],Just (-100))

如果我们将 State 视为一个命令式过程，那么反转列表就是它 return 的样子，而列表的最小值就是它的最终状态。由于列表可能为空，我们为最小值提供了一个可选的默认值。这样使得函数总，算是不错的Haskell风格：

λ myFunct' [] ([],*** Exception: Prelude.minimum: empty list λ runState (myFunct []) Nothing ([],Nothing)

现在，让我们通过编写一个函数来获得 State 的好处，该函数 return 一次完成列表的最小值和反向：

reverseAndMinimum :: Ord a => [a] -> ([a], Maybe a) reverseAndMinimum xs = runState (reverseAndMinimum' xs [ ]) Nothing reverseAndMinimum' :: Ord a => [a] -> [a] -> State (Maybe a) [a] reverseAndMinimum' [ ] res = return res reverseAndMinimum' (x:xs) res = do smallestSoFar <- get case smallestSoFar of Nothing -> put $ Just x Just y -> when (x < y) (put $ Just x) reverseAndMinimum' xs (x: res)

首先，这是一个迭代算法，因此需要一个最小值的起始值。我们将此事实隐藏在 reverseAndMinimum' 中，提供 Nothing 作为起始值。

反向部分的逻辑我借鉴了现代Prelude.reverse。我们只是将元素从第一个参数 xs 移动到第二个参数 res，直到 xs 为空。

这部分就是求当前x和state box存储的值中较小的那部分。我希望你会发现它可读。

case smallestSoFar of Nothing -> put $ Just x Just y -> when (x < y) (put $ Just x)

这是执行递归的部分：

reverseAndMinimum' xs (x: res)

它再次应用 reverseAndMinimum'，但适用于更小的列表 xs； monadic 接线自动将当前最小值的盒子传送到线路下。

让我们跟踪对 reverseAndMinimum' 的调用的执行情况。假设我们说：

runState (reverseAndMinimum' [1,2,3] [ ]) Nothing

会发生什么？

1和Nothing中较小的一个是1。因此，框中的 Nothing 将替换为 Just 1。

State会被再次调用，就像我们用这样的代码调用它一样：

runState (reverseAndMinimum' [2,3] [1]) (Just 1)

以此类推，直到参数变为空列表，此时方框一定会包含最小的数字。

这个版本实际上 比 myFunct' 快 22% ，并且使用的内存也少一些。（尽管您可能会查看编辑历史记录，但需要一些努力才能找到它。）

就是这样。希望对您有所帮助！

特别感谢 Li-Yao 夏为 reverseAndMinimum 设计的代码实际上击败了 myFunct'.

Haskell 状态为函数类型

Haskell State as function type

haskell

state-monad