Haskell + "Delete Parameter"

Question

I have a kind of theoretical question that my friend and I tried to see how we could do this. We have a function called palindrome that tells us that String is a palindrome. Here, how we implemented it (there are probably better ways to do this, but as we like it more.)

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

What we want to do is remove Lambda, which we use here, and just work with a partial application and high-order functions. We had several ideas on how to do this, but not one of them matches the type of function we perform:

 palindrome :: String -> Bool 

One of the closest approaches is to use composition, but it returns a function that takes two lines, not one, because for the opposite and the other for (==):

 palindrome = (==) . reverse 

Perhaps we are forgetting something or not seeing anything. How would you do this to use these two functions without using Lambda?

Answer 1

You have three answers right now, but maybe not much understanding.

The problem is that you have two x on the right side, and it doesn't seem like there is a good way to remove them. To "duplicate" you need a function with one of the following signatures: 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) 

It is actually surprisingly hard to find; I would suggest that the first one would be available under the name dup x = (x, x) , but it could not be found anywhere. As far as I know, not one of them is found anywhere in the prelude.

It turns out that there the Monad is called the "Reader" monad, which imposes a single value (in this case, your x ) on many functions. This type of monad is (->) x , which means that for all y these are functions x -> y . The second-last function above (x -> x -> y) -> x -> y can simply be written as:

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

Therefore, you can write simply:

 id >>= (==) . reverse 

or even more briefly:

 palindrome = reverse >>= (==) 

It turns out that all other versions secretly use (>>=) behind the scenes. It turns out, for example, that each Monad is Applicative , and the Control.Applicative library exports the symbol (<*>) :: Applicative f => f (x -> y) -> fx -> fy . 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 for it as >>= (as indicated above, (x -> y) -> (y -> x -> z) -> x -> z and join :: m (mx) -> mx , which in this case (x -> x -> y) -> x -> y .

There are many options, but the declaration of these instances is done in these libraries. If you want to do this without these libraries, you will have to write a tedious version:

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

before applying these features. At this point, it is 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 2

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

 palindrome = (==) <*> reverse 

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

Answer 3

You can use join from Control.Monad

 palindrome = join ((==) . reverse) 

join is an important function for monads. However, for this special case, which is functions (or, more precisely, an instance of (->) Monad ), join fx simply evaluates fxx .

Answer 4

Several alternatives (although worse than previous answers ;-))

 import Control.Arrow palindrome1 = (reverse &&& id) >>> uncurry (==) palindrome2 = ((==) &&& reverse) >>> uncurry ($) 

Answer 5

Using Control.Applicative

 palindrome = (==) <*> reverse