Question

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;
}
Was it helpful?

Solution

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

OTHER TIPS

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

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));
}

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.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top