1

Possible Duplicate:
Iterating through a String and replacing single chars with substrings in haskell

I'm trying to implement a function that looks at a String ([Chars]) and checks for every letter whether this letter should be replaced with another string. For example we might have a [Chars] consisting of "XYF" and rules that says "X = HYHY", "Y = OO", then our output should become "HYHYOOF".

I want to use the following two types which I have defined:

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

My idea is that the function should look something like the following below using guards. The problem is however I can't find any information on how to the recursive call should look like when i want browse through all my rules to see if any of them fits to the current letter x. I hope anyone can give some hints on how the notation goes.

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  =
Improve this question
0

3 Answers 3

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

i thought the helper function was not needed as you could just check whehther x was equal to t ( in my example ), but i see where your method is going. thanks for input.
The problem is that you have two lists to traverse, the list of letters, and the rules. Doing that in the same function is not nice, since you need to reinstate the full set of rules for the next letter, you'd need three arguments. Separating the two traversals gives shorter, easier to understand and maintain code.
2

I'd suggest that you learn to do this with generic utility functions. Two key functions that you want here:

  1. lookup :: Eq a => a -> [(a, b)] -> Maybe b. Finds a mapping in an association list—a list of pairs used to represent a map or dictionary.
  2. concatMap :: (a -> [b]) -> [a] -> [b]. This is similar to map, but the function mapped over the list returns a list, and the results are concatenated (concatMap = concat . map).

To use lookup you need to change your Rule type to this more generic synonym:

type Rule = (Char, String)

Remember also that String is a synonym for [Char]. This means that concatMap, when applied to String, replaces each character with a string. Now your example can be written this way (I've changed argument orders):

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"

I changed the argument order of apply because when an argument has the same type as the result, it often helps to make that argument the last one (makes it easier to chain functions).

We can go further and turn this into a one-liner by using the utility function fromMaybe :: a -> Maybe a -> a from the Data.Maybe module (fromMaybe default Nothing = default, fromMaybe default (Just x) = x):

import Data.Maybe

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

An exercise you can do to complement this is to write your version of all of these utility functions on your own by hand: lookup, concatMap (break it down into concat :: [[a]] -> [a] and map :: (a -> b) -> [a] -> [b]), and fromMaybe. That way you can understand the "full stack" involved in this solution.

Improve this answer

Comments

1

My solution is structurally similar to the other ones, but uses monads:

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]

The first monad we're dealing with is Maybe a. It is actually a little bit more, a MonadPlus, which allows us to use msum (which boils down something like [Nothing, Just 2, Nothing, Just 3] to the first "hit", here Just 2).

The second monad is [a], which allows us to use a list comprehension in apply.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.