Approach to string split by character in Haskell

Question

I'm trying to learn Haskell and the mindset of programming functionally. I have started off by trying to understand the basics by writing code without any Monads in it.

So far, I think I'm getting used to the type system and how the basics works.

I thought to myself, why not try to get some feedback on what I have written to learn even more. So hopefully I will get some valuable information!

I have written a function which iterates a String and splits it into [String] by using given Char as a delimiter. Similar to what PHP's explode and Python's split does.

Here's what I have got so far:

main :: IO()
main = do
    print $ groupBy "/hejsan/asdas" '/' []
    print $ groupBy "/hejsan/asdas/hoho" '/' []
    print $ groupBy "/hejsan/asdas/hahsdhashdas" '/' [] 
    print $ groupBy "/hejsan/99/hahsdhashdas" '/' [] 
    print $ groupBy "/123/asdas/hahsdhashdas///" '/' [] 
    print $ groupBy "/123/asdas/hahsdhashdas//20////hej" '/' [] 

groupBy :: String -> Char -> [String] -> [String]
groupBy "" _ [] = []
groupBy (x:xs) c [] 
    | x == c = groupBy xs c []
    | otherwise = groupBy xs c [[x]]
groupBy "" _ (r:rs) = reverse result
    where result = if r == "" then rs else [r] ++ rs
groupBy (x:xs) c (r:rs)
    | x == c = groupBy xs c $ nextGroup ++ rs
    | otherwise = groupBy xs c $ [r ++ [x]] ++ rs
    where nextGroup = if r == "" then [r] else [""] ++ [r]

With output:

["hejsan","asdas"]
["hejsan","asdas","hoho"]
["hejsan","asdas","hahsdhashdas"]
["hejsan","99","hahsdhashdas"]
["123","asdas","hahsdhashdas"]
["123","asdas","hahsdhashdas","20","hej"]

So the main idea is to only show groups which have values in them. I bet there is:

• Some library function which can simplify the functions internals
• Some way to eliminate the 3rd argument so that it will be transparent to the user (Currying?)

I welcome all types of feedback except for feedback like "there is a library function which does all that for you". I'd like feedback on the internals and this particular problem is just an example

Answer 1

Well, sorry, but it is really tempting to note that there is in fact a library routine that can do that, and it is even called the same as your function:

groupBy (\a b -> b /= '/') "/hejsan/asdas"

This code with groupBy from Data.List will give you ["/hejsan","/asdas"]. Even though it should probably be noted that this is taking advantage of how groupBy is implemented internally, which might not be the best idea.

But let's look at your implementation - two things jump out:

• You are clearly using the first element in the rs list differently from the rest. Why not make it an additional parameter so you can skip de- and recomposing the list all the time?

• Why do you even need an accumulation parameter for your groups? Once you append something to rs, you already know that it will be reversed in the end and end up at the start of the return value. So you can simply prepend the group to the result of the recursive function call.

With the two changes and a bit of refactoring (replacing your if by pattern matches), we get the following version:

groupBy :: String -> Char -> String -> [String]
groupBy ""     _ "" = []
groupBy ""     _ r  = [r]
groupBy (x:xs) c ""
    | x == c        = groupBy xs c ""
    | otherwise     = groupBy xs c [x]
groupBy (x:xs) c r
    | x == c        = r : groupBy xs c ""
    | otherwise     = groupBy xs c (r ++ [x])

This can be improved further:

• This has clearly two modes of operation depending on r == "". When calling you always know whether that is the case, so you could easily split it into two functions. One of them can get rid of the r parameter completely, so you end up with a nice function to call from outside.

• Building a list using ++ is inefficient, as it creates a copy of the list each time you append an element, leading O(n²) complexity. It's better to use x:r and then reverse once in the end, which is a more efficient O(n). A bit more involved refactoring enables you to construct the string in the right form right away (see span).

That's really all the difference to the "perfect" library-level implementation (see the library code). Note that generally, initialization of accumulation parameters is simply done by defining a wrapper function, even though we can easily put this function without even needing it.

