CODEWITHSUNDEEP
haskell
jyet
jyet

Reputation: 845

How to reverse characters in a string keeping digits at the original index?

I have recently started learning Haskell. I am trying to reverse a string which contains chars and numbers. The string is to be reversed keeping digits at the original place.

Original String = "H1AW2J1"

Reversed = J1WA2H1

I am trying to follow the pattern which I used in Swift.

  1. filter digits and then reverse the string.
  2. find the index of digits in the original string.
  3. insert the digits at index obtained from step 2 into the string from step 1.

Below are the codes following above steps.

reversedChars "H1AW2J1" retuns "JWAH"

reversedChars  = reverse . filter isLetter

Indexes returns tuples.

indexes xs = [(x, elemIndex x xs) | x <- xs]

[('H',Just 0),('1',Just 1),('A',Just 2),('W',Just 3),('2',Just 4),('J',Just 5),('1',Just 1)]

Questions

  1. How to insert digits at the repective index into reversedChars
  2. elemIndex is returning same index Just 1 for multiple occurrence of 1.

Upvotes: 3

Views: 820

Answers (3)

Sridhar Ratnakumar
Sridhar Ratnakumar

Reputation: 85442

A different approach does away with having to find the indices of individual elements:

reverseIf :: (a -> Bool) -> [a] -> [a]
reverseIf f = fill <*> reverse . filter f
  where fill s []     = s
        fill (s:ss) (r:rs)
          | f s       = x : fill ss rs
          | otherwise = s : fill ss (r:rs)

Here is another version:

reverseIf :: (a -> Bool) -> [a] -> [a]
reverseIf f = snd . (flip (mapAccumL g) <*> reverse . filter f)
  where g r e | f e       = (tail r, head r)
              | otherwise = (r, e)

Invocation:

> reverseIf (not . isDigit) "H1AW2J1"
"J1WA2H1"

Upvotes: 0

Dogbert
Dogbert

Reputation: 222278

  1. How to insert digits at the repective index into reversedChars

I would use a recursive function like this, which inserts the next reversed char if it encounters a letter, otherwise just inserts the actual character:

import Data.Char

reverseLetters :: String -> String
reverseLetters xs = go xs (reverse $ filter isLetter $ xs)
  where
    go xs [] = xs
    go (x:xs) (r:rs) | isLetter x = r : go xs rs
                     | otherwise  = x : go xs (r:rs)

main = print $ reverseLetters "H1AW2J1"

Output:

"J1WA2H1"
  1. elemIndex is returning same index Just 1 for multiple occurrence of 1.

That's because that is what elemIndex is defined to return. If you want all indices, you can do:

Prelude> map fst $ filter ((== '1') . snd) $ zip [0..] "H1AW2J1"
[1,6]

Upvotes: 5

Julia Path
Julia Path

Reputation: 2366

My solution would also look similar to @Dogbert's however here is one that implements it the way you approached the problem.

There is no update function for lists in the standard library and even if there was, it would not be a good idea to use it, as it would have O(n) where n is the index, because lists are singly linked lists. Instead you have to write your own function to include the numbers back into the string:

reverseChars :: [Char] -> [Char]
reverseChars cs = insert reversedChars digits
  where reversedChars = reverse $ filter isLetter cs
        digits = filter (\(_,c) -> isDigit c) $ indexes cs

insert :: [a] -> [(Int, a)] -> [a]
insert = go 0
  where go i (x:xs) ((j,y):ys)
          | j > i = x : go (i+1) xs ((j,y):ys)
          | otherwise = y : go (i+1) (x:xs) ys
        go _ xs [] = xs
        go _ [] ys = map snd ys

indexes :: [a] -> [(Int, a)]
indexes = zip [0..]

I have also changed the implementation of indexes, because elemIndex also has complexity O(n) with n being the position of the searched-for element in the list, so your indexes function would have O(n²). Furthermore with this implementation you get rid of the Maybe in indexes.

Upvotes: 2

Related Questions