c++ to functional

I am wondering how to do this in a functional programming language. Maybe f# or haskell. Can someone show me an example without using any function calls except for find and rfind?

This function finds the next slash using i as the num of slash (<0 for backwards).

size_t findSlash(const char *sz, size_t i)
{
    std::string s = sz;
    size_t a, b, c, n, ai = abs(i), pos=0;
    for (n=0; n<ai; n++)
    {
     if (i<0)
     {
      a = s.rfind("\\", pos);
      b = s.rfind("/", pos);
     }
     else
     {
      a = s.find("\\", pos);
      b = s.find("/", pos);
     }
     if (a==-1u)
     {
      if (b==-1u)
       return pos;
      c = b;
     }
     else if (b==-1u)
      c = a;
     else
      c = min(a, b);
     pos = c+1;
    }
    return c;
}

From stackoverflow

• So, uh, what is this? Does it just find the 'i'th slash (forward or backward) in the string (or the '-i'th from the end if i is negative)? I am not sure if I interpreted it right just from reading the code.

  In any case, it would be straightforward to port, but it is not clear what your goal/purpose is.

  acidzombie24 : i mostly only want to see how it would look as its hard for me to wrap my head around

  Brian : Well, the same algorithm would look like pretty much the same code (with slightly different syntax). A different algorithm to give the same results would be easier to read and look different, but that's true regardless of whether written in C++, F#, or Haskell or whatever. What do you want to learn?

• In first, your code is broken. size_t is unsigned type and never can be i<0.

  In second, your code is ugly std library misuse and ineffective. There should be used regular expression library or such or use handcrafted scanner. Resulting code is far cleaner and faster. For example (I have not been using C for many years but below code crafted in 10 minutes works.):

  size_t findSlash(const char *sz, int i)
  {
      const char *s = sz;
      if (i<0) {
          for(;*s;s++);
          for(;;s--){
              if(s<sz) return -1;
              if((*s == '/') || (*s == '\\'))
                  if(! ++i) break;
          }
      }
      else {
          for(;;s++){
              if(! *s) return -1;
              if((*s == '/') || (*s == '\\'))
                  if(! i--) break;
          }
      }
      return s-sz;
  }
  

  I haven't used to write Haskell or F# but for example below code in Erlang should state as example how to do it in functional language:

  findslash(L, I) when is_list(L), is_integer(I) ->
      if  I<0  ->
              case findslash(lists:reverse(L), -1*I - 1, 0) of
                  none -> none;
                  X -> length(L) - X - 1
              end;
          I>=0  -> findslash(L, I, 0)
      end.
  
  findslash([H|_], 0, X) when H=:=$/; H=:=$\\ -> X;
  findslash([H|T], I, X) when H=:=$/; H=:=$\\ ->
      findslash(T, I-1, X+1);
  findslash([_|T], I, X) -> findslash(T, I, X+1);
  findslash([], _, _) -> none.
  

  My attempt in Haskell with error checking and keeps laziness for i>=0:

  findSlash :: String -> Int -> Maybe Int
  findSlash str i
    | i <  0 = reversed (_findSlash (reverse str) (-1*i-1) 0)
    | i >= 0 = _findSlash str i 0
      where
        reversed Nothing  = Nothing
        reversed (Just a) = Just ((length str) - a - 1)
        _findSlash (x:xs) i n
          | x == '/' || x == '\\' = if i==0 then Just n else _findSlash xs (i-1) (n+1)
          | True                  =                          _findSlash xs  i    (n+1)
        _findSlash []     _ _     = Nothing
  

  J.F. Sebastian : Shouldn't it be `if (! --i) break;`?

  Hynek -Pichi- Vychodil : No, it's trick how to return first slash for i=0.

  J.F. Sebastian : the first slash corresponds to `i==1` otherwise you can't find the first slash from the end of a string. See http://stackoverflow.com/questions/548584/c-to-functional/550158#550158

  Hynek -Pichi- Vychodil : Have you tried it? Just try, it works as usual in most of Perl or Python functions of same sort. i==0 is first from start, i==-1 is first from back.

  J.F. Sebastian : You're right. I've confused indexing and counting. It is ubiquitous to use zero-based *indexing* in programming, but we usually use `1` when *counting* something. In this problem interpreting `i` as an *index* rather than *quantity of something* is more appropriate.

