如何将 (Either String (a -> b)) 映射到 (Either String [(a -> b)])

Question

我尝试通过自己的练习找到解决方案，并满足以下要求：

我们需要根据给定序列移动对象。
序列由动作组成。

以下是可能的操作：F、L、R

F : 前进
L : 向左旋转90°
R : 向右旋转90°

然后用字符串表示一个序列，像这样：

"FFLRLFF"

我想解析上面的序列（并处理错误），然后将每个动作绑定到一个函数，如下所示：

parseAction :: Char -> Either String (a -> a)
parseAction 'F' = Right moveForward
parseAction 'L' = Right turnLeft
parseAction 'R' = Right turnRight
parseAction s   = Left ("Unkown action : " ++ [s])

-- Implementation omitted
moveForward :: a -> a
turnLeft :: a -> a
turnRight :: a -> a

现在我想要的是具有以下签名的东西：

parseSequence :: String -> Either String [(a -> a)]

我想通过多次使用 parseAction 函数来解析一个完整的序列，但是当那个 returns 离开时失败了。我一直在思考如何实现这个功能。

你有什么想法吗？

Answer 1

这看起来像

mapM :: Monad m => (a -> m b) -> [a] -> m [b]

其中

a ~ Char
b ~ (a -> a)
m ~ (Either String)

所以一个实现很简单：

parseSequence :: String -> Either String [a -> a]
parseSequence = mapM parseAction

顺便说一句，请注意您的 parseAction 并不是真的想使用 (a -> a) 类型，它必须适用于 any 类型 a，由调用函数的人选择。您反而希望它使用 (Location -> Location) 类型，其中 Location 是您用来表示您正在移动的对象的位置的任何类型。

等同于mapM，你可以（如duplode所建议的那样）改用traverse，它更通用一些。在最新版本的 GHC 中，遍历是在 Prelude 中；在旧版本中，您可能必须从 Data.Traversable 导入它才能使用它。

Answer 2

如果您将 parseAction 映射到您的源字符串上，您将参与其中。在 GHCi 中：

> :type map parseAction "FFRRF"
[Either String (a->a)]

所以现在你可以把它折叠成一个 Either 值

validActions = foldr f (Right [])
   where
      f (Left str) _ = Left str
      f (Right x) (Right xs) = Right (x:xs)
      f (Right x) (Left str) = error "Can't happen"

然而，这有一个恼人的 "error" 案例。所以要摆脱它：

import Data.Either

validActions vs = if null ls then Right rs else Left $ head ls
   where (ls, rs) = partitionEithers vs

Answer 3

注意：为了更加清楚，我将使用 Thing -> Thing 而不是 a -> a。

你需要traverse:

traverse parseAction
  :: Traversable t => t Char -> Either String (t (Thing -> Thing))

在您的例子中，t 是 []，因此，t Char 是 String。 traverse parseAction 将走过 String，为每个 Char 生成一个动作并收集结果。 traverse 使用 Either 的 Applicative 实例来处理 Lefts 和 Rights，在第一个 Left.

处停止

P.S.: mapM 在 amalloy 的回答中，在这种情况下，相当于 traverse。它们之间的唯一区别是 traverse 更通用，因为它只需要您在遍历时使用的仿函数的 Applicative（而不是 Monad）。

如何将 (Either String (a -> b)) 映射到 (Either String [(a -> b)])

How to map (Either String (a -> b)) to (Either String [(a -> b)])

haskell

monads

either