Haskell Function

Question

I need to create a function that takes string and decoding rules. It is supposed to change characters in string until there is nothing possible to change according to decoding rules. Each time I get string and decoding rules (first is what change, second is to what).

I'm quite lost, I tried to create all possible combinations and then generate list based on rules. Here's my try.

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]

Error message:

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

Disclaimer: none of this is as pretty as it could be.

You have a lookup table with rules. Haskell has a handy lookup function:

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

We can fold a lookup over the string:

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

Let's call this 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 : ""

But a single pass doesn't necessarily get the job done. We need to recursively call this until there are no transformations left to perform. This means we need to know if any of the characters in the input string are in the lookup table.

The ... is left to fill in with the correct recursive call to avoid presenting a complete answer.

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

The first condition might also be expressed as follows.

any (flip elem $ map fst rules) s