Personal tools

99 questions/Solutions/6

From HaskellWiki

< 99 questions | Solutions(Difference between revisions)
Jump to: navigation, search
 
(Added solution using Control.Arrows fan out operator.)
 
(11 intermediate revisions by 8 users not shown)
Line 4: Line 4:
 
isPalindrome :: (Eq a) => [a] -> Bool
 
isPalindrome :: (Eq a) => [a] -> Bool
 
isPalindrome xs = xs == (reverse xs)
 
isPalindrome xs = xs == (reverse xs)
  +
</haskell>
  +
  +
<haskell>
  +
isPalindrome' [] = True
  +
isPalindrome' [_] = True
  +
isPalindrome' xs = (head xs) == (last xs) && (isPalindrome' $ init $ tail xs)
  +
</haskell>
  +
  +
Here's one to show it done in a fold just for the fun of it. Do note that it is less efficient then the previous 2 though.
  +
  +
<haskell>
  +
isPalindrome'' :: (Eq a) => [a] -> Bool
  +
isPalindrome'' xs = foldl (\acc (a,b) -> if a == b then acc else False) True input
  +
where
  +
input = zip xs (reverse xs)
  +
</haskell>
  +
  +
Another one just for fun:
  +
  +
<haskell>
  +
isPalindrome''' :: (Eq a) => [a] -> Bool
  +
isPalindrome''' = Control.Monad.liftM2 (==) id reverse
  +
</haskell>
  +
  +
Or even:
  +
  +
<haskell>
  +
isPalindrome'''' :: (Eq a) => [a] -> Bool
  +
isPalindrome'''' = (==) Control.Applicative.<*> reverse
  +
</haskell>
  +
  +
Here's one that does half as many compares:
  +
  +
<haskell>
  +
palindrome :: (Eq a) => [a] -> Bool
  +
palindrome xs = p [] xs xs
  +
where p rev (x:xs) (_:_:ys) = p (x:rev) xs ys
  +
p rev (x:xs) [_] = rev == xs
  +
p rev xs [] = rev == xs
  +
</haskell>
  +
  +
Here's one using foldr and zipWith.
  +
  +
<haskell>
  +
palindrome :: (Eq a) => [a] -> Bool
  +
palindrome xs = foldr (&&) True $ zipWith (==) xs (reverse xs)
  +
palindrome' xs = and $ zipWith (==) xs (reverse xs) -- same, but easier
  +
</haskell>
  +
  +
  +
<haskell>
  +
isPalindrome list = take half_len list == reverse (drop (half_len + (len `mod` 2)) list)
  +
where
  +
len = length list
  +
half_len = len `div` 2
  +
  +
isPalindrome' list = f_part == reverse s_part
  +
where
  +
len = length list
  +
half_len = len `div` 2
  +
(f_part, s_part') = splitAt half_len list
  +
s_part = drop (len `mod` 2) s_part'
  +
</haskell>
  +
  +
  +
Using Control.Arrows (&&&) fan out operator.
  +
  +
With monomorphism restriction:
  +
  +
<haskell>
  +
isPalindrome1 xs = (uncurry (==) . (id &&& reverse)) xs
  +
</haskell>
  +
  +
Point free with no monomorphism restriction:
  +
  +
<haskell>
  +
isPalindrome1 = (uncurry (==) . (id &&& reverse))
 
</haskell>
 
</haskell>

Latest revision as of 20:49, 30 November 2012

(*) Find out whether a list is a palindrome. A palindrome can be read forward or backward; e.g. (x a m a x).

isPalindrome :: (Eq a) => [a] -> Bool
isPalindrome xs = xs == (reverse xs)
isPalindrome' []  = True
isPalindrome' [_] = True
isPalindrome' xs  = (head xs) == (last xs) && (isPalindrome' $ init $ tail xs)

Here's one to show it done in a fold just for the fun of it. Do note that it is less efficient then the previous 2 though.

isPalindrome'' :: (Eq a) => [a] -> Bool
isPalindrome'' xs = foldl (\acc (a,b) -> if a == b then acc else False) True input
	where
	input = zip xs (reverse xs)

Another one just for fun:

isPalindrome''' :: (Eq a) => [a] -> Bool
isPalindrome''' = Control.Monad.liftM2 (==) id reverse

Or even:

isPalindrome'''' :: (Eq a) => [a] -> Bool
isPalindrome'''' = (==) Control.Applicative.<*> reverse

Here's one that does half as many compares:

palindrome :: (Eq a) => [a] -> Bool
palindrome xs = p [] xs xs
   where p rev (x:xs) (_:_:ys) = p (x:rev) xs ys
         p rev (x:xs) [_] = rev == xs
         p rev xs [] = rev == xs

Here's one using foldr and zipWith.

palindrome :: (Eq a) => [a] -> Bool
palindrome xs = foldr (&&) True $ zipWith (==) xs (reverse xs)
palindrome' xs = and $ zipWith (==) xs (reverse xs) -- same, but easier


isPalindrome list = take half_len list == reverse (drop (half_len + (len `mod` 2)) list)
	where 
		len = length list
		half_len = len `div` 2
 
isPalindrome' list = f_part == reverse s_part
	where 
		len = length list
		half_len = len `div` 2
		(f_part, s_part') = splitAt half_len list
		s_part = drop (len `mod` 2) s_part'


Using Control.Arrows (&&&) fan out operator.

With monomorphism restriction:

isPalindrome1 xs = (uncurry (==) . (id &&& reverse)) xs

Point free with no monomorphism restriction:

isPalindrome1 = (uncurry (==) . (id &&& reverse))