Geek Answers Handbook

Translation of a simple imperative algorithm into a functional style

Recently, I made a small algorithm to extract function arguments from a piece of code and save only the most external functions. I found that this algorithm is very easy to develop for real. However, I am really interested in functional programming, and I was wondering how you would do the same in a functional way.

It would be very helpful if you could show me how such an algorithm can work, so I could better understand how functional programming works. I would also like to know what your thought process is when developing an algorithm.

I made an imperative version in Python, but your answer does not have to be in python; haskell or any other language will do the same.

Here is what it does (taking the string as input and the return 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 is 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:]
+4
source share
5 answers

Here is 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 filter the list, so it filtercomes to mind; however, regardless of whether we save or drop the character, it depends on some state (our account is open / closed paren). Thus, the monadic filter function filterMis suitable, and we can use the monad Stateto abstract this plumbing from our open / close count.

Let me know if you want more information on how this works.

+6
source

, jberryman, ,

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)

, , , .

-- # 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)

( ), , , .

clean str = stateFilter handleChar str 0

, . , , Haskell , .

+3

, , .

, . , 0 , 1 1 .. n > 0, . / n.

. -, "where".

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
+2

- . , , for , , .

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. Python, Haskell " ", " ".

+1

, , goto +:

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


--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:]

, - . , , ( "" ): , "start" "end", , ")" , ( Python).

There are also some minor style issues, such as using indexing and slicing in linked lists (its O (N) in Haskell instead of O (1)) and using a tail recursive loop (gotos) instead of more structured folds (for loops). However, it’s important that you can still write an original, strong version of the algorithm if you really want to.

0
source

More articles:


All Articles