何时使用Haskell monads

2 回答

• 7

  在Haskell中表达这种迭代过程的最佳方法是作为每个连续结果的无限列表 . 将您的四个步骤拼凑在一起会产生从解决方案到不同（更好）解决方案的功能概念;你需要做的就是无限次地应用这个 . 然后，您的函数的用户可以使用任何列表函数来获得答案： solve s0 !! numIterations ，或 find stoppingCondition $ solve s0 ，或任何您想要的 .

  为了到达这里，让我们写出每个函数的类型 .

  • moves :: Solution -> [Move]
    给出可能的解决方案，找出可能做出的改变 .

  • value :: Solution -> Move -> Double
    给定解决方案和移动，对其进行评估并将该值记录为实数 .

  • choose :: Solution -> [Move] -> Move
    给出一个解决方案和一系列动作，选择最好的一个 .

  • apply :: Solution -> Move -> Solution
    如果有移动，请将其应用于现有解决方案以获得新解决方案 .

  你想编写一个像 solve :: Solution -> (Solution -> Bool) -> Solution 这样的类型的函数，它采用初始解决方案和停止条件来执行你的算法 .

  相反，让's make this an infinite list; this means that you' ll只删除谓词并拥有 Solution -> [Solution] .

  import Data.Ord
  import Data.List
  
  -- moves, value, and apply are domain-specific
  choose :: Solution -> [Move] -> Move
  choose s ms = maximumBy (comparing $ value s) ms
  
  solve :: Solution -> [Solution]
  solve = iterate $ \s -> apply s . choose s $ moves s
  

  这里的关键是 iterate :: (a -> a) -> a -> [a] ，它会重复将一个函数应用于一个值，并为您提供结果 - 完全是您算法的描述 .

  但是，我真的写这个的方式如下：

  import Data.Ord
  import Data.List
  
  solve :: Ord o => (s -> [m]) -> (s -> m -> o) -> (s -> m -> s) -> s -> [s]
  solve moves value apply = iterate step
    where step   s = apply s . choose s $ moves s
          choose s = maximumBy (comparing $ value s)
  

  这样做的好处是您可以为任何问题域重用相同的通用结构 . 您需要做的就是提供 moves ， value 和 apply 函数！根据我的心情，我可能会改写：

  import Control.Applicative
  import Data.Ord
  import Data.List
  
  solve :: Ord o => (s -> [m]) -> (s -> m -> o) -> (s -> m -> s) -> s -> [s]
  solve moves value apply = iterate step
    where step   = (.) <$> apply <*> choose <*> moves
          choose = maximumBy . comparing . value
  

  在这里，我们使用applicative notation来说我们实际上只是在一个上下文中执行 (.) apply choose moves （这只是 apply . choose $ moves ），其中每个函数都隐式传递一个参数 s （读者应用程序） . 如果我们真的想要改变事物，我们可以写

  import Control.Applicative
  import Data.Ord
  import Data.List
  
  solve :: Ord o => (s -> [m]) -> (s -> m -> o) -> (s -> m -> s) -> s -> [s]
  solve moves value apply =
    iterate $ (.) <$> apply <*> maximumBy . comparing . value <*> moves
  

  任何这些片段都可以完全满足您的需求 . （Proviso：你的任何一个函数都没有效果/ monad，所以随机性就出来了 . 不过，你很容易使这个monadic . ）

  ---

  但是，只是为了踢，让我们考虑 State monad . 这表示使用某种环境进行计算，因此 State s a 与 s -> (a,s) -something同构，可以查看状态并可能更新它 . 在这里，函数签名左侧的所有 Solution -> 将会消失，右边的 -> Solution 也会消失 . 这会让你失望

  • moves :: State Solution [Move]

  • value :: Move -> State Solution Double

  • choose :: [Move] -> State Solution Move

  • apply :: Move -> State Solution ()

  这意味着你会有一些monadic动作 step ：

  import Control.Applicative
  import Control.Monad.State
  import Data.Ord
  import Data.List
  
  choose :: [Move] -> State Solution Move
  choose = let val m = do v <- value m
                          return (m,v)
           in fst . maximumBy (comparing snd) <$> mapM val ms
  
  step :: State Solution ()
  step = apply =<< choose =<< moves
  

  你可以让它更加无点，或者像上面那样使它变成多态，但我不会在这里做到这一点 . 关键是，一旦你有 step ，就可以用 runState . last $ replicateM_ numIterations step 生成答案，或者给出一个 whileM 函数， runState $ whileM (stoppingCondition :: State Solution Bool) step . 同样，用户可以决定如何停止它 . 您的 moves 和 value 函数可能会使用 get :: State s s 查询状态; apply 可能会使用 modify :: (s -> s) -> State s () 调整状态而不需要将其拉出来 . 您可以在这些类型中看到与上面结构的相似性;事实上，你可以在 step 的定义中看到那个结构 . 每个人都说“string together apply ， choose / value ， moves ”，这是你的算法的定义 .

  ---

  来自这两者的带回家的消息是你想要避免显式的循环/递归，正如你正确地意识到的那样 . 如果你强行考虑这个算法，那么_1143331_ monad似乎是一个自然结构，因为它隐藏了你正在考虑的那些命令性功能 . 但是，它有缺点：例如，一切都变成了monadic，而且 apply 以外的所有函数中最差的都能够改变保存的解决方案 . 如果你想象这个算法每次产生一个新的结果，你会得到 step :: Solution -> Solution 的概念，并且从那里你可以使用 iterate 获得一个表现良好的无限列表 .

  回复于 2024-04-29T04:37:22+08:00
• 43

  这是一个伪代码草图，说明如何使用State monad通过计算来线程化搜索状态：

  import Control.Monad.State
  
  type SearchState = ...
  type Move = ...
  type Fitness = ...
  
  determineMoves :: State SearchState [Move]
  determineMoves = do
    -- since determineMoves is in the State monad, we can grab the state here
    st <- get
    ...
  
  evaluateMoves :: [Move] -> [(Move, Fitness)]
  evaluateMoves = ...
  
  chooseMove :: [(Move, Fitness)] -> Move
  chooseMove = ...
  
  -- makeMove is not itself monadic, but operates on the SearchState
  -- type we're threading through with the State monad
  makeMove :: Move -> SearchState -> SearchState
  makeMove m st = ...
  
  loop :: State SearchState ()
  loop = do
    moves <- determineMoves
    let candidates = evaluateMoves moves
        move = chooseMove candidates
    -- we pass a function (SearchState -> SearchState) to modify in 
    -- order to update the threaded SearchState
    modify (makeMove move)
    loop
  

  请注意，即使您的主计算处于状态monad，也不是每个组件都必须在monad中 . 这里， evaluateMoves 和 chooseMove 是非monadic，我使用 let 向您展示如何将它们显式集成到 do 块中 . 但是，一旦你对这种风格感到满意，你可能会想要使用 <$> （又名 fmap ）和功能组合来变得更加简洁：

  loop :: State SearchState ()
  loop = do
    move <- (chooseMove . evaluateMoves) <$> determineMoves
    modify (makeMove move)
    loop
  

  回复于 2024-04-29T04:37:22+08:00