From the readability point of view, I'd suggest to keep some maximum line length, like 72 or 80 characters. Beyond that it's difficult to read. Also instead of having Either (Either X Y) Z, declare your own data type with 3 constructors. Not only it'll be simpler, but the constructor names will also be more descriptive and it'll be easier to understand what's going on. You should also document the function better, it's not clear what the Int argument is without thoroughly inspecting the code. A small improvement is also replacing nested ifs with a case statement.
In general, I'd say that it's not really possible to make a genuine single-pass solution.
Obviously we can't avoid checking the last element, if the list is a palindrome, and we need to have the first element to compare it to. So we'll always have to either get to the last element at the beginning, or keep the elements as we traverse the list, to have them for comparison when we get to the end, So we can't get to the situation when we just traverse the list from the beginning to the end, releasing the elements already traversed.
In your case, you're also traversing the list twice, although it's somewhat hidden. The first pass is the recursive call to walk, which gets to the end of the list. And the second traversal is occurring in the line
Left (Right (y:ys)) -> if y == x then
(if n > 0 then Left (Right ys) else Right True)
else Right False
where we're traversing ys as walk returns to its parent call.
(The above nested ifs can be rewritten as
... -> case () of
_ | y /= x -> Right False
| n > 0 -> Left (Right ys)
| otherwise -> Right True
using case.)
Furthermore, since walk calls itself recursively and examines the result of the recursive call, it can't be optimized to tail recursion, so you're building a chain of n calls on the stack.
Another thing to notice is that the whole original list is kept in memory until the whole chain of walks finishes.
My attempt to solve this problem would look like this:
isPal' :: (Eq a) => [a] -> Bool
isPal' xs = f [] xs xs
where
f ss xs [] = ss == xs
f ss (_:xs) [_] = ss == xs
f ss (x:xs) (_:_:es) = f (x:ss) xs es
We're traversing the list at two different "speeds" at the same time in a tail-recursive loop, to get to the middle. During that we compute the reverse of the traversed part in ss. When we hit the middle after n/2 steps, we just compare the accumulated reversed first half with the rest. The combined length of ss and xs is always n and if we find out in the middle a difference, like in "aaabcaaa", we finish and release resources early.
Since all suggested algorithms are O(n), it's hard to decide which one will be more efficient just by reasoning. We'd have to do some measurements, for example using the criterion package.
Update: The problem could be actually solved in a genuine one pass using a rolling checksum, at the cost of having false positives in (rare) cases of hash collisions. Just compute two rolling checksums while traversing the list, one forwards and one backwards, and compare them at the end.
import Control.Arrow ((&&&), second)
import Data.Foldable (foldMap)
import Data.Function (on)
import Data.Hashable
import Data.Monoid
import Data.Word
-- see https://en.wikipedia.org/wiki/Rolling_hash
-- and https://en.wikipedia.org/wiki/Lehmer_random_number_generator#Parameters_in_common_use
modulus :: Word64
modulus = 2^31 - 1
expG :: Word64
expG = 7^5
data RKHash = RKHash { rkExp :: Word64, rkVal :: Word64 }
deriving (Eq, Show)
inject :: (Hashable a) => a -> RKHash
inject = RKHash expG . (`mod` modulus) . fromIntegral . hash
instance Monoid RKHash where
mempty = RKHash 1 0
mappend (RKHash e1 v1) (RKHash e2 v2) =
RKHash ((e1 * e2) `mod` modulus) ((v1 * e2 + v2) `mod` modulus)
isPalindrome :: (Hashable a) => [a] -> Bool
isPalindrome = uncurry (on (==) rkVal) . second getDual
. foldMap ((id &&& Dual) . inject)
