haskell - 在 Haskell 中实现内存是一个单子(monad)吗？

Question

我试图解决Project Euler's Problem 14 (涉及 Collat​​z 序列的长度)使用内存，这就是我为保留先前计算的结果所做的方法。我有这个功能，collatzSequence ，我想记住它，我用 computeWithMemo 记住它，它接受一个函数，一个计算函数的值，一个 Map , 并返回该点的函数值和更新的 Map .这就是 Monad 模式吗？谢谢!

import Data.Map                                                                   

computeWithMemo :: (Int -> Int) -> Int -> Map Int Int -> (Maybe Int, (Map Int Int)
computeWithMemo fun key memo                                                      
  | elem key (Data.Map.keys memo) = (Data.Map.lookup key memo, memo)              
  | otherwise = (Just (fun key), Data.Map.insert key (fun key) memo)              

collatzSequence :: Int -> Int                                                     
collatzSequence x                                                                 
  | x == 1 = 1                                                                    
  | even x = 1 + collatzSequence (x `div` 2)                                      
  | odd x = 1 + collatzSequence (x*3 + 1)                                         

memoize f = computeWithMemo f                                                     

memoizedCollatz = memoize collatzSequence                                         

solve x m                                                                         
  | x > 1 = solve (x-1) (snd (computeWithMemo (collatzSequence) x m))             
  | otherwise = m                                                                 

solution = solve 10000 Data.Map.empty                                             

Answer 1

这是对 State 的部分内部结构的临时重新实现。 monad 在某种意义上创建和执行以模拟状态的方式获取和返回附加参数的函数。

您的代码和 State 之间的主要区别是:

您在 solve 中硬编码为某种类型的函数传递状态的逻辑。方法。
State提供函数>>= (bind)，它定义了如何组合两个有状态函数，或者如何从另一个函数调用一个有状态函数(所有 monad 都需要这样做)。

你硬编码从一个无状态函数创建一个有状态函数的过程，并返回一个 Int .
State提供函数return可用于使任何无状态函数有状态(所有 monad 都需要这样做)。

您可以对状态执行的操作进行硬编码，特别是在 Map Int Int 中内存函数.
State为 get 提供一些功能, set 和 modify 与 >>= 一起的状态可用于创建以各种方式有状态的函数(这是特定于 State 的，而不是一般的 monads)。

所以，是的，你基本上已经定义了一个特定单子(monad)的非常、非常具体和狭窄的情况!

如果你想正式使它成为一个真正的 monad，你可以定义类似于 >>=和 return ，甚至可能实现 Monad typeclass 以便您可以在它们上使用 Haskell 的组合器和语法糖。