Replacing a character in a string with a string in Haskell in point-free style

Question

The idea is to write a function replace that takes three arguments, a wildcard, a substitution string, and an input string. An example would look like replace '*' "foo" "foo*" = "foobar". Normally this wouldn't be too much of an issue, I'd just write something recursive and check if each character in the string equals my wildcard character. However, I need to write it in point-free style. I have no idea how to do this. I know I can drop the very last argument, the input string, but after that I'm stuck.

My non-point-free style solution is: replace wildcard sub = concatMap (\c -> if c==wildcard then sub else [c]) .

Note: We are not allowed to import external libaries, i.e. no Text.Replace.

Answer 1

Clearly, writing point-free just for the sake of being point-free is stupid.

The reason why it's useful to consider point-free style is that it leads, if done properly, towards a more category-compositional way of thinking. So if we want to give a useful answer to such a task, this is what we should keep in mind.

concatMap is a nice hook into a category, because it's just >>= in the list monad. IOW, it lifts a list-Kleisli-arrow A->[B] into a list-to-list function [A]->[B]. So let's focus on how to write

useChar :: Char -> [Char]
useChar = \c -> if c==wildcard then sub else [c]

as an arrow. I'll actually write it as a function, but you could also go into the Kleisli category instead.

First thing to note is that you're copying c. That's in general done with the fanout operator

(&&&) :: Arrow (~>)
   => (b~>x) -> (b~>y) -> (b~>(x,y))

so

import Control.Arrow
sub = "SUBST"
useChar = (==wildcard)&&&(:[])
       >>> \(decision, embd) -> if decision then sub else embd

Note, (:[]) is the identity Kleisli arrow for the list monad; I'm not going to exploit that though.

Now, the if decision works on booleans, but booleans are ugly. Categorically speaking, a boolean is just a sum type of two unit types

 Bool ≈ Either () () ≡ (()+())
(≡≡) :: Eq a => a -> a -> Either () ()
x ≡≡ y
 | x==y       = Right ()
 | otherwise  = Left ()

We could as well encode some useful information into either of those () options, and specifically for the Right option that's clearly just the constant sub.

constRight :: c -> Bool -> Either () c
constRight _ False = Left ()
constRight c True = Right c

useChar = ((==wildcard)>>>constRight sub) &&& (:[])
       >>> \(decision, embd) -> case decision of
              Left () -> embd
              Right theSub -> theSub

or in a more general view

substRight :: c -> Either a b -> Either a c
substRight _ (Left a) = Left a
substRight c (Right _) = Right c

useChar = ((≡≡wildcard)>>>substRight sub) &&& (:[])
       >>> \(decision, embd) -> case decision of
              Left () -> embd
              Right theSub -> theSub

Obviously we can substitute on the left as well as a generic operator

useChar = ((≡≡wildcard)>>>substRight sub) &&& (:[])
       >>> \(decision, embd) -> substLeft embd decision

Now if we turn the tuple around the lambda is adapting to the curryed form of substLeft:

useChar = (:[]) &&& ((≡≡wildcard)>>>substRight sub) >>> uncurry substLeft