Haskell + "Remove a parameter"

Question

I have a kind of theoretical question, that a friend and I have been trying to see, how we could do it. We have a function named palindrome, that tell us if a String is a palindrome. Here's how we implemented it (there are probably better ways to do it, but that's how we like it more.)

palindrome :: String -> Bool
palindrome = \x -> (== reverse x) x

What we want to do is to remove the Lambda we're using here and just work with partial application and high order functions. We have had several ideas of how to do this, but none of them matches with the type of function we made:

palindrome :: String -> Bool

One of the closest approaches was using composition, but it returns us a Function, that takes two Strings and not one, since one is for reverse and other for the (==):

palindrome = (==) . reverse

Maybe, we're forgetting something or we're not seeing something. How would you do it in order to use this two functions without using Lambda?

Answer 1

You can use the <*> operator for the (->) instance of Applicative.

palindrome = (==) <*> reverse

The <*> operator is kind of like function application in some context. In this case, that context is "functions taking a String as an argument". So you get a function that takes a String and pass it to two functions that also take Strings and then applies the result of the former to the latter. In other words, f <*> g = \x -> f x (g x).

Answer 2

You've got three answers right now but perhaps not so much understanding.

The problem is that you've got two x's on the right hand side, and it doesn't look like there's a good way to remove one. You need a function with one of the following signatures to "duplicate" that x:

x -> (x, x)
x -> (x -> a, x -> b) -> (a, b)
((x, x) -> y) x -> y
(x -> x -> y) -> x -> y
(x -> y) -> (x -> y -> z) -> (x -> z)

These are actually surprisingly hard to find; I would have imagined that the first of these would be available under the name dup x = (x, x), but it's nowhere to be found. None of these are anywhere to be found in the Prelude, to my knowledge.

It turns out that there's a Monad called the "Reader" monad which threads one value (in this case your x) through many functions. This monad's type is (->) x, meaning that it's the functions x -> y for all y. The second-to-last function above (x -> x -> y) -> x -> y can actually just be written as:

Prelude> :m + Control.Monad
Prelude Control.Monad> :t (id >>=)
(id >>=) :: (a -> a -> b) -> a -> b

You could therefore write just:

id >>= (==) . reverse

or even more concisely:

palindrome = reverse >>= (==)

It turns out that everyone else's version secretly uses (>>=) behind the scenes. It turns out for instance that every Monad is an Applicative and the Control.Applicative library exports a symbol (<*>) :: Applicative f => f (x -> y) -> f x -> f y. In the case of f being (->) a we have: (<*>) :: (a -> x -> y) -> (a -> x) -> y which we can apply to (==) and reverse to get:

palindrome = (==) <*> reverse

Or Control.Monad has the same instance Monad ((->) x) and exports both >>= for it (as above, (x -> y) -> (y -> x -> z) -> x -> z and join :: m (m x) -> m x which in this case is (x -> x -> y) -> x -> y.

There are lots of options, but that instance declaration is made in those libraries. If you wanted to do it without those libraries you'd have to write out the tedious:

instance Monad ((->) x) where
    return = const
    yx >>= zxy = \x -> zxy (yx x) x

before you applied those functions. At that point it's almost easier to write:

Prelude> let dup x = (x, x)
Prelude> let palindrome = uncurry ((==) . reverse) . dup
Prelude> :t palindrome
palindrome :: Eq a => [a] -> Bool

Answer 3

You can use join from Control.Monad

palindrome = join ((==) . reverse)

join is an essential function for monads. However, for this special case, which is functions (or to be more precise, the (->) instance of Monad), join f x just evaluates to f x x.