Difference between revisions of "99 questions/Solutions/6"
< 99 questions | Solutions
Jump to navigation
Jump to search
(Added >>= solution) |
|||
(13 intermediate revisions by 10 users not shown) | |||
Line 5: | Line 5: | ||
isPalindrome xs = xs == (reverse xs) |
isPalindrome xs = xs == (reverse xs) |
||
</haskell> |
</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> |
||
+ | |||
+ | Using <code>>>=</code> instead of <code><*></code>: |
||
+ | |||
+ | <haskell> |
||
+ | isPalindromeM :: (Eq a) => [a] -> Bool |
||
+ | isPalindromeM = 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> |
||
+ | |||
+ | [[Category:Programming exercise spoilers]] |
Latest revision as of 00:08, 8 July 2019
(*) 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
Using >>=
instead of <*>
:
isPalindromeM :: (Eq a) => [a] -> Bool
isPalindromeM = 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))