7

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

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

以下是可能的操作：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函数来解析一个完整的序列，并在该函数返回 Left 时失败。我被困在如何实现这个功能上。

你有什么想法 ？

4

3 回答 3

11

这看起来像

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并不是真的想使用 type (a -> a)，它必须适用于任何type a，由调用函数的人选择。相反，您希望它使用 type (Location -> Location)，其中 Location 是您用来表示您正在移动的对象的位置的任何类型。

等效于 mapM，您可以（如 duplode 所建议的那样）改为使用 traverse，这稍微更通用。在最近版本的 GHC 中，traverse 在 Prelude 中；在旧版本中，您可能必须从 Data.Traversable 导入它才能使用它。

于 2015-09-11T19:57:40.583 回答
7

注意：为了更加清楚，我将使用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使用 的Applicative实例Either来处理Lefts 和Rights，在第一个Left.

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

于 2015-09-11T20:05:53.463 回答
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"

然而，这有一个烦人的“错误”案例。所以要摆脱它：

import Data.Either

validActions vs = if null ls then Right rs else Left $ head ls
   where (ls, rs) = partitionEithers vs
于 2015-09-11T20:00:04.430 回答