Haskell - Couldn't match type `[Char]' with `Char'

Question

I currently have the following code in Haskell

splitStringOnDelimeter :: String -> Char -> [String]

splitStringOnDelimeter "" delimeter = return [""]

splitStringOnDelimeter string delimeter = do
    let split = splitStringOnDelimeter (tail string) delimeter
    if head string == delimeter
    then return ([""] ++ split)
    else return ( [( [(head string)] ++ (head split) )] ++ (tail split))

If I run it in a Haskell terminal (i.e. https://www.tryhaskell.org) with values for the return statement such as ( [( [(head "ZZZZ")] ++ (head ["first", "second", "third"]) )] ++ (tail ["first", "second", "third"])) or [""] ++ ["first", "second", "third"] or [""] then I receive the correct types from the terminal which is different to my local stack compiler. Furthermore, if I also change the top return statement to return "" then it doesn't complain about that statement which I'm pretty sure is incorrect.

My local compiler works fine with the rest of my Haskell codebase which is why I think it might be something wrong with my code...

Answer 1

One of the unfortunate things in the design of the Monad typeclass, is that they introduced a function called return. But although in many imperative programming languages return is a keyword to return content, in Haskell return has a totally different meaning, it does not really return something.

You can solve the problem by dropping the return:

splitStringOnDelimeter :: String -> Char -> [String]
splitStringOnDelimeter "" delimeter = [""]
splitStringOnDelimeter string delimeter =
    let split = splitStringOnDelimeter (tail string) delimeter in
    if head string == delimeter
    then ([""] ++ split)
    else ( [( [(head string)] ++ (head split) )] ++ (tail split))

The return :: Monad m => a -> m a is used to wrap a value (of type a) in a monad. Since here your signature hints about a list, Haskell will assume that you look for the list monad. So that means that you return would wrap [""] into another list, so implicitly with return [""] you would have written (in this context), [[""]], and this of course does not match with [String].

The same goes for do, again you them make a monadic function, but here your function has not much to do with monads.

Note that the name return is not per se bad, but since nearly all imperative languages attach an (almost) equivalent meaning to it, most people assume that it works the same way in functional languages, but it does not.

Mind that you use functions like head, tail, etc. These are usually seen as anti-patterns: you can use pattern matching instead. We can rewrite this to:

splitStringOnDelimeter :: String -> Char -> [String]
splitStringOnDelimeter "" delimeter = [""]
splitStringOnDelimeter (h:t) delimeter | h == delimeter = "" : split
                                       | otherwise = (h : sh) : st
    where split@(sh:st) = splitStringOnDelimeter t delimeter

By using pattern matching, we know for sure that the string has a head h and a tail t, and we can directly use these into the expression. This makes the expression shorter as well as more readable. Although if-then-else clauses are not per se anti-patterns, personally I think guards are syntactically more clean. We thus use a where clause here where we call splitStringOnDelimter t delimeter, and we pattern match this with split (as well as with (sh:st). We know that this will always match, since both the basecase and the inductive case always produce a list with at least one element. This again allows use to write a neat expression where we can use sh and st directly, instead of calling head and tail.

If I test this function locally, I got:

Prelude> splitStringOnDelimeter "foo!bar!!qux" '!'
["foo","bar","","qux"]

As take-away message, I think you better avoid using return, and do, unless you know what this function and keyword (do is a keyword) really mean. In the context of functional programming these have a different meaning.

Answer 2

return has type forall m a. Monad m => a -> m a. The output type of the function splitStringOnDelimiter is [String], so if you try to write some output value using return, the compiler will infer that you want to provide some m a, thus instantiating m to [] (which is indeed an instance of the Monad typeclass), and a to String. It follows that the compiler will now expect some String to be used as argument of return. This expectation is violated in, for example, return ([""] ++ split), because here the argument of return, namely [""] ++ split has type [String] rather than String.

do is used as a convenient notation for monadic code, so you should rely on it only if you are interested in using the monadic operations of the output type. In this case, you really just want to manipulate lists using pure functions.

I'll add my 2 cents and suggest a solution. I used a foldr, that is a simple instance of a recursion scheme. Recursion schemes like foldr capture common patterns of computation; they make recursive definitions clear, easy to reason about, and total by construction.

I also took advantage of the fact that the output list is always non-empty, so I wrote it in the type. By being more precise about my intentions, I now know that split, the result of the recursive call, is a NonEmpty String, so I can use the total functions head and tail (from Data.List.NonEmpty), because a non-empty list has always a head and a tail.

import Data.List.NonEmpty as NE (NonEmpty(..), (<|), head, tail)

splitStringOnDelimeter :: String -> Char -> NonEmpty String
splitStringOnDelimeter string delimiter = foldr f (pure "") string
  where f h split = if h == delimiter 
                      then ("" <| split) 
                      else (h : NE.head split) :| NE.tail split