• Haskell:

  import Data.List
  
  findSlash :: String -> Int -> Int
  findSlash str i = findIndices (\c -> c == '\\' || c == '/') str !! i
  

  Handling the negative index (which is ugly 'cause you don't really want to do it):

  findSlash :: String -> Int -> Int
  findSlash str i =
      index (findIndices (\c -> c == '\\' || c == '/') str) i
            where index xs i | i  < 0 = (reverse xs) !! ((-i) - 1)
                             | i >= 0 = xs !! i
  

  Handling errors:

  findSlash :: String -> Int -> Maybe Int
  findSlash str i = index i
      where xs = findIndices (\c -> c == '\\' || c == '/') str
            l = length xs
            index i
                | i <  0 && i < (-l) = Nothing
                | i >= 0 && i >= l   = Nothing
                | i <  0             = Just $ (reverse xs) !! ((-i) - 1)
                | i >= 0             = Just $ xs !! i
  

  Now you can say:

  map (findSlash "/foo/bar/baz") [-4..4]
  

  and get:

  -- -4        -3     -2     -1      0      1      2       3       4
  [Nothing,Just 0,Just 4,Just 8,Just 0,Just 4,Just 8,Nothing,Nothing]
  

  Anyway, handling the offset from the end makes the code pretty ugly, and ruins the possibility for lazy evaluation. So I think most people would use the first one, perhaps with a bit of error-checking thrown in. (Which also kills laziness, since length would force evaluation of the whole list. You can use "drop" instead of "!!" to avoid errors AND to prevent evaluation of the entire result list, however. TMTOWTDI.)

  luqui : I am very confused by your definition of "index" in the last variant. The four cases you list are equivalent to: i < 1, i >= 1, i == -1, i == 0. Surely this is not what you intended.

  jrockway : That is the letter L, not a numeric one.

• You can write a pure-functional code in pure C:

  /** Return pointer to the `n`-th occurrence of any char from `chars` in `s`.
  
      Return NULL if it can't find the `n`-th occurrence.  
      Start at the end of `s` if `n` is negative.
      `n` is zero-based.
  */
  const char* 
  find_nth(const char* s, int n, const char* chars) 
  {
    if (n < 0) return rfind_nth(s, -(n+1), chars);
    if (! (s && *s)) return NULL;
    if (find(chars, *s)) return (n == 0) ? s : find_nth(s+1, n-1, chars);
    else return find_nth(s+1, n, chars);
  }
  

  Full program:

  #include <string.h>
  
  const char* 
  find(const char* s, char c) 
  {
    if (! (s && *s)) return NULL;
    return (*s == c) ? s : find(s + 1, c);
  }
  
  const char* 
  rfind_nth_range(const char* s, const char* end, size_t n, const char* chars)
  {
    if (! (s && end && (end - s) > 0)) return NULL;
    if (find(chars, *(end - 1))) // `*(end-1)` is in `chars`
      return (n == 0) ? end - 1 : rfind_nth_range(s, end - 1, n-1, chars);
    else
      return rfind_nth_range(s, end - 1, n, chars);
  }
  
  const char* 
  rfind_nth(const char* s, size_t n, const char* chars)
  {
    return rfind_nth_range(s, s + strlen(s), n, chars);
  }
  
  int 
  main(void) 
  {
    const char* const s = "ab/cd\\e";
    return !(find_nth(s, 1, "/\\") == (s+5));
  }
  

  luqui : That recursion is going to kill you in C.

  J.F. Sebastian : The fact that you *can* do something doesn't tell you that it is a good idea to do it.