Hope this helps.

Answer 2

Another version, using the Prelude function break.

groupBy :: String -> Char -> [String]
groupBy str delim = let (start, end) = break (== delim) str
                    in start : if null end then [] else groupBy (tail end) delim  

Answer 3

OP asked specifically about eliminating the third argument so that it will be transparent to the user. In general, the easy way to do this is to have one function that fronts for another. There is no rule that says that the starting call of a recursive function has to have all the options that the nested calls have. Similarly, there's no rule that says that the recursion has to produce the result in its final form. So, a shell function to do pre- and post- processing around a recursion seems reasonable.

So even the original function implementation could be hidden inside a simple wrapper:

simpleGroupBy :: String -> Char -> [String]
simpleGroupBy s c = groupBy s c []

For cleanliness, you could probably rename simpleGroupBy to groupBy, rename groupBy to groupBy' and hide this groupBy' in a where clause under the new groupBy. This nesting allows the constant c to be pulled out of the recursive argument list, to be referenced in place at the outer function's scope.

Here's an alternative implementation that does all that and also uses foldr to shift the focus from the recursion to what happens at each step of the recursion. The implementation borrows from the cleanup suggested by @Peter

groupBy :: String -> Char -> [String]
-- Work backards through the string, starting with an empty result list 
-- and no pending element.
groupBy s c = let (res,elem) = foldr step ([],[]) s
              -- The final result should include the leading chars, 
              -- if any.
              in  if elem == [] 
                  then res
                  else elem:res
    where 
        step x accum@(result,[]) - No element is in progress.
            -- With no element in progress, x is the end of a new
            -- one, or ignored if it's c.
            | x == c    = accum -- final or repeated c has no effect
            | otherwise = (result,[x]) -- x ends the element
        step x       (result,element) -- An element is in progress.
            -- x is the head (so far) of an element in progress,
            -- except if c, in which case the element is the head
            -- (so far) of the result list and the element is 
            -- considered empty.
            | x == c    = (element:result,[]) -- include the element in the result
            | otherwise = (        result,x:element) -- include x in the element

Answer 4

If someone tells you not to write such a function because it already exists, then you should ignore it and go ahead and write it. It's a great exercise.

That said, after you've written your version, it's a good idea to look up the libraries and see its source code for comparison. You'll probably find very good code there, since it has been reviewed and tested by many people.

In fact you can learn stuff from the documentation alone. For instance, you mention Python's split. I don't know Python well, but I checked its documentation and it defines the function in a different way. Splitting "/abc/def//g" with '/' would give ["", "abc", "def", "", g]. That's different from your examples, but it makes more sense for CSV files, for instance, where 2 consecutive delimiters indicate an empty field. Maybe you want Python's split's definition, or maybe you really want a function that produces your examples, but in this case you'd need a more precise specification.

Another example: in Haskell, you'll see that a function like yours would likely have the arguments reversed:

groupBy' delim str = foo

because this allows you to easily write (groupBy' '/'), which is often more useful than (groupBy' "my string").

I don't know of any function in the standard libraries that does exactly what you want. In your specification, Data.List.groupBy doesn't work. But even if you don't mind not discarding the delimiters, using groupBy for that is just wrong (groupBy expects a function that's like equality: transitive and reflexive).

However, your function looks very similar to words from the Prelude. So you could write a wordsBy function that is like words that, instead of using spaces as delimiters, takes a function argument that determines the delimiters.

I got this by modifying the library code:

wordsBy :: (Char -> Bool) -> String -> [String]
wordsBy isDelim xs =               
  case dropWhile isDelim xs of
    ""  -> []
    xs' -> w : wordsBy isDelim rest
          where (w, rest) = break isDelim xs'
-- note that xs' starts with a non-delimiter, and w is completely
-- non-delimiters.

yourGroupBy c = wordsByDelim (== c)

It's similar to Landei's version. I believe Landei's version is like Python's split. This one is a bit longer but gives the results you want.

So, maybe not what you expected, but I hope it helps. ;-)