Translating a simple imperative algorithm to functional style

Question

I recently made a small algorithm to strip out function arguments from a snippet of code and only keep the outermost functions.
I found that this algorithm was very easy to design in an imperative way.
However, I'm really interested in functional programming and I was wondering how you would accomplish the same thing in a functional way.

It would be very helpful to me if you could show me how such an algorithm might work, so I might get a better idea of how functional programming works. Also I'd like to know what your thought process is while designing the algorithm.

I made the imperative version in Python, but your answer doesn't have to be in python; haskell or any other language will do just as well.

Here's what it does (taking a string as input and returning a string):

"foo(a.d, b.e.fi()).go(sd, ds())"     -- returns -->  "foo().go()"
"foo(a, b).bar().fuu"                 -- returns -->  "foo().bar().fuu"
"foo.bar"                             -- returns -->  "foo.bar"

And here's my imperative code:

def get_rid_of_arguments(text):
    i, start, end = 0, 0, 0
    result = ""
    for j, c in enumerate(text):
        if c == '(':
            if i == 0:
                start = j
                result += text[end:start]
            i += 1
        elif c == ')':
            i -= 1
            if i == 0:
                end = j + 1
                result += '()'
    return result + text[end:]

Answer 1

Here's my version:

import Control.Monad
import Control.Monad.State

-- filter `str` with the "stateful" monadic predicate function `handleChar`, 
-- with an initial state of 0
getRidOfArguments :: String -> String
getRidOfArguments str = filterM handleChar str `evalState` 0

handleChar :: Char -> State Int Bool
handleChar '(' = modify (+1) >> gets (<= 1)
handleChar ')' = modify (max 0 . subtract 1) >> gets (== 0)
handleChar _   = gets (== 0)

My thought process was: we're filtering a list so filter comes to mind; however whether we keep or drop a character depends on some state (our count of open/closed parens). So the monadic filter function filterM is appropriate, and we can use the State monad to abstract that plumbing of our open/close count.

Let me know if you want more details on how the above works.

Answer 2

Alright, I'd prefer jberryman's solution, but if you'd like to avoid a monad, the try this

stateFilter :: (s -> a -> (s, Bool)) -> [a] -> s -> [a]
stateFilter f as state = snd $ foldr stepper (state, []) as
  where stepper (state, filtered) a =
          let (state', b) = f state a in
             if b then (state', a:filtered) else (state', filtered)

This keeps a state running through our filtering function and we just return whether the current value is true and our new state. Then your code is just

-- # Converted from jberrymans lovely answer
handleChar :: Int -> Char -> (Int, Bool)
handleChar s '(' = (max 0 (s - 1), s <= 1)
handleChar s ')' = (s +1, s <= 0)
handleChar s _   = (s, s == 0)

Now the state is explicit (and not as pretty) but perhaps easier to understand.

clean str = stateFilter handleChar str 0

Now this is nice and functional, the whole thing boils down to folding over the string. There's a bit of plumbing going on to track the state but once you start to grok Haskell a bit more this goes away nicely.

Answer 3

Plenty of answers already, but just to add to the list, here's one in very simplistic functional style.

It uses a helper function that takes a nesting count. So, 0 means not inside brackets, 1 means inside 1 pair etc. If n > 0 then we drop characters. If we hit a bracket increment/decrement n accordingly.

The helper function is basically a case-by-case description of that algorithm. If using it for real, you would dangle it off a "where" clause.

skipBrackets :: String -> String
skipBrackets s = skipper s 0

skipper :: String -> Int -> String

skipper [] _ = []
skipper ('(':xs) 0 = '(' : skipper xs 1
skipper (')':xs) 1 = ')' : skipper xs 0

skipper ('(':xs) n = skipper xs (n + 1)
skipper (')':xs) n = skipper xs (n - 1)

skipper (x:xs) 0 = x : skipper xs 0
skipper (x:xs) n = skipper xs n

Answer 4

One way to do it is to convert from iterative to recursive style. In other words, instead of using a for loop to execute some code multiple times, you achieve the same thing by making your function call itself.

An example in Haskell:

get_rid_of_arguments [] = []
get_rid_of_arguments ('(':xs) = "()" ++ (get_rid_of_arguments $ dropper xs)
get_rid_of_arguments (x:xs) = x : get_rid_of_arguments xs

dropper [] = []
dropper (')':xs) = xs
dropper ('(':xs) = dropper $ dropper xs
dropper (_:xs) = dropper xs

main = do
    print $ get_rid_of_arguments "foo(a.d, b.e.fi()).go(sd, ds())" == "foo().go()"
    print $ get_rid_of_arguments "foo(a, b).bar().fuu" == "foo().bar().fuu"
    print $ get_rid_of_arguments "foo.bar" == "foo.bar"

P.S. neither your original python code nor this Haskell code are correct ways to "strip out function arguments from a snippet of code", I'm just answering the "how do I translate this code" question.

Answer 5

One trick that I like when doing this sort of conversin is looking at tail calls as a sort of goto+variable assignment:

sumn n = addn n 0

addn i acc =
   if i == 0 then
      acc
   else
      addn (i-1) (acc + i)

def sumn(n):
  #lets pretend Python has gotos for now...
  i, acc = n, 0
 acc:
  if i == 0:
     return acc
  else:
     i, acc = (i-1), (acc + i)
     goto acc

In your case, this would translate kind of like

--Haskell pseudocode w/ string slicing
get_rid xs = go 0 0 0 0 ""
  where
    -- "go" is a common name for these tail-recursive loop functions.
    go i j start end result =
      if j < length xs then
         case xs !! j of
           '('  -> 
              if i == 0 then
                go (i+1) (j+1) j end (result ++ (text[end:start]))
              else
                go (i+1) (j+1) start end result
           ')' -> 
              if i == 1 then
                go (i-1) (j+1) start (j+1) (result ++ "()")
              else
                go (i-1) (j+1) start end result
           _ ->
              go i (j+1) start end result
      else
         result ++ text[end:]

The end result is super ugly because this is still a fundamentally imperative algorithm with lots of variable assignment going on. Additionally, the functional version makes it explicit that all your variables were in the largest scope available (the "go" loop): I guess you should be able to get rid of "start" and "end" by using an inner loop to find the next ")" instead of doing everything in the main loop (this is also valid for the original Python program).

There are also some minor style issues, like still using indexing and slicing on linked lists (its O(N) in Haskell instead of O(1)) and from using a tail recursive loop (gotos) instead of more structured folds (for loops). That said, the important point is that you can still write the original, imperative, version of the algorithm if you really want to.