## Removing Spaces

### February 11, 2020

We have a simple task today, with dozens of potential solutions:

Write a program to remove all spaces from a string.

Your task is to write a program to remove all spaces from a string. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

(defun remove-all-spaces (string) (remove #\space string))

(remove-all-spaces “Hello World !”) ; –> “HelloWorld!”

Nice drill! Although there are more interesting ways of solving this, I’d go with the simplest one, using Julia:

RemoveSpaces(x::String) = join(split(x, ” “))

Fortunately, it doesn’t need any packages either.

sed ‘s/ //g’

Am I cheating?

Klong version

Here’s a solution in Python.

Output:

Haskell one-liner:

Here’s a solution in C.

Example usage:

An even more monadic one-liner:

Or even:

Last one – there is an ‘ifM’ function in Control.Conditional that lifts if’ (the conditional function) into a monad (in this case, the function monad, so ‘ifM f g h’ is ‘if f x then g x else h x’ and I don’t need Control.Applicative any more. The bind, mzero and return are in the list monad (so are concatMap, empty list, and \x->[x] respectively):

@matthew: Can you explain your Haskell programs? Amazing what 1 line can do! Thanks, Steve

@Steve: Here’s an attempt at an explanation (I might post this elsewhere, so grateful for any comments):

In Haskell, a string is just a list of characters, so one way of doing this is to map a function over that list. What should that function be? It can’t just be a map from Char to Char – what would it do for the space character? A possibility, since we are already dealing with lists is to use a function Char->[Char], ie. take a Char and return a list of Chars:

Now let’s start the fooling around.

First of all, let’s go point free. f is just applying two functions (concat and map g) to its argument, so we can rewrite as a composition:

Now, it would be good to get rid of that auxiliary function, one way would be to use a lambda:

or:

Alternatively, we can use an ‘Iverson bracket’ and use the numeric value of the boolean test as a parameter to ‘replicate’, ‘replicate n a’ makes n copies of a, and ‘fromEnum False’ is 0, ‘fromEnum True’ is 1:

and we should recognize that ‘concat . map f’ is just a monadic bind: (>>= f):

Now that lambda is of the form: \c -> (f (g c) c) which is almost the form of the S-combinator:

and if we change the parameter order of replicate we get exactly this form:

Haskell doesn’t have an S combinator as such, but the Applicative operator ‘ap’ is equivalent to S in the function monad, so finally we end up with:

That’s nice, but the use of replicate is a bit obscure, let’s go back to the case form:

or

Being Haskell programmers we can’t help noticing that [] and [c] are both monadic – [] is just ‘monadic zero’ in the list monad, and in the same monad, [c] is ‘return c’, so now we have:

Not much more to be done with the ‘case’ form, but we can make use of the laziness of Haskell to rewrite the ‘if’ form: we can write ‘if’ as a function:

and laziness ensures that only one of y and z get evaluated, so we have:

or:

where const is just the K-combinator:

so what I want is a “functional if”:

and this can be done by “lifting” if’ into the function Monad (though actually, this is an Applicative operation):

or, even better, use the ifM function directly (defined in Control.Conditional):

For a final monadic flourish, we can observe that ‘const’ itself is just ‘return’ in the function monad and we get:

Now f works for other instances of Monad (or rather MonadPlus, since we require mzero), for example Maybe and IO: