How to re-arrange a list based on a set of steps?

user_9679198 0
Viewed 56

I'm trying to re-arrange a list based on these steps:

  1. First move every operator (+,-,*) 1 index to the left by switching it with the element to the left.
  2. Then find any '+' or '-' two indexes ahead of a *, and move the '+' or '-' to the index before the *.

Example

["a","-","2","*","b","+","c"]

["-","a","*","2","+","b","c"]

["-","a","+","*","2","b","c"]

I have an imperative programming background, so my initial idea was to have an iterator as an argument, and keep track of the position in the index like that, but I could not get it to work. My second idea was to embrace Haskell and use list comprehension with generators, but I struggled there as well. Any ideas or solutions are appreciated!

list haskell
1 Answers

You can make use of explicit recursion. You can for example move elements one position to the left with:

isOperator :: String -> Bool
isOperator "+" = True
isOperator "-" = True
isOperator "*" = True
isOperator _ = False

stepOne :: [String] -> [String]
stepOne (x:xs@(o:xs'))
    | isOperator o = o : x : stepOne xs'
    | otherwise = x : stepOne xs
stepOne xa@[_] = xa
stepOne [] = []

Here the (x:xs@(o:xs')) pattern matches with lists with two or more elements. THe first element is x, the second is o, the remaining elements is stored in the xs' variable. xs is the tail of the "outer" cons. We check if o is an operator, if that is the case we swap with x and recurse on the tail xs'. If o is not an operator, we recurse on the tail xs'.

For the given sample data, we get:

Prelude> stepOne ["a","-","2","*","b","+","c"]
["-","a","*","2","+","b","c"]

I leave step two as an exercise.

That being said, one of the success stories of Haskell is probably parsing. Several libraries and tools exist like parsec [Hackage] and attoparsec [Hackage]. happy [haskell.org] is a compiler compiler that can construct a parser in Haskell based on a grammer. You thus do not per se need to perform infix-to-prefix conversion, but let tools do the work for you.

user_675790
Related