6

I have this snippet of code:

palindrome :: String -> Bool
palindrome x = x == reverse x

Is there any way to rewrite this in a point-free style?

stites
  • 4,903
  • 5
  • 32
  • 43
user2852456
  • 129
  • 2

5 Answers5

10

Yes, because any function can be written in point-free style. Here, the Applicative instance for (->) r (aka Reader) does this for you, because

(f <*> g) x = f x (g x)

You may recognize this as the S-combinator from SKI calculus (return is K by the way).

Your Palindrome checker is written as

x == reverse x

which in infix form reads

(==) x (reverse x)

and by comparison with the <*> definition above this leads to the expression

isPalindrome x = ((==) <*> reverse) x

where you can drop the trailing x to get the solution

isPalindrome = (==) <*> reverse

which is probably less readable than the original expression and should not be used for that reason. Point-free style is for readability, and only useful in certian cases.

David
  • 8,275
  • 5
  • 26
  • 36
  • 5
    "which is probably less readable than the original expression and should not be used for that reason" is an interesting remark. There are Pythonistas who would argue that `map` is always less readable than a list comprehension. What's readable really depends on what idioms are popular. A person used to seeing applicative style may read the point-free version as "equality over identity and reversed" or something, which is easy to understand. And popular idioms is something changing with time, so if you want it to change in a particular direction you can help by using the "weird" ones sparingly. – kqr Oct 13 '13 at 20:33
  • 1
    @kqr right, someone used to Applicative (->) uses doesn't have a problem with this code. But note that of the basic Applicatives (->) is pretty high up there in obscurity when you learn about it for the first time; the code here is very simple, but can be written in a way that only intermediate programmers can understand by just reading over it. – David Oct 14 '13 at 09:14
  • @David right, but `<*>` and `join` should be part of [a basic repertoire for point-free style](http://stackoverflow.com/a/11050971/849891) which can be learnt for its own sake (apart from being an Applicative instance). – Will Ness Oct 14 '13 at 09:19
2

You might think this method is cheating:

palindrome :: Eq a => [a] -> Bool
palindrome = palindrome'
  where palindrome' xs = xs == reverse xs

Of course there's also the applicative style that David and freyrs suggested:

palindrome'' :: Eq a => [a] -> Bool
palindrome'' = (==) <*> reverse

But how about this expression as a fold?

palindrome''' :: Eq a => [a] -> Bool
palindrome''' = (foldl (\b (x, y) -> b && x == y) True)
              . (uncurry zip)
              . reverse'
  where reverse' xs = (xs, reverse xs)
Alexander Vieth
  • 876
  • 6
  • 9
  • 1
    Although `reverse'` isn't point-free, so you could say that's just the same as your first one. To make `reverse'` point-free, you would need the applicative version yet again, making it sort of the same thing as your second example! (The `foldl` lambda isn't point-free either, but I have a feeling that's just a reimplementation of `all` from `Data.List` so that expression could quickly be made point-free.) – kqr Oct 13 '13 at 20:34
  • fold with `(&&)` is just `and`: `palindrome = and . uncurry (zipWith (==)) . join ((,).reverse)`. But of course `and . uncurry (zipWith (==))` is just an implementation of `uncurry (==)`, as [the answer by swish](http://stackoverflow.com/a/19350803/849891) exemplifies. :) – Will Ness Oct 14 '13 at 09:11
2

(->) r is also a Monad, so your palindrome checker can be written with monadic bind, which is probably more readable than the Applicative solution above

palindrome :: String -> Bool
palindrome = reverse >>= (==)
ademidov
  • 21
  • 1
  • 1
  • a side note: `ap k g == g >>= (flip k) == k <*> g == \x -> k x (x r)`. So your code expresses `reverse xs == xs`. – Will Ness Oct 14 '13 at 09:07
1

Yes.

palindrome :: String -> Bool
palindrome = ap (==) reverse
Stephen Diehl
  • 8,271
  • 5
  • 38
  • 56
1
 palindrome :: String -> Bool
 palindrome = uncurry (==) . (id &&& reverse)

(&&&) is defined in Control.Arrow so that (f &&& g) x = (f x, g x).

Will Ness
  • 70,110
  • 9
  • 98
  • 181
swish
  • 367
  • 4
  • 18