1

可能重复：
遍历字符串并用haskell中的子字符串替换单个字符

我正在尝试实现一个查看字符串（[Chars]）并检查每个字母是否应该用另一个字符串替换的函数。例如，我们可能有一个由“XYF”和“X = HYHY”、“Y = OO”的规则组成的 [Chars]，那么我们的输出应该变成“HYHYOOF”。

我想使用我定义的以下两种类型：

type Letters = [Char]
data Rule = Rule Char Letters deriving Show

我的想法是，使用警卫的函数应该如下所示。但是问题是，当我想浏览我的所有规则以查看它们中的任何一个是否适合当前字母 x 时，我找不到任何关于递归调用应该是什么样子的信息。我希望任何人都可以就符号的运行方式提供一些提示。

apply :: Letters -> [Rule] -> Letters
apply _ _ = []
apply (x:xs) (Rule t r:rs)  
| x /= t = apply x (Rule t rs)
| x == t = r++rs:x
| otherwise  =
4

3 回答 3

5

I would suggest a helper function to check whether a rule matches,

matches :: Char -> Rule -> Bool
matches c (Rule x _) = c == x

and then you check for each character whether there are any matching rules

apply :: Letters -> [Rule] -> Letters
apply [] _ = []
apply s [] = s
apply (c:cs) rules = case filter (matches c) rules of
                       [] -> c : apply cs rules
                       (Rule _ rs : _) -> rs ++ apply cs rules

If you try an explicit recursion on rules within apply, it will become too ugly, since you need to remember the full rules list for replacing later characters.

于 2012-10-19T13:10:01.493 回答
2

我建议您学习使用通用实用程序函数来做到这一点。您在此处需要的两个关键功能：

  1. lookup :: Eq a => a -> [(a, b)] -> Maybe b. 在关联列表中查找映射 - 用于表示映射或字典的对列表。
  2. concatMap :: (a -> [b]) -> [a] -> [b]. 这类似于map，但映射到列表上的函数返回一个列表，结果是连接的 ( concatMap = concat . map)。

要使用lookup，您需要将Rule类型更改为这个更通用的同义词：

type Rule = (Char, String)

还要记住，这String是 的同义词[Char]。这意味着concatMap，当应用于 时String，将每个字符替换为字符串。现在你的例子可以这样写（我改变了参数顺序）：

apply :: [Rule] -> String -> String
apply rules = concatMap (applyChar rules) 

-- | Apply the first matching rule to the character.
applyChar :: [Rule] -> Char -> String
applyChar rules c = case lookup c rules of
                      Nothing -> [c]
                      Just str -> str

-- EXAMPLE
rules = [ ('X', "HYHY")
        , ('Y', "OO") ]

example = apply rules "XYF"  -- evaluates to "HYHYOOF"

我更改了参数顺序，apply因为当参数与结果具有相同类型时，通常有助于将该参数设置为最后一个参数（使链接函数更容易）。

fromMaybe :: a -> Maybe a -> a我们可以更进一步，通过使用Data.Maybe模块中的实用函数（fromMaybe default Nothing= default，fromMaybe default (Just x)= ）将其变成单线x：

import Data.Maybe

apply rules = concatMap (\c -> fromMaybe [c] $ lookup c rules)

您可以做一个补充练习，即自己手动编写所有这些实用函数的版本：lookup、concatMap（将其分解为concat :: [[a]] -> [a]和map :: (a -> b) -> [a] -> [b]）和fromMaybe。这样您就可以理解此解决方案中涉及的“全栈”。

于 2012-10-19T18:44:34.530 回答
1

我的解决方案在结构上与其他解决方案相似，但使用了 monad：

import Control.Monad 
import Data.Functor 
import Data.Maybe 

match :: Char -> Rule -> Maybe Letters
match c (Rule c' cs) = cs <$ guard (c == c')

apply :: Letters -> [Rule] -> Letters
apply cs rules = 
  [s | c <- cs
     , s <- fromMaybe [c] $ msum $ map (match c) rules]

我们处理的第一个 monad 是Maybe a. 它实际上有点多， a MonadPlus，它允许我们使用msum（归结[Nothing, Just 2, Nothing, Just 3]为第一个“命中”，here Just 2）。

第二个 monad 是[a]，它允许我们在apply.

于 2012-10-19T22:15:00.337 回答