string - Haskell 函数

Question

我需要创建一个接受字符串和解码规则的函数。它应该更改字符串中的字符，直到根据解码规则无法更改为止。每次我得到字符串和解码规则(第一个是什么变化，第二个是什么)。

我很迷茫，我尝试创建所有可能的组合，然后根据规则生成列表。这是我的尝试。

rules = [('E',"GZ"),('F',"HK"),('C',"EF"),('J',"CC")]
string = "JCEJ"

combinations = [(x,y,z) | x <- [ch | ch <- string], y <- [x | (x,y) <- rules], z <- [y | (x,y) <- rules]]

generate = [z | (x,y,z) <- combinations, if x == y then z else x]

错误信息:

decoder.hs:8:57: error:
    • Couldn't match expected type ‘Bool’ with actual type ‘[Char]’
    • In the expression: z
      In the expression: if x == y then z else x
      In a stmt of a list comprehension: if x == y then z else x
  |
8 | generate = [z | (x,y,z) <- combinations, if x == y then z else x]
  |                                                         ^

decoder.hs:8:64: error:
    • Couldn't match expected type ‘Bool’ with actual type ‘Char’
    • In the expression: x
      In the expression: if x == y then z else x
      In a stmt of a list comprehension: if x == y then z else x
  |
8 | generate = [z | (x,y,z) <- combinations, if x == y then z else x]
  |                                                                ^

Answer 1

免责声明:这些都没有它应该的那么漂亮。

您有一个包含规则 的查找表。 Haskell 有一个方便的 lookup 函数:

ghci> :t lookup
lookup :: Eq a => a -> [(a, b)] -> Maybe b

我们可以对字符串进行查找:

ghci> foldr (\x i -> case lookup x rules of {Just s -> s ++ i; _ -> (x:i)}) "" "EF"
"GZHK"

让我们称之为singlePassDecode:

singlePassDecode :: Foldable t => t Char -> [(Char, [Char])] -> [Char]
singlePassDecode s rules = foldr update "" s
  where
    update ch acc = 
      case lookup ch rules of
        Just s' -> s' ++ acc
        Nothing -> ch : ""

但一次通过并不一定能完成工作。我们需要递归调用它，直到没有要执行的转换。这意味着我们需要知道输入字符串中的任何字符是否在查找表中。

留下 ... 以填写正确的递归调用，以避免呈现完整的答案。

decode :: [Char] -> [(Char, [Char])] -> [Char]
decode s rules
  | any (\ch -> elem ch (map fst rules)) s = ...
  | otherwise = s

第一个条件也可以表示如下。

any (flip elem $ map fst rules) s